数据结构 | 树之哈夫曼树

定义

• 又称——最优二叉树
• 给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

构造算法

• 1）对给定的个权值构成棵二叉树的初始集合，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。
• 2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
• 3）从中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合中。
• 4）重复2）和3），直到集合F中只有一棵二叉树为止。

相关定理

• 对于具有个叶子节点的哈夫曼树，共有个节点。