哈夫曼树在排序算法中的案例教学研究

吐尔地·托合提，崔青，刘淑娴

（新疆大学信息科学与工程学院，乌鲁木齐 830046）

0 引言

哈夫曼树（Huffman Tree），又被称为最优二叉树，是一种带权路径长度最小的二叉树，其应用也很广泛，如基于哈夫曼树的编码[1]、压缩[2-3]、加密[4-5]、数据采样[6]等。在教学中，一般我们重点讲解带权路径长度的概念、哈夫曼树的性质、哈夫曼树的构造，以及哈夫曼编码[8]。其实，哈夫曼树也可以用来对于数据元素序列进行排序。

从哈夫曼树的性质可知，权重越大的叶子结点越靠近根结点，而权重越小的叶子结点离根结点越远。因此，将待排序序列中的每一个元素看成一个叶子结点，将元素关键码看成其权重（关键码为整形情况下），构造一棵哈夫曼树，然后层序遍历并依次输出叶子结点，就能得到基本有序（降序）序列。如果，在哈夫曼树的构造、遍历和输出过程中增设一些约束，那么也完全可以做到对数据元素的降序或升序排序。

本文在数据结构教学中，针对内部排序提出一个教学案例，在排序方法中引入哈夫曼树、二叉树的遍历、栈和队列等综合内容，通过讲解一些启发思路的知识点，一方面加深了学生对于哈夫曼树的性质、构造方法、二叉树遍历算法，以及哈夫曼树、栈和队列应用的理解和掌握，另一方面引导学生要认识到解决问题有多种方案可选，鼓励学生从知识中体会和掌握算法设计的思维方式和技巧，这有助于使学生分析问题和解决问题的能力得到提升。

1 基于哈夫曼树的排序算法思路

在待排序序列中数据元素关键码为整形（int 形）情况下，我们可以将每一个数据元素看成一个叶子结点，将数据元素关键码看成其权重构造一棵哈夫曼树。……