《二叉树遍历》PPT课件

《《二叉树遍历》PPT课件》由会员分享，可在线阅读，更多相关《《二叉树遍历》PPT课件（48页珍藏版）》请在装配图网上搜索。

1、6.3 二叉树的遍历,一、问题的提出,二、先左后右的遍历算法,三、算法的递归描述,四、中序遍历算法的非递归描述,五、遍历算法的应用举例,顺着某一条搜索路径巡访二叉树 中的结点，使得每个结点均被访问一 次，而且仅被访问一次。,一、问题的提出,“访问”的含义可以很广，如：输出结 点的信息等。,“遍历”是任何类型均有的操作， 对线性结构而言，只有一条搜索路 径(因为每个结点均只有一个后继)， 故不需要另加讨论。而二叉树是非 线性结构，,每个结点有两个后继， 则存在如何遍历即按什么样的搜索 路径遍历的问题。,对“二叉树”而言，可以有三条搜索路径：,1先上后下的按层次遍历； 2先左（子树）后右（子树）的

2、遍历； 3先右（子树）后左（子树）的遍历。,二、先左后右的遍历算法,先（根）序的遍历算法,中（根）序的遍历算法,后（根）序的遍历算法,若二叉树为空树，则空操作；否则， （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。,先（根）序的遍历算法：,若二叉树为空树，则空操作；否则， （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。,中（根）序的遍历算法：,若二叉树为空树，则空操作；否则， （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。,后（根）序的遍历算法：,typedef struct BiTNode / 结点结构 TElemType data

3、; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;,lchild data rchild,结点结构:,二叉树C 语言的类型描述如下:,若二叉树为空树，则空操作；否则， （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。,先（根）序的遍历算法：,三、算法的递归描述,Status Preorder (BiTree T, void( *visit)(TElemType/ 遍历右子树 ,说明,访问函数的示例和preOrder函数调用的方法算法6.1所示. 同理可以实现中序遍历二叉树和后序遍历二叉树. 3种遍历思想一

4、致,不同之处在于访问根结点的时机 先序:访问左子树之前访问根 中序:访问右子树之前访问根 后序:访问右子树之后访问根,A,B,C,D,F,E,H,I,四、用堆栈实现二叉树中序遍历,A,B,C,D,F,E,H,I,A,B,C,D,F,E,H,I,A,A,B,A,B,D,D,B,A,B,A,D,A,B,A,C,C,A,C,A,F,F,E,F,E,I,I,E,F,E,F,I,F,E,F,H,H,H,用堆栈实现二叉树中序遍历的规律,将根结点设置为待入栈结点p 如果p不为空,则p入栈,将p的左孩子设置为待入栈结点 如果p为空,则栈顶元素出栈,访问栈顶元素,然后将栈顶元素的右孩子设置为待入栈结点 直到P为

5、空且栈为空结束 算法见书上6.3,五、遍历算法的应用举例,2、建立二叉树的存储结构,1、求二叉树的深度(后序遍历),1、求二叉树的深度(后序遍历),算法基本思想:,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。,首先分析二叉树的深度和它的左、右子树深度之间的关系。,int Depth (BiTree T ) / 返回二叉树的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRigh

6、t= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval; ,2、建立二叉树的存储结构,不同的定义方法相应有不同的存储结构的建立算法,以字符串的形式 根 左子树 右子树 定义一棵二叉树,例如:,A,B,C,D,以空白字符“ ”表示,A(B( ,C( , ),D( , ),空树,只含一个根结点的二叉树,A,以字符串“A ”表示,以下列字符串表示,A B C D,A,B,C,D,基本的构造过程举例如下：,A,T,B,C,D,Status CreateBi

7、Tree(BiTree / CreateBiTree,仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树，,由二叉树的先序和中序序列建树,如果同时已知二叉树的中序序列“cbdaegf”，则会如何？,二叉树的先序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,a b c d e f g,c b d a e g f,例如:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,思考: 已知中序遍历：B D C E A F H G 已知后序遍历：D E C B H G F A,（B D C E）,A,作业:,1.写出中序遍历

8、二叉树的递归算法 2.写出计算二叉树叶结点个数的递归算法 叶结点满足的条件 3.给定二叉树的两种遍历序列，分别是： 前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树，并写出该二叉树的前序遍历序列和中序遍历序列。,6.5线索二叉树,何谓线索二叉树？ 线索链表的遍历算法 如何建立线索链表？,一、何谓线索二叉树？,遍历二叉树的结果是，求得结点的一个线性序列。,A,B,C,D,E,F,G,H,K,例如:,先序序列: A B C D E F G H K,如何记录树中每个结点在遍历序列中直接前驱和直接后继,因为：用二叉链表法存储包含n个结点

9、的二叉树，结点的指针区域中会有n+1个空指针。 可以利用这些空指针来指示前驱或后继,指向该线性序列中的“前驱”和 “后继” 的指针，称作“线索”,与其相应的二叉树，称作 “线索二叉树”,包含 “线索” 的存储结构，称作 “线索链表”,A B C D E F G H K, D ,C , B,E ,对线索链表中结点的约定：,在二叉链表的结点中增加两个标志域(bit)， ltag(左)和rtag(右)并作如下规定：,若该结点的左子树不空， 则Lchild域的指针指向其左子树， 且设置ltag的值为“0”； 否则，Lchild域的指针指向其“前驱”， 且设置ltag的值为“1” 。,若该结点的右子树不

10、空， 则rchild域的指针指向其右子树， 且设置rtag的值为 “0”； 否则，rchild域的指针指向其“后继”， 且设置rtag的值为“1”。,如此定义的二叉树的存储结构称作“线索链表”。,增加了前驱和后继等线索有什么好处？,能方便找出当前结点的前驱和后继，不用堆栈（递归）也能遍历整个树。,悬空？ NULL,悬空？ NULL,对该二叉树中序遍历的结果为: H, D, I, B, E, A, F, C, G 所以添加线索应当按如下路径进行：,为避免悬空态，应增设一个头结点,例:画出以下二叉树对应的中序线索二叉树。,线索二叉树的生成线索化过程,线索化过程就是在遍历过程中修改空指针的过程,注：

11、此图中序遍历结果为: H, D, I, B, E, A, F, C, G,0,root,1,对应的中序线索二叉树存储结构如图所示：,typedef struct BiThrNode TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针 PointerTag LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;,线索链表的类型描述：,typedef enum Link, Thread PointerTag; / Link=0:指针，Thread=1:线索,二、线索链表的遍历算法:,由于在线索链表中添加了遍

12、历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。,例如: 对中序线索化链表的遍历算法, 中序遍历的第一个结点 ？, 在中序线索化链表中结点的后继 ？,根结点的左子树上处于“最左下”（没有左子树）的结点。,若无右子树，则为后继线索所指结点；,否则为对其右子树进行中序遍历时访问的第一个结点。,void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e) p = T-lchild; / p指向根结点 while (p != T) / 空树或遍历结束时，p=T while (p-LTag=Link) p = p-lchild

13、; / 第一个结点 while (p-RTag=Thread / p进至其右子树根 / InOrderTraverse_Thr,(1)对二叉树中序遍历的同时建立线索. (2) 访问结点:在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息 . (3)如何记录前驱和后继结点: 遍历过程中，附设指针pre, 并始终保持指针pre指向当前访问的、指针p所指结点的前驱。,三、如何建立中序线索链表,void InThreading(BiThrTree p) if (p) / 对以p为根的非空二叉树进行线索化 InThreading(p-lchild); / 左子树线索化 i

14、f (!p-lchild) / 建前驱线索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后继线索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持 pre 指向 p 的前驱 InThreading(p-rchild); / 右子树线索化 / if / InThreading,Status InOrderThreading(BiThrTree / InOrderThreading, ,if (!T) Thrt-lchild = Thrt; else Thrt-lchild = T; pre = Thrt; InThreading(T); pre-rchild = Thrt; / 处理最后一个结点 pre-RTag = Thread; Thrt-rchild = pre; ,小结,7.4 二叉树遍历 7.4.1 二叉树遍历 7.4.2 二叉链存储结构下二叉树遍历的实现 7.5 线索二叉树 1.有关线索二叉树的几个术语 2. 线索二叉树的生成线索化,作业:给定如图所示二叉树T，请画出与其对应的中序线索二叉树。,后续内容,6.4树与二叉树的转换 6.6哈夫曼树,