数据结构课件第六章3

1、1第6章 树和二叉树（Tree & Binary Tree）6.1 树的基本概念树的基本概念6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.5 赫夫曼树及其应用赫夫曼树及其应用二叉树的运算二叉树的运算26.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树遍历二叉树遍历遍历指按某条搜索路线遍访每个结点且不重复。指按某条搜索路线遍访每个结点且不重复。常用的有常用的有先序、中序和后序遍历先序、中序和后序遍历，还有，还有层次层次遍历。遍历。Traversing Binary Tree6.3.2 线索二叉树线索二叉树用二叉链表法存储包含用二叉链

2、表法存储包含n n个结点的二叉树，结点的指针区域中个结点的二叉树，结点的指针区域中会有会有n+1n+1个空指针。个空指针。可以用它来可以用它来存放当前结点的直接前驱和后继存放当前结点的直接前驱和后继等线索，以加快查等线索，以加快查找速度。找速度。Threaded Binary Tree3例：【 2000年计算机系考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 2825405560330854解解: :因为中序遍历序列是：因为中序遍历序列是：5555 40 25 60 40 25 60 2828 08 33 08 33 5454对应线索树应当按此规律连线，即对应线索树应当按此规律

3、连线，即在原二叉树中添加虚线。在原二叉树中添加虚线。NILNILNILNILNILNIL和和NULLNULL的值都是的值都是0,0,区别何在？区别何在？ 在在DelphiDelphi中中NILNIL用来标用来标记空指针记空指针，NullNull用来表用来表示空的示空的VariantVariant型变量型变量或是或是ASCIIASCII码为码为0 0的字符，的字符，比如用于标记字符串结比如用于标记字符串结束。束。在在C/C+C/C+中定义的宏中定义的宏NULLNULL不加区别的包括了不加区别的包括了以上两种含义。以上两种含义。可见可见Object PascalObject Pascal的的语法要

4、比语法要比C/C+C/C+严谨得严谨得多多4线索二叉树的生成（递归算法见教材P134-135）设计技巧：设计技巧：依某种顺序依某种顺序遍历二叉树，对每个结点遍历二叉树，对每个结点p，判断其左指，判断其左指针是否为空，以及其针是否为空，以及其前驱结点的前驱结点的右指针是否为空。右指针是否为空。每次只修改每次只修改前驱结点的右指针前驱结点的右指针（后继）和（后继）和本结点的左指针本结点的左指针（前（前驱）驱），参见算法，参见算法6.6。线索二叉树的遍历线索二叉树的遍历（无需堆栈）（无需堆栈）难点：难点：在线索化二叉树中，并不是每个结点都能在线索化二叉树中，并不是每个结点都能直接找到其后继的，直接找

5、到其后继的，当标志为当标志为0 0时，则需要通过一时，则需要通过一定运算才能找到它的后继。定运算才能找到它的后继。56.4 6.4 树和森林树和森林6.4.1 树和森林与二叉树的转换树和森林与二叉树的转换6.4.2 树和森林的存储方式树和森林的存储方式6.4.3 树和森林的遍历树和森林的遍历66.4.1 树和森林与二叉树的转换转换步骤：step1: 将树中同一结点的兄弟相连;加线加线抹线抹线旋转旋转讨论讨论1 1：树如何转为二叉树？：树如何转为二叉树？孩子孩子兄弟兄弟表示法表示法step2: step2: 保留结点的最左孩子连线，保留结点的最左孩子连线，删除其它孩子连线；删除其它孩子连线；st

6、ep3: step3: 将同一孩子的连线绕左孩子将同一孩子的连线绕左孩子旋转旋转4545度角。度角。7方法：方法：加加线线抹线抹线旋转旋转 abeidfhgc树转二叉树举例：abeidfhgc兄弟相连兄弟相连长兄为父长兄为父孩子靠左孩子靠左8讨论2：二叉树怎样还原为树？abeidfhgc要点：要点：逆操作，把逆操作，把所有右孩子变为兄弟所有右孩子变为兄弟！ abdefhgic9法一： 各森林先各自转为二叉树； 依次连到前一个二叉树的右子树上。讨论讨论3 3：森林如何转为二叉树？：森林如何转为二叉树？即即F=TF=T1 1, T, T2 2, , ,T,Tm m B=root, LB, RB B

7、=root, LB, RB法二：法二：森林直接变兄弟，再转为二叉树森林直接变兄弟，再转为二叉树（参见教材（参见教材P138P138图图6.176.17，两种方法都有转换示意图），两种方法都有转换示意图）法一和法二得到的二叉树是完法一和法二得到的二叉树是完全相同的、惟一的。全相同的、惟一的。10ABCDEFGHJIABCDEFGHJIBCDEFGHJI森林转二叉树举例：（用法二，森林直接变兄弟，再转为二叉树）兄弟相连兄弟相连 长兄为父长兄为父头树为根头树为根 孩子靠左孩子靠左11BCDEFGHJI讨论4：二叉树如何还原为森林？要点：要点：把最右边的子树变为森林，其余右子树变为兄弟把最右边的子树变

8、为森林，其余右子树变为兄弟 即即B=root, LB, RB F=TB=root, LB, RB F=T1 1, T, T2 2, , ,T,Tm m ABCDEFGHJIEFABCDGHJI126.4.2 树和森林的存储方式树有三种常用存储方式：树有三种常用存储方式：双亲表示法双亲表示法 孩子表示法孩子表示法 孩子孩子兄弟表示法兄弟表示法 nextsiblingdatafirstchild指向左孩子指向左孩子指向右兄弟指向右兄弟问：问：树树二叉树的二叉树的“连线连线抹线抹线旋转旋转” ” 如何由计算机自动实如何由计算机自动实现？现？答：答：用用“左孩子右兄弟左孩子右兄弟”表示法来存储即可。表

9、示法来存储即可。 13abecdfhgbacedfgh例如：146.4.3 树和森林的遍历例如：例如：abdec先根序列：先根序列：后根序列：后根序列：a b c d eb d c e a深度优先遍历深度优先遍历（先根、后根）（先根、后根）广度优先遍历广度优先遍历（层次）（层次）先根遍历访问根结点；依次先根遍历根结点的每棵子树。后根遍历后根遍历 依次后根遍历根结点的每依次后根遍历根结点的每棵子树；棵子树； 访问根结点。访问根结点。树没有中序遍历（因树没有中序遍历（因子树不分左右）子树不分左右）15讨论：树若采用讨论：树若采用“先转换，后遍历先转换，后遍历”方式，结果是否一样？方式，结果是否一样

10、？abdec先序遍历：先序遍历：后序遍历：后序遍历：中序遍历：中序遍历：d e c b aabdeca b c d eb d c e a1. 树的先根遍历与二叉树的树的先根遍历与二叉树的先序先序遍历相同；遍历相同； 2. 树的树的后根后根遍历相当于二叉树的遍历相当于二叉树的中序中序遍历；遍历；3. 树没有中序遍历，因为子树无左右之分。树没有中序遍历，因为子树无左右之分。结论：结论：树的先根序列：树的先根序列：a b c d e树的后根序列：树的后根序列：b d c e a16先根遍历 若森林为空，返回； 访问森林中第一棵树的根结点； 先根遍历第一棵树的根结点的子树森林； 先根遍历除去第一棵树之

11、后剩余的树构成的森林。森林的遍历ABCDEFGHJI为何有中为何有中序？序？深度优先遍历深度优先遍历（先根、中根、（先根、中根、后根后根）广度优先遍历广度优先遍历（层次）（层次）中根遍历中根遍历若森林为空，返回；若森林为空，返回；中根遍历森林中第一棵树的根结点的子树森林；中根遍历森林中第一棵树的根结点的子树森林；访问第一棵树的根结点；访问第一棵树的根结点；中根遍历除去第一棵树之后剩余的树构成的森林。中根遍历除去第一棵树之后剩余的树构成的森林。17讨论：讨论：若采用若采用“先转换，后遍历先转换，后遍历”方式，结果是否相同？方式，结果是否相同？例如：例如：先根序列：先根序列：中根序列：中根序列：A

12、 B C D E F G H I JB C 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结论：结论：森林的先根和中根遍历在森林的先根和中根遍历在两种方式下的结果相同。两种方式下的结果相同。但森林的后根遍历则不一定，因而少用但森林的后根遍历则不一定，因而少用18 算法思路：算法思路：既然要求从上到下，从左到右，则既然要求从上到下，从左到右，则存放各子存放各子树结点的指针是个好办法，此时树结点的指针是个好办法，此时绝不能用递归绝不能用递归算法。算法。技巧：技巧：当根结点入队后，令其左、右孩子结点入

13、队，而左孩子出当根结点入队后，令其左、右孩子结点入队，而左孩子出队时又令它的左右孩子结点入队，队时又令它的左右孩子结点入队，由此便可产生按层次输出由此便可产生按层次输出的效果。的效果。 算法思路：算法思路：只查各结点后继链表指针，若左只查各结点后继链表指针，若左( (右右) )孩子的左孩子的左( (右右) )指针非空，则层次数加指针非空，则层次数加1 1；否则函数返回。；否则函数返回。 A B CD E19算法思路：算法思路：若不用递归，则要实现二叉树遍历的若不用递归，则要实现二叉树遍历的“嵌套嵌套”规规则，必用堆栈则，必用堆栈 。可直接用。可直接用whilewhile语句和语句和push/p

14、oppush/pop操作。操作。参见教材参见教材P130-131P130-131程序。程序。算法思路：算法思路：完全二叉树的特点是：没有左子树空而右子树单独完全二叉树的特点是：没有左子树空而右子树单独存在的情况存在的情况( (前前k-1k-1层都是满的，且第层都是满的，且第k k层左边也满）层左边也满）。技巧技巧: :按按层次遍历层次遍历方式，先把方式，先把所有所有结点（不管当前结点是否有左结点（不管当前结点是否有左右孩子）右孩子）都入队列都入队列. .若为完全二叉树若为完全二叉树, ,则层次遍历时得到的肯定则层次遍历时得到的肯定是一个连续的不包含空指针的序列是一个连续的不包含空指针的序列.

15、.如果序列中出现了空指针，如果序列中出现了空指针，则说明不是完全二叉树。则说明不是完全二叉树。20Void ABC(Bitree p, int l, int &h) if pNIL then l=l+1; if lh then h=l; ABC(p-Lchild, l, h); ABC(p-Rchild, l, h); 法法1 1：从根开始向下计算层次：从根开始向下计算层次( (比从叶子往上计算更简单比从叶子往上计算更简单) )l、h分别表示二叉树的层次分别表示二叉树的层次数和深度。数和深度。想一想，想一想，l和和h的初始值应设的初始值应设为多少？为多少？开始调用时，应当用开始调用时，

16、应当用ABC（p, 0, 0）若去掉若去掉h形参中的形参中的“&”号，则号，则h不不变化，算出的更深层数不能正确变化，算出的更深层数不能正确返回返回, h将永远为将永远为 0。21int BTreeDepth(Btree *BT) /*BT为二叉树某结点的指针为二叉树某结点的指针 int leftdep, rightdep; /设左右两个深度设左右两个深度/层次计数器层次计数器if(BT=NULL) return(0); /当前结点指针为空则立即返回当前结点指针为空则立即返回else leftdep= BTreeDepth(BT-left); /遍历当前结点左子树遍历当前结点左子树 r

17、ightdep=BTreeDepth(BT-right); /遍历当前结点右子树遍历当前结点右子树 if( leftdeprightdep)return(leftdep+1); /从叶子起计数从叶子起计数 else return(rightdep+1); /BTreeDepth法法2 2：递归时从叶子开始向上计数，层深者保留。：递归时从叶子开始向上计数，层深者保留。22void LayerOrder(Bitree T) /层序遍历二叉树 InitQueue(Q); /建一个空队（初始化队列） EnQueue(Q,T); /将一个结点插入队尾的函数 while( !QueueEmpty(Q) )

18、 DeQueue(Q, &p); /队首结点出队(送入p) visit(p); if(p-lchild) EnQueue(Q,p-lchild); /p的左孩子入队 if(p-rchild) EnQueue(Q,p-rchild); /p的右孩子入队 /LayerOrder 当孩子为空时不要当孩子为空时不要将空指针入队将空指针入队23intint IsFull_BitreeIsFull_Bitree(Bitree(Bitree T) T)/是完全二叉树返回是完全二叉树返回1 1, ,否则返否则返0 0 InitQueue(Q InitQueue(Q); ); /建队（初始化队列）建队（初始化队列） flag=flag=0 0; ; /标志初始化标志初始化 EnQueue(Q,TEnQueue(Q,T); ); /结点结点T T入队（入队（空指针也要入队空指针也要入队） whilewhile(!QueueEmpty(Q(!QueueEmpty(Q) ) DeQueue(Q,&pDeQueue(Q,&p); ); /队首结点出队队首结点出队( (送入送入p)p) if(!p) if(!p) flag=1flag=1; ; /队首结点为空则标志变，但也许是队尾队首结点为