ch62遍历二叉树和线索二叉树

1、1第第6 6章章 树和二叉树树和二叉树（Tree & Binary TreeTree & Binary Tree）6.1 树的基本概念树的基本概念6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.5 赫夫曼树及其应用赫夫曼树及其应用二叉树的运算二叉树的运算26.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树一、一、 遍历二叉树遍历二叉树遍历定义：遍历定义：遍历用途：遍历用途：遍历方法：遍历方法：指按某条搜索路线遍访每个结点且指按某条搜索路线遍访每个结点且不重复（又称周游）。不重复（又称周游）。它是树结构插入、删除、修改、查找它是树结构

2、插入、删除、修改、查找和排序运算的前提，是二叉树一切运和排序运算的前提，是二叉树一切运算的基础和核心。算的基础和核心。对每个结点的查看通常都是对每个结点的查看通常都是“先左先左后右后右”。Traversing Binary Tree广度优先和深度优先广度优先和深度优先3遍历规则：遍历规则：v 二叉树由根、左子树、右子树构成，定义为二叉树由根、左子树、右子树构成，定义为D、 L、R注：注：“先、中、后先、中、后”的意思是指的意思是指访问的根结点访问的根结点D D是先于子树出现是先于子树出现还是后于子树出现。还是后于子树出现。v D、 L、R的组合定义了六种可能的遍历方案：的组合定义了六种可能的遍

3、历方案：DLR, LDR, LRD, DRL, RDL, RLDv 若限定若限定先左后右先左后右，则有三种实现方案：，则有三种实现方案： DLR LDR LRD先先序遍历序遍历 中中序遍历序遍历 后后序遍历序遍历 4例例1 1：先序遍历的结果是：先序遍历的结果是：中序遍历的结果是：中序遍历的结果是：后序遍历的结果是：后序遍历的结果是： A B CD E口诀：口诀：DLR先序遍历，即先根再左、右先序遍历，即先根再左、右LDR中序遍历，即先左再根后右中序遍历，即先左再根后右LRD后序遍历，即先左、右再根后序遍历，即先左、右再根层次遍历：层次遍历：ABCDE5+*A*/EDCB先序遍历结果：先序遍历

4、结果：+ * * / A B C D E前缀表示法前缀表示法中序遍历结果：中序遍历结果：A / B * C * D + E后序遍历结果：后序遍历结果：A B / C * D * E +后缀表示法后缀表示法例例2 2：用二叉树表示算术表达式用二叉树表示算术表达式层次遍历结果：层次遍历结果：+*E*D/CAB6abadefgff n个结点个结点. . . . . 例例3 3：画出所有中序遍历序列和后序遍历序列一致的：画出所有中序遍历序列和后序遍历序列一致的 二叉树的所有形态二叉树的所有形态. .分析：中序遍历分析：中序遍历: LDR-LD: LDR-LD 后序遍历后序遍历: LRD-LD . :

5、LRD-LD . 结论：如果中序和后序结论：如果中序和后序（前序）遍历一致，（前序）遍历一致，则二叉树没则二叉树没有右（左）子树有右（左）子树7由此可以看出：由此可以看出：（1 1）遍历操作实际上是将非线性结构线性化的过程，）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列；其结果为线性序列；（2 2）遍历操作是一个递归的过程，因此，这三种遍历）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。操作的算法可以用递归函数实现。 DLR ( BiTree T ) if (T) /非空二叉树非空二叉树 printf(“%d”,T-data); /访问根结点访问根结点D

6、 D DLR(T-lchild); /递归遍历左子树递归遍历左子树 DLR(T-rchild); /递归遍历右子树递归遍历右子树 return(0); 8 LDR(BiTree T) if(T) LDR(T-lchild); printf(“%d”,T-data); LDR(T-rchild); return(0); （1） 从前面的三种遍历算法可以知道：如果将从前面的三种遍历算法可以知道：如果将printf语句抹去，从递归的角度看，这三种算法是完全相同语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的的，或者说这三种遍历算法的访问路径是相同的，只访问路径是相同的，只是访

7、问结点的时机不同是访问结点的时机不同。对遍历的分析：对遍历的分析：LRD (BiTree T) if(T) LRD(T-lchild); LRD(T-rchild); printf(“%d”,T-data); return(0);DLR输出序列：输出序列：LDR输出序列：输出序列：LRD输出序列：输出序列：例例4 写出该树三种遍历的输出序列：写出该树三种遍历的输出序列：A B D E G HI J C FD B G EI H J A C FD G I JH E B F C A10分析：分析：由先序遍历特征，根结点必在先序序列头部；由先序遍历特征，根结点必在先序序列头部；由中序遍历特征，根结点必

8、在其中间，而且其左部由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树的子孙，其右部必全部是右子树的子必全部是左子树的子孙，其右部必全部是右子树的子孙；孙；例：仅知二叉树的先序序列例：仅知二叉树的先序序列“abcdefg” abcdefg” 不能唯不能唯一确定一棵二叉树，如果同时已知二叉树的中序一确定一棵二叉树，如果同时已知二叉树的中序序列序列“cbdaegf”,cbdaegf”,则会如何？则会如何？11a b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列先序序列中序序列中序序列12已知中序遍历：已知中序遍历：B D C

9、 E A F H G已知后序遍历：已知后序遍历：D E C B H G F A（B D C E）（ F H G）A （D C E）BFGHCD EABBACCD C E例例5：试画出该树。试画出该树。13从虚线的出发点到终点的路从虚线的出发点到终点的路径径上，每个结点经过上，每个结点经过3 3次次。AFEDCBG第第1 1次次经过时访问，是经过时访问，是先序先序遍历遍历第第2 2次次经过时访问，是经过时访问，是中序中序遍历遍历第第3 3次次经过时访问，是经过时访问，是后序后序遍历遍历 任何一棵二叉树都可以将它的外部轮廓用一条线任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉

10、树的包线。如图：绘制出来，我们将它称为二叉树的包线。如图：14（2 2） 二叉树遍历的时间效率和空间效率二叉树遍历的时间效率和空间效率 时间效率时间效率: : /每个结点只访问一次每个结点只访问一次 空间效率空间效率: : /栈占用的最大辅助空间栈占用的最大辅助空间精确值：树深为精确值：树深为k k的递归遍历需要的递归遍历需要k+1k+1个辅助单元个辅助单元递归遍历算法的应用举例递归遍历算法的应用举例2 2、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数3 3、求二叉树的深度、求二叉树的深度1 1、建立二叉树的二叉链表、建立二叉树的二叉链表15例例1 1：建立二叉树的二叉链表。即：如何

11、把二叉树存入建立二叉树的二叉链表。即：如何把二叉树存入 电脑内？电脑内？怎样建树怎样建树？（教材（教材P131P131算法算法6.46.4）考虑考虑2 2：输入结点时怎样表示：输入结点时怎样表示“无孩子无孩子”？ 用空格字符表示用空格字符表示无孩子无孩子或指针为空或指针为空考虑考虑1 1：以何种遍历方式来输入和建树？：以何种遍历方式来输入和建树？ 采用完全先序遍历，以字符串的形式输入。采用完全先序遍历，以字符串的形式输入。例：将左图所示二叉树按完全先序例：将左图所示二叉树按完全先序遍历次序输入：遍历次序输入：A B C D E G F (/n)16Status CreateBiTree(BiT

12、ree &T) scanf( “c%”, &ch); if (ch= ) T = NULL; else if ( !(T = new BiTNode) exit(OVERFLOW); T-data = ch; / 生成根结点 CreateBiTree(T-lchild); / 构造左子树 CreateBiTree(T-rchild); / 构造右子树 return OK; / CreateBiTree17例例2 2：【严题集严题集6.426.42】编写递归算法，计算二叉树中编写递归算法，计算二叉树中叶子结点的数目。叶子结点的数目。 思路：思路：这个操作可以使用三种遍历顺序中的任何一种，这个操作

13、可以使用三种遍历顺序中的任何一种，只是需要只是需要将访问操作变成判断该结点是否为叶子结点将访问操作变成判断该结点是否为叶子结点，如果是叶子结点将计数器如果是叶子结点将计数器countcount加加1 1即可。下面这个算法即可。下面这个算法是利用先序遍历实现的。是利用先序遍历实现的。void CountLeaf (BiTree T, int &count) if ( T ) if (!T-lchild)& (!T-rchild) count+; / / 对叶子结点计数对叶子结点计数 CountLeaf( T-lchild, count); CountLeaf( T-rchild, count);

14、 /if / CountLeaf18例例3 3：求二叉树的深度求二叉树的深度 思路：思路：二叉树的深度应为其左、右子树深度的最大值二叉树的深度应为其左、右子树深度的最大值加加1 1。由此，需先分别求得左、右子树的深度，由此，需先分别求得左、右子树的深度，算法中算法中“访问结点访问结点”的操作为的操作为: :求得左、右子树深度的最大值，求得左、右子树深度的最大值，然后加然后加 1 1 。相当于采用后序遍历。相当于采用后序遍历。int Depth (BiTree T ) if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); dept

15、hRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight)? depthLeft : depthRight; return depthval; 19 算法思路：算法思路：既然要求从上到下，从左到右，则既然要求从上到下，从左到右，则存放各子树结点的指针是个好办法，此时存放各子树结点的指针是个好办法，此时绝不能用绝不能用递归递归算法。算法。技巧：技巧：当根结点入队后，令其左、右孩子结点入队，而当根结点入队后，令其左、右孩子结点入队，而左孩子出队时又令它的左右孩子结点入队，左孩子出队时又令它的左右孩子结点入队，由此便由此便可产生按

16、层次输出的效果。可产生按层次输出的效果。ABFGHCD EA队头队头队尾队尾（1）A入队，入队，A为队首元素，故为队首元素，故A出队；出队； “出对出对”的意思就是该元素被访问。的意思就是该元素被访问。 A出队后，马上将出队后，马上将A的左右孩子的左右孩子BF都入队；都入队；BF(2)队首元素为队首元素为B，将它出队（访问）；，将它出队（访问）；B出对后，马上将出对后，马上将B的左右孩子的左右孩子C入队；入队；（3）队首元素为）队首元素为F，将它出队；，将它出队；F出队后，出队后，马上将马上将F的左右孩子的左右孩子G入队；依次类推。入队；依次类推。c出队顺序为：出队顺序为：A B F C G

17、D E HGD E21void void LayerOrderLayerOrder(Bitree T) (Bitree T) /层次遍历二叉树层次遍历二叉树 InitQueue(Q); InitQueue(Q); /建一个空队（初始化队列）建一个空队（初始化队列） EnQueue(Q,T); EnQueue(Q,T); /根结点入队根结点入队 while(while( !QueueEmpty(Q)!QueueEmpty(Q) ) ) DeQueue(Q, &p);DeQueue(Q, &p); /队首结点出队队首结点出队( (送入送入p)p) visit(p); visit(p); if(p-

18、lchild) if(p-lchild) EnQueue(Q,p-lchild);EnQueue(Q,p-lchild); /左孩子入队左孩子入队 if(p-rchild) if(p-rchild) EnQueue(Q,p-rchild);EnQueue(Q,p-rchild);/右孩子入队右孩子入队 /LayerOrder /LayerOrder 当孩子为空时不要当孩子为空时不要将空指针入队将空指针入队22算法思路：算法思路：完全二叉树的特点是：完全二叉树的特点是：没有左子树空而右没有左子树空而右子树单独存在的情况子树单独存在的情况( (前前k-1k-1层都是满的，且第层都是满的，且第k k

19、层左边层左边也满）。也满）。技巧技巧: :按按层次遍历层次遍历方式，先把所有结点（不管当前结点方式，先把所有结点（不管当前结点是否有左右孩子）是否有左右孩子）都入队列都入队列. .若为完全二叉树若为完全二叉树, ,则层次则层次遍历时得到的肯定是一个连续的不包含空指针的序列遍历时得到的肯定是一个连续的不包含空指针的序列. .如果序列中出现了空指针，则说明不是完全二叉树。如果序列中出现了空指针，则说明不是完全二叉树。int IsFull_Bitree(BiTree T /是完全二叉树返回1,否则返0 InitQueue(Q); /建队（初始化队列） flag=0; /标志初始化 23EnQueue

20、(Q,T); /根结点入队（空指针也要入队） while(!QueueEmpty(Q) while(!QueueEmpty(Q) /直到队列空为止 DeQueue(Q,p);DeQueue(Q,p); /队首结点出队(送入p) if(!p) flag=1;if(!p) flag=1; /队首结点为空则标志变 else if (flag) return 0;else if (flag) return 0; /无左孩子有右孩子 elseelse EnQueue(Q,p-lchild);EnQueue(Q,p-lchild); /左孩子入队列 EnQueue(Q,p-rchild);EnQueue(

21、Q,p-rchild); /右孩子入队列 /while/while return 1; return 1; /执行至此必为队空且中间无空指针，完全二叉树/IsFull_Bitree /IsFull_Bitree 例六：例六：复制二叉树复制二叉树其基本操作为其基本操作为:生成一个结点。生成一个结点。BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = new BiTNode) exit(1); T- data = item; T- lchild = lptr; T- rchild = rptr

22、; return T; 生成一个二叉树的结点生成一个二叉树的结点:(其数据域为其数据域为item,左指针域为左指针域为lptr,右指针域为右指针域为rptr)BiTNode *CopyTree(BiTNode *T) if (!T ) return NULL; if (T-lchild ) newlptr = CopyTree(T-lchild);/复制左子树 else newlptr = NULL; if (T-rchild ) newrptr = CopyTree(T-rchild);/复制右子树 else newrptr = NULL; newT = GetTreeNode(T-data

23、, newlptr, newrptr); return newT; / CopyTreeABCDEFGHK D C B H K G F E A例如例如: :下列二叉树下列二叉树的复制过程如下的复制过程如下: :newT27二、 线索二叉树线索二叉树（ Threaded Binary Tree ）所以，所以， 空指针数目空指针数目2n(n-1)=n+1个。个。证明：证明：用二叉链表存储包含用二叉链表存储包含n n个结点的二叉树，结点个结点的二叉树，结点必有必有2n个链域。除根结点外，二叉树中每一个链域。除根结点外，二叉树中每一个结点个结点有且仅有一个双亲有且仅有一个双亲，意即每个结点地，意即每个

24、结点地址占用了双亲的一个链域，址占用了双亲的一个链域，n n个结点地址共占个结点地址共占用了用了n-1n-1个指针域个指针域。也就是说，只会有。也就是说，只会有n n1 1个个链域存放指针。链域存放指针。讨论讨论1 1：用二叉链表法（用二叉链表法（l_child, r_childl_child, r_child）存储）存储 包含包含n n个结点的二叉树，结点的指针区域中个结点的二叉树，结点的指针区域中 会有多少个会有多少个空空指针？指针？28结论：结论：用二叉链表存储包含用二叉链表存储包含n n个结点的二叉树，结点个结点的二叉树，结点的指针区域中会有的指针区域中会有n+1n+1个空指针。个空指

25、针。讨论讨论2 2：二叉树是非线性结构，如何定义其直接后继？二叉树是非线性结构，如何定义其直接后继？ 对二叉树进行某种遍历之后，将得到一个线性对二叉树进行某种遍历之后，将得到一个线性 有序的序列。有序的序列。 例如对某二叉树的例如对某二叉树的中序遍历中序遍历结果是结果是B D C E A B D C E A F H GF H G，意味着已将该树转为线性排列，显然其中结，意味着已将该树转为线性排列，显然其中结点点具有唯一前驱和唯一后继具有唯一前驱和唯一后继。 讨论讨论3 3：如何获得这种如何获得这种“直接前驱直接前驱”或或“直接后继直接后继”？有何意义？有何意义？29这就是这就是（Threade

26、d Binary Tree）二叉树中容易找到结点的二叉树中容易找到结点的左右孩子左右孩子信息，但该结信息，但该结点的直接前驱和直接后继只能在某种遍历过程中点的直接前驱和直接后继只能在某种遍历过程中动态动态获得。获得。先依先依遍历规则遍历规则把每个结点对应的把每个结点对应的前驱前驱和和后继线索后继线索预存起来，这叫做预存起来，这叫做“线索化线索化”。意义：意义：从从任一结点任一结点出发都能快速找到其前驱和后出发都能快速找到其前驱和后继，且继，且不必借助堆栈。不必借助堆栈。30 每个结点增加两个域：每个结点增加两个域：fwd和和bwd；如何预存这类信息？有两种解决方法：如何预存这类信息？有两种解决

27、方法： 与原有的左右孩子指针域与原有的左右孩子指针域“复用复用”，充分利用那，充分利用那n+1n+1个空链域。个空链域。规规 定：定：1 1）若结点有左子树，则）若结点有左子树，则lchildlchild指向其左指向其左孩子；否则，孩子；否则，lchildlchild指向其直接前驱指向其直接前驱( (即即线索线索) )；2 2）若结点有右子树，则）若结点有右子树，则rchildrchild指向其右指向其右孩子；否则，孩子；否则，rchildrchild指向其直接后继指向其直接后继( (即线索即线索) ) 。datalchildrchildfwdbwddatalchildrchild缺点：空间效

28、缺点：空间效率太低！率太低！如何判断是孩如何判断是孩子指针还是线子指针还是线索指针？索指针？如何区如何区别？别？31lchild LTagdataRTagrchild约定约定: 当当Tag域为域为0时时,表示孩子情况表示孩子情况;当当Tag域为域为1时时,表示表示线索线索情况情况.前驱前驱(后继后继)左左(右右)孩子孩子为区别两种不同情况，特增加两个标志域：为区别两种不同情况，特增加两个标志域：问：问：增加了前驱和后继等线索有什么好处？增加了前驱和后继等线索有什么好处？能方便找出当前结点的前驱和后继，不用能方便找出当前结点的前驱和后继，不用堆栈（递归）也能遍历整棵树。堆栈（递归）也能遍历整棵树

29、。各各1bit1bit321. 1. 有关线索二叉树的几个术语：有关线索二叉树的几个术语：线索链表：线索链表：线线 索：索：线索二叉树：线索二叉树：线线 索索 化：化：用用含含TagTag的结点样式所构成的二叉链表。的结点样式所构成的二叉链表。指向结点前驱和后继的指针。指向结点前驱和后继的指针。加上线索的二叉树。加上线索的二叉树。对二叉树以对二叉树以某种次序遍历某种次序遍历使其变为线索二使其变为线索二叉树的过程。叉树的过程。线索化过程线索化过程就是在遍历过程中修改空指针的过程：就是在遍历过程中修改空指针的过程： 将空的将空的lchildlchild改为结点的直接前驱；改为结点的直接前驱； 将空

30、的将空的rchildrchild改为结点的直接后继。改为结点的直接后继。 非空指针呢？仍然指向孩子结点（称为非空指针呢？仍然指向孩子结点（称为“正常情况正常情况”）33dataAGEIDJHCFBLtag0011110101Rtag0001010111AGEIDJHCFB例例1：带了两个标志的某：带了两个标志的某先序遍历结果先序遍历结果如下表所示，如下表所示，请画出对应的二叉树。请画出对应的二叉树。ATag=1表示线索表示线索:Ltag=1表示前驱表示前驱Rtag=1表示后继表示后继34ABCGEIDHFroot悬空？悬空？ NILNIL悬空？悬空？ NILNIL解：对该二叉树解：对该二叉树中

31、序中序遍历的结果为遍历的结果为: : H, D, I, B, E, H, D, I, B, E, A, F, C, G A, F, C, G 所以添加线索应当按如下路径进行：所以添加线索应当按如下路径进行：为避免悬空为避免悬空态，应增设态，应增设一个头结点一个头结点例例2 2：画出以下二叉树对应的：画出以下二叉树对应的中序中序线索二叉树。线索二叉树。2. 2. 线索二叉树的生成线索二叉树的生成线索化（线索二叉树的重点）线索化（线索二叉树的重点）3500A00C00B11E11F11G00D11I11H注：此图中序遍历结果为注：此图中序遍历结果为: : H, D, I, B, E, A, F,

32、C, G对应的中序线索二叉树存储结构如图所示：对应的中序线索二叉树存储结构如图所示：root36例例3 3：已知一棵二叉树的中序序列为：已知一棵二叉树的中序序列为cbedahgijf,cbedahgijf,后序序后序序列为列为cedbhjigfa,cedbhjigfa,画出该二叉树的先序线索二叉树。画出该二叉树的先序线索二叉树。线索二叉树的生成算法（递归算法见教材线索二叉树的生成算法（递归算法见教材P134-135，自，自学学）目的：目的：在遍历二叉树的过程中修改空指针，添加前在遍历二叉树的过程中修改空指针，添加前驱或后继的线索，使之成为线索二叉树。驱或后继的线索，使之成为线索二叉树。 为了记

33、下遍历过程中访问结点的先后次序，需要为了记下遍历过程中访问结点的先后次序，需要设置两个指针：设置两个指针： p p指针指针当前结点之指针；当前结点之指针； prepre指针指针当前结点的前趋结点指针。当前结点的前趋结点指针。37设计技巧：设计技巧：依某种顺序遍历二叉树，对每个结点依某种顺序遍历二叉树，对每个结点p，判，判断其左指针是否为空，以及其断其左指针是否为空，以及其前驱结点的前驱结点的右右指针是否为空。指针是否为空。每次只修改每次只修改前驱结点的右指针前驱结点的右指针（后继）和（后继）和本结点的左本结点的左指针指针（前驱）（前驱），参见，参见P135算法算法6.7。若若p-lchildN

34、ULL,则则 p-LTag=1; p-lchildpre; /p的前驱线索应存的前驱线索应存p结点的左边结点的左边若若pre-rchildNULL, 则则 pre-RTag1; pre-rchild=p; /pre的后继线索应存的后继线索应存pre结点的右边结点的右边38难点：难点：在线索化二叉树中，并不是每个结点都能在线索化二叉树中，并不是每个结点都能直接找到其后继的，直接找到其后继的，当标志为当标志为0 0时，则需要通过一时，则需要通过一定运算才能找到它的后继。定运算才能找到它的后继。以以中序线索二叉树中序线索二叉树为例：为例：当当RTag=1时，直接后继指针就在其时，直接后继指针就在其rchild域内；域内