数据结构第6章树和二叉树解读.ppt

结点的权及带权路径长度： 若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。 从根结点到该结点之间的路径长度与该结点的权的乘积称为结点的带权路径长度。 树的带权路径长度（ Weighted Path Length ，WPL）：树的各叶结点所带的权值 wi 与该结点到根的路径长度 li 的乘积的和。 Huffman树——带权路径长度达到最小的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。 例 有4个结点，权值分别为7，5，2，4，构造有4个叶子结点 的二叉树 a b c d 7 5 2 4 WPL=7*2+5*2+2*2+4*2=36 d c a b 2 4 7 5 WPL=7*3+5*3+2*1+4*2=46 a b c d 7 5 2 4 WPL=7*1+5*2+2*3+4*3=35 对于已知的一组叶子的权值W1，W2，…，Wn： 构造Huffman树的方法——Huffman算法 构造Huffman树步骤 以权值分别为W1,W2．．．,Wｎ的ｎ个结点，构成n棵二叉树T1,T2,．．．,Tn并组成森林F={T1,T2,．．．Tn},其中每棵二叉树 Ti仅有一个权值为 Wi的根结点； 在F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和（根结点的权值=左右孩子权值之和，叶结点的权值= Wi） 从F中删除这两棵二叉树，同时将新二叉树加入到F中; 重复(2)、(３)直到F中只含一棵二叉树为止，这棵二叉树就是Huffman 树。 F : {7} {5} {2} {4} F : {7} {5} {6} F : {7} {11} 7 5 2 4 初始 合并{2} {4} 7 5 2 4 6 F : {18} 11 7 5 2 4 6 合并{5} {6} 5 合并{7} {11} 2 7 4 6 11 18 举例霍夫曼树的构造过程 例 w={5, 29, 7, 8, 14, 23, 3, 11} 5 14 29 7 8 23 3 11 14 29 7 8 23 11 3 5 8 8 7 15 14 29 23 3 5 8 11 11 3 5 8 19 14 29 23 8 7 15 11 3 5 8 19 29 23 14 8 7 15 29 29 14 8 7 15 29 11 3 5 8 19 23 42 11 3 5 8 19 23 42 29 14 8 7 15 29 58 11 3 5 8 19 23 42 29 14 8 7 15 29 58 100 　　由哈夫曼树构造思想得知，初始森林中共有n棵二叉树，每棵树中都仅有一个孤立的结点，接着将当前森林中的两棵根结点权值最小的二叉树合并成一棵新的二叉树。每次都是将两个子树合并，所以不存在度为1的结点 特点1：哈夫曼树中不存在度为1的结点 　　由哈夫曼树构造思想得知，初始森林中共有n棵二叉树，每棵树中都仅有一个孤立的结点，接着将当前森林中的两棵根结点权值最小的二叉树合并成一棵新的二叉树。每合并一次，森林中就减少一棵树。显然要进行n-1次合并，才能使森林中的二叉树的数目，由n棵减少到只剩下一棵最终的哈夫曼树。并且每次合并，都要产生一个新结点。合并n-1次共产生n-1个新结点，并且它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中共有2n-1个结点。 特点2：n个叶子结点构造的哈夫曼树中，共有2n-1个结点 特点3：任一棵哈夫曼树的带树路径长度等于所有分支结点（非叶子结点）值的累加和。 11 3 5 8 19 23 42 29 14 8 7 15 29 58 100 哈夫曼结点结构(采用静态链表) weight lchild rchild parent Huffman树应用 最佳判定树 等级 分数段 比例 A B C D E 0~59 60~69 70~79 80~89 90~100 0.05 0.15 0.40 0.30 0.10 a60 a90 a80 a70 E Y N D Y N C Y N B Y N A 70?a80 a60 C Y N B Y N D Y N E Y N A 80?a90 60?a70 E A D B C a80 a70 a60 a90 E Y N D Y N C Y N B Y N A 在远程通讯中，要将待传字符转换成由二进制的字符串： 设要传送的字符为： ABACCDA 若编码为：A—00 B—01 C—10 D---11