树与森林的遍历

《树与森林的遍历》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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.二叉树的层次遍历算法（二叉链表存储）；2.求二叉树中最大结点值（二

3、叉链表存储）。哈夫曼树及其应用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，3，4，…结点数nn=1n=2n=3n=4n=5n=6n

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

5、第i个叶子结点的权值，li为第i个叶子结点的路径长度。例如，图6.26中三棵二叉树的带权路径长度分别为：WPL(a)=7×2＋5×2＋2×2＋4×2＝36WPL(b)=4×2＋7×3＋5×3＋2×1＝46WPL(c)=7×1＋5×2＋2×3＋4×3＝35问题2:什么样的树的带权路径长度最小？例如：给定一个权值序列{2,3,4,7}，可构造如图6.29所示的多种二叉树的形态。4.哈夫曼树构造哈夫曼算法的步骤如下：（1）用给定的n个权值{w1,w2,…,wn}对应的n个结点构成n棵二叉树的森林F={T1,T2,…,Tn}，其中每一棵二叉树Ti(1≤i≤n)都只有一个权

6、值为wi的根结点，其左、右子树为空。（2）在森林F中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、右子树，标记新二叉树的根结点权值为其左右子树的根结点权值之和。（3）从F中删除被选中的那两棵二叉树，同时把新构成的二叉树加入到森林F中。（4）重复（2）、（3）操作，直到森林中只含有一棵二叉树为止，此时得到的这棵二叉树就是哈夫曼树。6.5.2哈夫曼编码表6–1指令的使用频率指令使用频率(Pi）I10.40I20.30I30.15I40.05I50.04I60.03I70.03表6–2指令的变长编码指令使用频率(Pi）I10I21I300I401I5000I6001I7

7、010图6.30构造哈夫曼树示例表6–3指令的哈夫曼编码指令使用频率(Pi）I10I210I3110I411100I511101I611110I711111可以验证，该编码是前缀编码。若一段程序有1000条指令，其中I1大约有400条，I2大约有300条，I3大约有150条，I4大约有50条，I5大约有40条，I6大约有30条，I7大约有30条。对于定长编码，该段程序的总位数大约为3×1000＝3000。采用哈夫曼编码后，该段程序的总位数大约为1×400＋2×300＋3×150＋5×（50＋40＋30＋