哈夫曼树

1、定义

 

给定n个权值为n的叶子结点，构造一科二叉树，如果带权路径长度达到最小，成这样的二叉树为最优二叉树，也就是哈夫曼树（Huffman tree）

 

2、构造

 

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1,w2,…,wn,则哈夫曼树的构造规则

为：
(1) 将w1,w2,…,wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

 

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。 

    下面给出哈夫曼树的构造过程，假设给定的叶子结点的权分别为1,5,7,3，则构造哈夫曼树过程如图6-29所示。 从图6-29可知，n 个权值构造哈夫曼树需n-1次合并，每次合并，森林中的树数目减1，最后森林中只剩下一棵树，即为我们求得的哈夫曼树。