数据结构树与二叉树C

1、Recap:00A00C00B11E11F11G00D11I11H注：此图中序遍历结果为: H, D, I, B, E, A, F, C, G0root0Recap:建立和遍历设计技巧：设计技巧：依某种顺序依某种顺序遍历二叉树，对每个结点遍历二叉树，对每个结点p，判断其左指，判断其左指针是否为空，以及其针是否为空，以及其前驱结点的前驱结点的右指针是否为空。右指针是否为空。每次只修改每次只修改前驱结点的右指针前驱结点的右指针（后继）和（后继）和本结点的左指针本结点的左指针（前（前驱）驱），参见算法，参见算法6.6。若若p-lchildNULL, ,则则p-Ltag=1;p-Ltag=1;p-lc

2、hildp-lchildpre;pre; /p/p的前驱线索应存的前驱线索应存p p结点的左边结点的左边若若pre-rchildNULL, 则则pre-Rtagpre-Rtag1;1;pre-rchild=ppre-rchild=p; /pre/pre的后继线索应存的后继线索应存prepre结点的右边结点的右边以以中序线索二叉树中序线索二叉树为例：为例：当当RTag=1时，直接后继指针就在其时，直接后继指针就在其rchild域内；域内；当当RTag=0时，直接后继是当前结点时，直接后继是当前结点的结点的结点；请注意中序遍历规则是请注意中序遍历规则是LDR，方法：加线抹线旋转 abeidfhgc

3、abeidfhgc兄弟相连长兄为父孩子靠左回顾1：树如何转为二叉树？左孩子右兄弟表示法3回顾回顾2 2：二叉树怎样还原为树？二叉树怎样还原为树？abeidfhgc要点：逆操作，把所有右孩子变为兄弟！ abdefhgic4法一：法一： 各森林先各自转为二叉树； 依次连到前一个二叉树的右子树上。讨论1：森林如何转为二叉树？即F=T1, T2, ,Tm B=root, LB, RB法二：法二：森林直接变兄弟，再转为二叉树（参见教材P138图6.17，两种方法都有转换示意图）法一和法二得到的二叉树是完法一和法二得到的二叉树是完全相同的、惟一的。全相同的、惟一的。5ABCDEFGHJIABCDEFGHJ

4、IBCDEFGHJI森林转二叉树举例：森林转二叉树举例：（用法二，森林直接变兄弟，再转为二叉树）（用法二，森林直接变兄弟，再转为二叉树）兄弟相连 长兄为父头树为根 孩子靠左6BCDEFGHJI讨论讨论2 2：二叉树如何还原为森林？二叉树如何还原为森林？要点：把最右边的子树变为森林，其余右子树变为兄弟 即B=root, LB, RB F=T1, T2, ,TmABCDEFGHJIEFABCDGHJI7树有三种常用存储方式：双亲表示法 孩子表示法 孩子兄弟表示法 nextsiblingdatafirstchild指向左孩子指向右兄弟问：树二叉树的“连线抹线旋转” 如何由计算机自动实现？答：用“左孩

5、子右兄弟”表示法来存储即可。 8abecdfhgbacedfgh例如例如：9例如：abdec先根序列：后根序列：a b c d eb d c e a深度优先遍历（先根、后根）广度优先遍历（层次）先根遍历访问根结点；依次先根遍历根结点的每棵子树。后根遍历 依次后根遍历根结点的每棵子树； 访问根结点。树没有中序遍历（因子树不分左右）10讨论：树若采用“先转换，后遍历”方式，结果是否一样？abdec先序遍历：后序遍历：中序遍历：d e c b aabdeca b c d eb d c e a1. 树的先根遍历与二叉树的先序遍历相同； 2. 树的后根遍历相当于二叉树的中序遍历；3. 树没有中序遍历，因

6、为子树无左右之分。结论：树的先根序列：树的先根序列：a b c d e树的后根序列：树的后根序列：b d c e a11先序遍历若森林为空，返回；访问森林中第一棵树的根结点；先序遍历第一棵树的根结点的子树森林；先序遍历除去第一棵树之后剩余的树构成的森林。森林的遍历森林的遍历ABCDEFGHJI深度优先遍历（先序、中序）广度优先遍历（层次）中序遍历若森林为空，返回；中序遍历森林中第一棵树的根结点的子树森林；访问第一棵树的根结点；中序遍历除去第一棵树之后剩余的树构成的森林。12讨论：若采用“先转换，后遍历”方式，结果是否相同？例如：先序序列：中序序列：A B C D E F G H I JB C

7、D A F E H J I G先序序列：中序序列：A B C D E F G H I JB C D A F E H J I G结论：森林的先序和中序遍历在两种方式下的结果相同。13什么是带权树？什么是带权树？abdc7524即叶子带有权值。例如：最优二叉树(哈夫曼树)如果是带权路径长度最短的树14一、Huffman树的构建二、Huffman编码三、算法实现最优二叉树Huffman树Huffman编码带权路径长度最短的树不等长编码是通信中最经典的压缩编码15树的带权路径长树的带权路径长度如何计算？度如何计算？WPL = wklk k=1nabdc7524(a)cdab2457(b)bdac752

8、4(c)WPL=WPL=WPL=Huffman树是WPL 最小的树树中所有叶子结点的带权路径长度之和36463516构造构造Huffman树的基本思想：树的基本思想： 权值大的结点用短路径，权值大的结点用短路径， 权值小的结点用长路径。权值小的结点用长路径。一、一、 HuffmanHuffman树树（最优二叉树）（最优二叉树）路路 径径：路径长度路径长度：树的路径长度树的路径长度：带权路径长度带权路径长度：树的带权路径长度树的带权路径长度：HuffmanHuffman树树：由一结点到另一结点间的分支所构成。由一结点到另一结点间的分支所构成。路径上的分支数目。路径上的分支数目。从树根到从树根到每

9、一结点每一结点的路径长度之和。的路径长度之和。结点到根的路径长度与结点上权的乘积（结点到根的路径长度与结点上权的乘积（WPLWPL）debacf g即树中所有即树中所有叶子结点叶子结点的带权路径长度之和的带权路径长度之和带权路径长度最小的树。带权路径长度最小的树。例如：例如：aeae的路径长度的路径长度树长度树长度210Huffman常译为赫夫曼、霍夫曼、哈夫曼等Weighted Path Length17构造构造HuffmanHuffman树的步骤树的步骤（即（即HuffmanHuffman算法）：算法）：(1) 由给定的由给定的 n 个权值个权值 w1, w2, , wn 构成构成n棵二叉

10、树的集合棵二叉树的集合F = T1, T2, , Tn （即森林）（即森林） ，其中每棵二叉树，其中每棵二叉树 Ti 中中只有一个带权为只有一个带权为 wi 的根结点，其左右子树均空。的根结点，其左右子树均空。(2) 在在F 中选取中选取两棵根结点权值最小的树两棵根结点权值最小的树 做为左右子树构造做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值一棵新的二叉树，且让新二叉树根结点的权值等于等于其左其左右子树的根结点右子树的根结点权值之和权值之和。(3) 在在F 中删去这两棵树，同时将新得到的二叉树加入中删去这两棵树，同时将新得到的二叉树加入 F中中。(4) 重复重复(2) 和和(3)

11、, 直到直到 F 只含一棵树为止。这棵树便是只含一棵树为止。这棵树便是Huffman树。树。18在权值集合7,5,2,4中，总是合并当前值最小的两个权具体操作步骤：具体操作步骤：a. 初始b. 合并2 4c. 合并5 6d. 合并7 1119例题：已知权值例题：已知权值 W= 5, 6, 2, 9, 7 , 建立对应的建立对应的Huffman树树20Huffman树的应用：树的应用：设有设有4 4个字符个字符d,i,a,nd,i,a,n，出现的频度分别为，出现的频度分别为7,5,2,47,5,2,4，怎样编码才能使它们组成的报文长度最短？，怎样编码才能使它们组成的报文长度最短？法法1 1：等长

12、编码等长编码（如二进制编码）（如二进制编码）令令d=d=0000，i=i=0101，a=a=1010，n=n=1111，则：，则：WPLWPL1 12bit2bit(7(75 52 24 4）3636法法2 2：不等长编码不等长编码（如（如HuffmanHuffman编码）编码）令令d=d=0 0;i=;i=1010,a=,a=110110,n=,n=111111，则：，则：WPLWPL2 2= =1 1bitbit7 72 2bitbit5+35+3bitbit(2+4)=(2+4)=3535明确：要实现明确：要实现HuffmanHuffman编码，就要先构造编码，就要先构造HuffmanH

13、uffman树树讨论：讨论：HuffmanHuffman树有什么用？树有什么用？频度高的信息用频度高的信息用短码，低的用长短码，低的用长码，传输效率肯码，传输效率肯定高！定高！最小冗余编码、信息高效传输最小冗余编码、信息高效传输21按左“0”右“1” 对Huffman树的所有分支编号dain111000Huffman编码结果：d=0, i=10, a=110, n=111WPL=1bit72bit5+3bit(2+4)=35（小于等长码的WPL=36）Huffman编码也称为22哈夫曼编码哈夫曼编码 哈夫曼树的应用很广，哈夫曼编码就是其在电讯通信中的应用之一。在电讯通信业务中，通常用二进制编码

14、来表示字母或其他字符，并用这样的编码来表示字符序列。 例：例：如果需传送的电文为如果需传送的电文为 ABACCDA，它只用到，它只用到四种字符，用两位二进制编码便可分辨。四种字符，用两位二进制编码便可分辨。假设假设 A, B, C, D 的编码分别为的编码分别为 00, 01, 10, 11，则上述电文便为，则上述电文便为 00010010101100（共（共 14 位），译码员按两位进行位），译码员按两位进行分组译码，便可恢复原来的电文。分组译码，便可恢复原来的电文。 能否使编码总长度更短呢能否使编码总长度更短呢？ 23实际应用中各字符的出现频度不相同实际应用中各字符的出现频度不相同 用用（

15、长长）编码表示频率）编码表示频率（小小）的字符）的字符 使得编码序列的总长度最小，使所需总空间量最少使得编码序列的总长度最小，使所需总空间量最少 若假设若假设 A, B, C, D 的编码分别为的编码分别为 0，00，1，01，则电文则电文 ABACCDA 便为便为 000011010（共（共 9 位）。位）。可译为可译为 BBCCDA、ABACCDA、AAAACCACA 存在多义性存在多义性24要求任一字符的编码都不能是另一字符编码的前缀！要求任一字符的编码都不能是另一字符编码的前缀！ 这种编码称为这种编码称为（其实是非前缀码）。（其实是非前缀码）。 译码的惟一性问题译码的惟一性问题 利用最

16、优二叉树可以很好地解决上述两个问题利用最优二叉树可以很好地解决上述两个问题 在编码过程要考虑两个问题在编码过程要考虑两个问题 数据的最小冗余编码问题数据的最小冗余编码问题 译码的惟一性问题译码的惟一性问题 25 以电文中的字符作为叶子结点构造二叉树。以电文中的字符作为叶子结点构造二叉树。然后将然后将二叉二叉树树中中 结点引向其左孩子的分支标结点引向其左孩子的分支标 0，引向其右孩子的分支标，引向其右孩子的分支标 1； 每每 个字符的编码即为从根到每个叶子的路径上得到的个字符的编码即为从根到每个叶子的路径上得到的 0, 1 序列。如序列。如 此此得到的即为二进制前缀编码。得到的即为二进制前缀编码

17、。 用二叉树设计二进制前缀编码用二叉树设计二进制前缀编码 例：例： ABCD0 1 0 1 0 1 编码编码： A：0 B：10 C：110 D：111 任意一个叶子任意一个叶子 结点都不可能结点都不可能 在其它叶子结在其它叶子结 点的路径中。点的路径中。 26假设各个字符在电文中出现的假设各个字符在电文中出现的（或频率）为（或频率）为 wi ，其其为为 li，电文中只有，电文中只有 n 种字符，种字符，为：为： niiilw1叶子结点的权叶子结点的权 从根到叶子的路径长度从根到叶子的路径长度 WPL设计电文总长最短的编码设计电文总长最短的编码 设计哈夫曼树（以设计哈夫曼树（以 n 种种 字符

18、出现的频率作权）字符出现的频率作权） 用哈夫曼树设计总长最短的二进制前缀编码用哈夫曼树设计总长最短的二进制前缀编码 由哈夫曼树得到的二进制前缀编码称为由哈夫曼树得到的二进制前缀编码称为哈夫曼编码哈夫曼编码 27解：解： A CBD0 0 0 1 1 1 编码编码： A：0 C：10 B：110 D：111 例：例：如果需传送的电文为如果需传送的电文为 ABACCDA，即：，即：A, B, C, D 的频率（即权值）分别为的频率（即权值）分别为 0.43, 0.14, 0.29, 0.14，试构造哈夫曼编码。试构造哈夫曼编码。 则电文则电文 ABACCDA 便为便为 0110010101110（

19、共（共 13 位）。位）。 28解：解： EBD编码编码： A：11 C：10 E：00 B：010 D：011 例：例：如果需传送的电文为如果需传送的电文为 ABCACCDAEAE， 即：即：A, B, C, D, E 的频率（即权值）分别为的频率（即权值）分别为 0.36, 0.1, 0.27, 0.1, 0.18，试构造哈夫曼编码。，试构造哈夫曼编码。 则电文则电文 ABCACCDAEAE 便为便为 110101011101001111001100 （共（共 24 位，比位，比 33 位短）。位短）。 C A 1 1 1 1 0 0 0 0 29 译码译码 从哈夫曼从哈夫曼树根开始，对待

20、译码电文逐位取码。若树根开始，对待译码电文逐位取码。若编码是编码是“0”，则向左走；若编码是，则向左走；若编码是“1”，则向右走，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束。发，直到电文结束。 1111 T ; A C S电文为电文为 “1101000” 译文只能是译文只能是“CAT” 30严习题集严习题集6.266.26：设通信用的电文由字符集设通信用的电文由字符集a,b,c,d,e,f,g,ha,b,c,d,e,f,g,h中的字母构成，这中的字母构成，这8 8个字母在电个字母在电文中出现的概率分别为文中出现的概率分

21、别为 0.07, 0.19, 0.02, 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 0.06, 0.32, 0.03, 0.21, 0.10 ，试为这，试为这8 8个字个字母设计哈夫曼编码。母设计哈夫曼编码。310.070.070.190.190.020.020.060.060.320.320.030.030.210.210.100.100.070.070.190.190.020.020.060.060.320.320.030.030.210.210.100.100.050.050.070.07 0.190.190.020.020.060.0

22、60.320.320.030.030.210.21 0.100.100.050.050.110.110.070.070.190.190.020.020.060.060.320.320.030.030.210.210.100.100.050.050.110.110.170.17320.070.070.190.190.020.020.060.060.320.320.030.030.210.210.100.100.050.050.110.110.170.170.280.280.070.070.190.190.020.020.060.060.320.320.030.030.210.210.100.10

23、0.050.050.110.110.170.170.280.280.400.40330.070.070.190.190.020.020.060.060.320.320.030.030.210.210.100.100.050.050.110.110.170.170.280.280.400.400.600.60a0.070.07b0.190.19c0.020.02d0.060.06e0.320.32f0.030.03g0.210.21h0.100.100.050.050.110.110.170.170.280.280.400.400.600.601.001.0000000001111111a a

24、= = 1010 1010b b = = 00 00c c = = 10000 10000d d = = 1001 1001e e = = 11 11f f = = 10001 10001g g = = 01 01h h = = 1011 101134WPL = 2.61typedef struct typedef struct unsigned int weight;unsigned int weight;unsigned int parent,lchild,rchild;unsigned int parent,lchild,rchild; HTNode, HTNode, * *Huffma

25、nTree; /HuffmanTree; /动态分配数组存储赫夫曼树动态分配数组存储赫夫曼树typedef char typedef char * * *HuffmanCode; HuffmanCode; Huffman Huffman树没有度为树没有度为1 1的结点的结点 一棵有一棵有n n0 0个叶子结点的个叶子结点的HuffmanHuffman树共有树共有2n2n0 0-1-1个结点个结点设共有设共有n n个节点，则个节点，则n=nn=n0 0+n+n2 2;(;(没有度为没有度为1 1的节点，的节点，n n1 1=0)=0)度之和度之和 = n-1 = 2n= n-1 = 2n2 2

26、n-1 = 2(n-n n-1 = 2(n-n0 0) ) n=2n n=2n0 0-1-1 可以存储在一个大小为可以存储在一个大小为2n2n0 0-1-1的一维数组中。的一维数组中。节点权值，父节点，左孩子节点和右孩子节点节点权值，父节点，左孩子节点和右孩子节点 35void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int * *w, int n)w, int n) /w/w存放存放n n个字符的权值

27、，构造赫夫曼树个字符的权值，构造赫夫曼树HT,HT,并求出并求出n n个字符的赫夫曼编码个字符的赫夫曼编码HCHC if (n=1) return; if (n=1) return; / n/ n为字符数目，为字符数目， m=2m=2* *n-1; n-1; / m/ m为结点数目为结点数目 HT = (HuffmanTree)malloc(m+1)HT = (HuffmanTree)malloc(m+1)* *sizeof(HTNodesizeof(HTNode);); /HT /HT存放存放HuffmanHuffman树结构，树结构，0 0号单元未用号单元未用, ,其余前其余前n n个单元

28、个单元 /存放树的叶子结点，存放树的叶子结点，n-1n-1个单元存放内部结点个单元存放内部结点 for (p=HT1, i=1; i=n; +i,+p,+w) for (p=HT1, i=1; iweight = p-weight = * *w; p-parent=0;w; p-parent=0; p-lchild=0; p-rchild=0; p-lchild=0; p-rchild=0; / / * *p=p=* *w,0,0,0w,0,0,0；初始化；初始化HTHT中的叶结点循环退出时中的叶结点循环退出时i=n+1;i=n+1;36 for (; i=m;+i,+p) for (; iw

29、eight = 0; p-parent=0; p-weight = 0; p-parent=0; p-lchild=0; p-rchild=0; p-lchild=0; p-rchild=0; / / * *p=0,0,0,0; p=0,0,0,0; 初始化初始化HTHT中的内部结点中的内部结点 for (i=n+1; i=m;+i) for (i=n+1; i=m;+i) / / 建赫夫曼树，建赫夫曼树，( (建立建立HTHT静态链表中的链静态链表中的链) ) Select(HT,i-1,s1,s2); Select(HT,i-1,s1,s2);/在在HT1HT1i-1i-1中选择中选择pa

30、rentparent / / 为为0 0且且weightweight最小的两个结点，序号分别为最小的两个结点，序号分别为s1s1和和s2s2 HTs1.parent=i; HTs2.parent = i; HTs1.parent=i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; HTi.weight = HTs1.weight + HTs2.weight; 37 /从叶子到根逆向求赫夫曼编码

31、从叶子到根逆向求赫夫曼编码1. HC= (HuffmanCode)(n+1)*sizeof(char *);2. cd = ( *)n * (char) ); 3. cdn-1=0; /编码结束符编码结束符4. (i=1;i=n;+i) /逐个字符求赫夫曼编码逐个字符求赫夫曼编码5. start = n-1; /编码结束符位置编码结束符位置6. (c=i,f=HTc.parent; f!=0; c=f,f=HTf.parent) /从叶子到根逆向求编码从叶子到根逆向求编码7. (HTf.lchild =c) cd-start=0;8. cd-start=1;9. HCi=(char *)(n-

32、start)*(char); 10. strcpy(HCi,&cdstart); /从从cd复制编码串到复制编码串到HC11. (cd); /释放工作空间释放工作空间 /HuffanCoding38HuffmanHuffman编码举例编码举例解：先将概率放大100倍，以方便构造哈夫曼树。放大后的权值集合 w= 7, 19, 2, 6, 32, 3, 21, 10 ，按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。例1【严题集6.26】：假设用于通信的电文仅由8个字母 a, b, c, d, e, f, g, h 构成，它们在电文中出现的概率分别为 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 ，试为这8个字母设计哈夫曼编码。如果用07的二进制编码方案又如何？ 【类同P148例2】000000281001071