数据结构第6章树幻灯片.ppt

3.二叉树BT恢复成森林F（BT?F） 这是F?BT的逆变换。 方法：对BT中任一结点，其Lchild所指结点仍为孩子，而Rchild所指结点为它的右兄弟，即“左孩子，右兄弟”。 如对例6-23中的二叉树BT，恢复成森林F的过程为：A的左子B为A的第一子，A的右子E为A的右兄弟，因A是根，所以E应为另一棵树的根；B的左子为空，故B一定为叶子，而C为B的右兄弟，依次类推。 A B D C F E H I G J D C H J I F G A B E 二叉树BT 森林F 6.5.3树和森林的遍历 树和森林的遍历是二叉树遍历的推广，即按某种规则（或次序）将树或森林中每个结点访问且仅访问一次。 1．先根遍历树T 方法：若T≠∧ ，先访问T的根结点，然后从左至右依次遍历根下的各子树。对各子树的遍历们采用先根遍历方法（递归）。 例6-24 设树T如图6.45所示。对其按先根遍历的过程为：访问根结点A；A有三棵子树，依次按先根遍历。因第一棵子树只有一个结点B，访问之，第二棵子树的根为C，访问C，再遍历C下的D和E；接着再遍历A的第三棵子树，即访问结点F。 A B F D C E 图6.45 先根序列: A B C D E F 树和森林的遍历 2．后根遍历树T 方法：若T≠∧，从左至右遍历根下的各子树，最后访问根结点。对各子树的遍历采用后根遍历算法。 对例6-24中的对T，后根遍历过程为：先遍历根A的第一棵子树，即访问B；然后遍历A的第二棵子树，仍旧采用后根遍历法，访问序列应为（D,E,C）；接着遍历A的第三棵子树，即访问结点F；最后访问总的根结点A。 A B F D C E 图6.45 A 后根序列: B C D E F 树和森林的遍历 3．先序遍历森林F 设F={ T1,T2,………..,Tm }，其中Ti(1≤i≤m)为F中第i棵子树。 方法：若F≠φ，则： （1）访问F中T1之根； （2）先序遍历T1之根下的各子树（子森林）； （3）先序遍历除T1之外的森林（T2,……,Tm）。 显然(2)、(3)为递归调用，即：若子森林存在，仍按先序遍历方法对其遍历。如对例6-23中的森林F，先序遍历结果为：（A,B,C,D,E,F,G,H,I,J）。 此方法等价为：先将F转换二叉树BT，然后对BT按前序（DLR）遍历，其结果是一样的。 D C H J I F G A B E T1 T2 T3 A B D C F E H I G J DLR：A,B,C,D,E,F,G,H,I,J 树和森林的遍历 4．后序遍历森林F 方法：若F≠φ，则： （1）后序遍历F中T1之根下的各子树（子森林）； （2）访问T1之根； （3）后序遍历除T1之外的森林{ T2,……,Tm }。 显然，(1)、(3)递归调用，即：若子森林存在，仍按后序遍历方法对其遍历。如对例6-23中的森林F，后序遍历的结果为：（B,C,D,A,F,E,H,J,I,G）。 此方法等价为：先将F转换成二叉树BT，然后对BT按中序(LDR)遍历。 D C H J I F G A B E T1 T2 T3 A B D C F E H I G J LDR：B,C,D,A,F,E,H,J,I,G 6.6二叉树应用举例 树和二叉树在系统软件和应用软件中应用很多，限于篇幅，我们讨论二叉树的一个典型应用——Huffman(哈夫曼)树及其编码和译码。 6.5.1 Huffman树及其构造算法 Huffman树，简称H树，其含义是加权路径长度最短的二叉树。 1．路径及其长度 当树中从一结点到另一结点存在一条通路时，称两结点间存在一条路径，用路径上的结点序列表示。路径上分支数(或弧的条数)为路径的长度。因为树是无环路的有向图，且除根外，每结点只有唯一的一个直接前驱(双亲)，故从树根结点到其它任何一结点存在且仅存在一条路径。 例6-25设树T如图6.46: 此树中从结点A到D的路径为：（A, B, C, D），路径长度等于3。 A B C D 2．树的路径长度 树的路径长度定义为从根结点到其它每一结点的路径长度之和。对有n个(n0)结点的二叉树来说，完全二叉树的路径长度最短。如一棵完全二叉树BT如图6.47: 其路径长度为:0+1+1+2+2+2+2+3+3=16。 3．加权结点 权是附加给一结点的数值，如 此时称该结点为加权结点。树中加权结点的路径长度定义为从