哈夫曼

哈夫曼算法是一种用于构建最优二叉树的数据结构技术。其过程如下：

首先，进行初始化阶段。给定一组权值{w1, w2, ..., wn}，这些权值表示n个元素的权重。我们从这些权值构建n棵初始的二叉树集合F，每棵树Ti只有一个带权wi的根节点，且其左右子树都是空的。

接着，寻找最小树。在F中选择两棵权值最小的树作为新树的左右子树，合并它们，新树的根节点权值等于左右子树根节点权值之和。这样操作的目的是构造一棵权值更小的新树。

然后，更新F。将这两棵树从集合中移除，并将新树添加至F中。这个过程会递归进行，直到F中只剩下一棵树为止。

当只剩下一棵树时，这棵特殊的树就是哈夫曼树。它具有两个显著特性：一是所有的边权值都是由两个子节点的权值之和构成，二是它是最优的，因为每次合并都是选择权值最小的两棵树，使得整个树的带权路径长度（即所有边权值之和）最小。

哈夫曼树是一种树形结构，用哈夫曼树的方法解编程题的算法就叫做哈夫曼算法。树并不是指植物，而是一种数据结构，因为其存放方式颇有点象一棵树有树叉因而称为树。 最简哈夫曼树是由德国数学家冯。哈夫曼 发现的，此树的特点就是引出的路程最短。 概念理解：1.路径 从树中一个节点到另一个节点之间的分支构成这两个节点之间的路径。2.路径长度 路径上的分支数目称作路径长度。