哈夫曼树的建立



一、 实验目的：



1． 理解哈夫曼树及其应用。



2． 掌握生成哈夫曼树的算法。



二、 实验内容：



哈夫曼树，即最优树，是带权路径长度最短的树。有着广泛的应用。在解决某些判定问题上，及字符编码上，有着重要的价值。



构造一棵哈夫曼树，哈夫曼最早给出了算法，称为哈夫曼算法：



（1）根据给定的N个权值 W1，W2，W3，……，Wn ，构成N棵二叉树的集合F= T1，T2，T3，……，Tn ，其中每棵二叉树T1只有一个带权为WI的根结点，其左右子树均空。



（2）在 F中选出两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的权值为其左右子树上的根结点的权值之和。



（3）在F中删除这两棵树，同时将新得到的加到F之中。重复（2）和（3），直至F中只剩一个为止。