树与森林的遍历

《树与森林的遍历》由会员分享，可在线阅读，更多相关《树与森林的遍历（36页珍藏版）》请在金锄头文库上搜索。

1、树与森林的遍历,1. 树的遍历 树的遍历方法主要有以下两种： 1） 先根遍历 若树非空，则遍历方法为： (1) 访问根结点。 (2) 从左到右， 依次先根遍历根结点的每一棵子树。 例如， 图6.21中树的先根遍历序列为ABECFHGD。,2） 后根遍历 若树非空， 则遍历方法为： （1） 从左到右， 依次后根遍历根结点的每一棵子树。 （2） 访问根结点。 例如， 图6.21中树的后根遍历序列为EBHFGCDA。,2. 森林的遍历 森林的遍历方法主要有以下三种： 1） 先序遍历 若森林非空， 则遍历方法为： (1) 访问森林中第一棵树的根结点。 (2) 先序遍历第一棵树的根结点的子树森林。 (3

2、) 先序遍历除去第一棵树之后剩余的树构成的森林。 例如， 图6.24(a)中森林的先序遍历序列为ABCDEFGHIJ。,2） 中序遍历若森林非空， 则遍历方法为： (1) 中序遍历森林中第一棵树的根结点的子树森林。 (2) 访问第一棵树的根结点。 (3) 中序遍历除去第一棵树之后剩余的树构成的森林。 例如， 图6.24(a)中森林的中序遍历序列为BCDAFEHJIG。,3） 后序遍历若森林非空， 则遍历方法为： (1) 后序遍历森林中第一棵树的根结点的子树森林。 (2) 后序遍历除去第一棵树之后剩余的树构成的森林。 (3) 访问第一棵树的根结点。,作业：1.二叉树的层次遍历算法（二叉链表存储）

3、；2.求二叉树中最大结点值（二叉链表存储）。,哈夫曼树及其应用,1. 哈夫曼树,1. 路径和路径长度 路径是指从一个结点到另一个结点之间的分支序列， 路径长度是指从一个结点到另一个结点所经过的分支数目。树的路径长度是从树根到每一结点的路径长度之和。,问题1: 什么样的二叉树的路径长度PL最小？ 路径长度为0的结点至多只有1个（根）； 路径长度为1的结点至多只有2个； 路径长度为2的结点至多只有4个； 依此类推，路径长度为k的结点至多只有2k个, 所以n个结点二叉树其路径长度至少等于如下所示序列的前n项之和。,结点路径长度0，1， 1， 2，2，2，2， 3， 3， 3， 3， 3， 3， 3，

4、 3， 4，结点数n n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=15,由图6.27可知，结点n对应的路径长度为log2n，所以前n项之和为 。完全二叉树的路径长度 (h为树的深度)，所以完全二叉树具有最小路径长度的性质，但不具有唯一性。有些树并不是完全二叉树， 但也可以具有最小路径长度，如图所示。,2. 结点的权和带权路径长度 在实际的应用中，人们常常给树的每个结点赋予一个具有某种实际意义的实数，我们称该实数为这个结点的权。在树形结构中，我们把从树根到某一结点的路径长度与该结点的权的乘积，叫做该结点的带权路径长度。,3. 树的带权路径长度 树的带权路径长度为树中所有叶

5、子结点的带权路径长度之和，通常记为：,其中n为叶子结点的个数，wi为第i个叶子结点的权值，li为第i个叶子结点的路径长度。 例如， 图 6.26中三棵二叉树的带权路径长度分别为：,WPL(a)=7252224236WPL(b)=4273532146WPL(c)=7152234335,问题2: 什么样的树的带权路径长度最小？ 例如： 给定一个权值序列2, 3, 4, 7， 可构造如图6.29所示的多种二叉树的形态。,4. 哈夫曼树,构造哈夫曼算法的步骤如下： （1） 用给定的n个权值w1, w2, , wn对应的n个结点构成n棵二叉树的森林F=T1, T2, , Tn，其中每一棵二叉树Ti(1i

6、n)都只有一个权值为wi的根结点，其左、右子树为空。 （2） 在森林F中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、右子树，标记新二叉树的根结点权值为其左右子树的根结点权值之和。 ,（3） 从F中删除被选中的那两棵二叉树， 同时把新构成的二叉树加入到森林F中。 （4） 重复（2）、（3）操作， 直到森林中只含有一棵二叉树为止， 此时得到的这棵二叉树就是哈夫曼树。,6.5.2 哈夫曼编码,表 6 1 指令的使用频率,表 6 2 指令的变长编码,图6.30 构造哈夫曼树示例,表 6 3 指令的哈夫曼编码,可以验证，该编码是前缀编码。若一段程序有1000条指令， 其中I1大约有400条，I

7、2大约有300条，I3大约有150条，I4大约有50条，I5大约有40条，I6大约有30条，I7大约有30条。对于定长编码，该段程序的总位数大约为310003000。采用哈夫曼编码后，该段程序的总位数大约为 1400230031505（50403030）2200。可见，哈夫曼编码中虽然大部分编码的长度大于定长编码的长度3， 却使得程序的总位数变小了。可以算出该哈夫曼编码的平均码长为：,举例：数据传送中的二进制编码。 要传送数据 state, seat, act, tea, cat, set, a, eat， 如何使传送的长度最短？ 首先规定二叉树的构造为左走0，右走1 ，如图6.31所示。 为

8、了保证长度最短， 先看字符出现的次数， 然后将出现次数当作权， 如图6.32所示。,图6.31 左走0，右走1的二叉树,图6.32 对字符按权排序,图6.33 构造哈夫曼树的过程,按规定：0左1右， 则有,000 001 01 10 11 2 3 5 7 8 c s e a t,所以有state 的编码为 00111101101, stat的编码为001111011。 构造满足哈夫曼编码的最短最优性质： (1) 若didj（字母不同），则对应的树叶不同。 因此前缀码（任一字符的编码都不是另一个字符编码）不同，一个路径不可能是其它路径的一部分， 所以字母之间可以完全区别。 ,(2) 将所有字符变

9、成二进制的哈夫曼编码， 使带权路径长度最短，相当总的通路长度最短。 若要求传送以上这些编码长度不一的数据， 且还要求传送词间互相区分，应如何设计最优编码呢？ 为保证传送词间互相区别，则需加入一空白字符出现频率， 空白字符出现为7， 再构造哈夫曼树，由此得到的哈夫曼编码一定满足最短且又互相区分的性质。,c s e a t2 3 5 7 7 8,6.5.3 哈夫曼编码算法的实现,由于哈夫曼树中没有度为1的结点，则一棵有n个叶子的哈夫曼树共有2n-1个结点，可以用一个大小为2n-1 的一维数组存放哈夫曼树的各个结点。 由于每个结点同时还包含其双亲信息和孩子结点的信息，所以构成一个静态三叉链表。静态三

10、叉链表描述如下：,typedef struct unsigned int weight ; /* 用来存放各个结点的权值*/ unsigned int parent, LChild, RChild ; /*指向双亲、 孩子结点的指针*/HTNode, * HuffmanTree; /*动态分配数组， 存储哈夫曼树*/typedef char * *HuffmanCode ; /*动态分配数组， 存储哈夫曼编码*/,HuffmanTree CrtHuffmanTree(HuffmanTree *ht , *HuffmanCode , *hc, int * w, int n)/*w存放n个权值,

11、构造哈夫曼树ht, 并求出哈夫曼编码hc */HuffmanTree ht; m=2*n-1; ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /*0号单元未使用*/for(i=1; i=n; i+) hti = wi, 0, 0, 0; /*叶子结点初始化*/for(i=n+1; i=m; i+) hti =0, 0, 0, 0; /*非叶子结点初始化*/,for(i=n+1; i=m; i+) /*创建非叶子结点, 建哈夫曼树*/ /*在ht1hti-1的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、 s2返回*/ s

12、elect(ht, i-1, s1, s2); hts1.parent=i; hts2.parent=i; hti.LChild=s1; hti.RChild=s2; hti.weight=hts1.weight+hts2.weight; /*哈夫曼树建立完毕*/,/*从叶子结点到根， 逆向求每个叶子结点对应的哈夫曼编码*/hcode=(HuffmanCode)malloc(n+1)*sizeof(char *); /*分配n个编码的头指针*/cd=(char * )malloc(n * sizeof(char ); /*分配求当前编码的工作空间*/cdn-10； /*从右向左逐位存放编码，

13、首先存放编码结束符*/for(i=1; i=n; i+) /*求n个叶子结点对应的哈夫曼编码*/ start=n-1; /*初始化编码起始指针*/ for(c=i, p=hti.parent; p! =0; c=p, p=htp.parent) if(htp.LChild=c) cd-start=0; /*左分支标0*/ else cd-start=1; /*右分支标1*/ hcodei=(char *)malloc(n-start)*sizeof(char); /*为第i个编码分配空间*/ strcpy(hcodei, &cdstart); free(cd); ,数组ht的前n个分量表示叶子结点，最后一个分量表示根结点。 每个叶子结点对应的编码长度不等，但最长不超过n。,图6.41 实习题三用图,图6.42 实习题四用图,