哈夫曼树与树的应用

哈夫曼树与树的应用内容摘要：

1,T2,… ,Tn}， 其中每一棵二叉树 Ti中只有一个带权为 wi的根结点 ， 其左右子树为空。 ② 在 F中选取两棵权值最小的树作为左右子树以构造一棵新的二叉树，且新二叉树的根结点的权值为其左右子树根结点权值之和。 ③ 在 F中删除这两棵树，同时将新得到的二叉树加入 F中。 ④ 重复 (2)和 (3)，直到 F中只含一棵树为止。 Hu Junfeng 16 哈夫曼树的构造过程 6 12 2 3 2 3 5 6 12 2 3 5 6 11 12 2 3 5 6 11 12 23 4棵只有根的二叉树 3合并得到 3棵二叉树 6合并得到 2棵二叉树 1 12合并得到 1棵二叉树 左右选择不同，得到的 HuffMan树形态不同，但 WPL相同。 Hu Junfeng 17 哈夫曼树的存储实现 • 存储结构可以有多种，如二叉链表、三叉链表等。 下面给出一种顺序结构 (一维数组），结点结构： – ww: 以该结点为根的子树中所有外部结点的加权和。 – parent: 父结点在数组中的存储位置（下标），根无父，设为 1。 – llink: 左孩子存储位置，对于外部结点，无孩子，设为 1。 – rlink: 右孩子存储位置，对于外部结点，无孩子，设为 1。 ww parent llink rlink Hu Junfeng 18 哈夫曼树的表示 2 • 假定外部结点个数为 m，则内部结点个数必为 m1，因此最后得到的 HuffMan树必定有 2m1个结点。 因此，用 2m1个元素的一维数组就可以存储该 HuffMan树。 每个元素表示一个结点，前 m个存储外部结点，后 m1个用于内部结点。 • struct HtNode /*哈夫曼树结点的结构 */ { int ww。 int parent, llink, rlink。 }。 Hu Junfeng 19 哈夫曼树的表示 3 • struct HtTree /*哈夫曼树类型 */ { int m。 /*外部结点的个数 */ int root。 /* 哈夫曼树根在数组中的位置 */ struct HtNode *ht。 /*存放 2m1个结点的数组 */ }。 typedef struct HtTree *PHtTree。 /* 哈夫曼树类型的指针类型 */ struct HtTree /*哈夫曼树类型 */ { stru。