《DS树和二叉树二叉树的遍历实用教案》由会员分享，可在线阅读，更多相关《DS树和二叉树二叉树的遍历实用教案（53页珍藏版）》请在金锄头文库上搜索。
1、本节内容(nirng)前序、中序、后序遍历(binl)的过程前序、中序、后序遍历(binl)的递归算法前序、中序、后序遍历(binl)的非递归算法层序遍历(binl)算法第1页/共52页第一页，共53页。6.3.1遍历(binl)二叉树 二叉树的遍历(bin l)：是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。可以是对结点进行的各种处理，一般简化为输出结点的值。前序遍历中序遍历后序遍历层序遍历第2页/共52页第二页，共53页。假设(jish)二叉树的六种遍历(binl)方式：DLR、LDR、LRD、DRL、RDL、RLD如果限定先左后右，则遍历(b
2、inl)方式有三种：DLR=前序(或先序)LDR=中序LRD=后序根结点D左子树L右子树R二叉树二叉树的遍历方式第3页/共52页第三页，共53页。若二叉树为空，则返回(fnhu)；否则：访问根结点；前序遍历根结点的左子树；前序遍历根结点的右子树。前序遍历(binl)序列：ABCDEFG二叉树的前序遍历(binl)ABDGCEF第4页/共52页第四页，共53页。若二叉树为空，则返回；否则：中序遍历根结点(jidin)的左子树；访问根结点(jidin)；中序遍历根结点(jidin)的右子树。中序遍历(binl)序列：DGBAECF二叉树的中序遍历(binl)ABCDEFG第5页/共52页第五页，共
3、53页。若二叉树为空，则返回；否则(fuz)：后序遍历根结点的左子树；后序遍历根结点的右子树。访问根结点；后序(hux)遍历序列：GDBEFCA二叉树的后序(hux)遍历ABCDEFG第6页/共52页第六页，共53页。从二叉树的第一层（即根结点(jidin)）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点(jidin)逐个访问。A B C D E F G二叉树的层序遍历(binl)ABCDEFG层序遍历(binl)序列：第7页/共52页第七页，共53页。例:先序遍历(binl)序列（波兰式）为：中序遍历(binl)序列为：后序遍历(binl)序列（逆波兰式）为：- + a * b
4、 c d / e fa + b * c d e / fa b c d - * + e f / -a+/-*efcdb-第8页/共52页第八页，共53页。Q:若已知一棵二叉树的前序序列和中序序列，能否唯一(wiy)确定这棵二叉树呢？怎样确定？例如：已知一棵二叉树的前序遍历序列和中序遍历序列分别为ABCDEFGHI和BCAEDGHFI，如何(rh)构造该二叉树呢?第9页/共52页第九页，共53页。前序：前序：A B C D E F G H I中中序：序：B C A E D G H F I前序：前序：B C中序：中序：B C B C D EF GH IA前序：前序： D E F G H I中序：中序
5、： E D G H F IABCDEFGHI第10页/共52页第十页，共53页。前序：前序：F G H I中序：中序：G H F I前序：前序： D E F G H I中序：中序： E D G H F IABCDEFGHIABCDEFIGH第11页/共52页第十一页，共53页。1.根据前序序列(xli)的第一个元素建立根结点；2.在中序序列(xli)中找到该元素，确定根结点的左右子树的中序序列(xli)；3.在前序序列(xli)中确定左右子树的前序序列(xli)；4.由左子树的前序序列(xli)和中序序列(xli)建立左子树；5.由右子树的前序序列(xli)和中序序列(xli)建立右子树。已知
6、一棵二叉树的前序序列和中序序列，构造该二叉树的过程(guchng)如下：第12页/共52页第十二页，共53页。例：已知前序遍历(binl)序列为ABC，后序遍历(binl)序列为CBA，画出满足条件的二叉树。则下列二叉树都满足条件。ABCABC第13页/共52页第十三页，共53页。结论(jiln)给定一棵二叉树的前序和中序序列可以唯一确定(qudng)此二叉树给定一棵二叉树的中序和后序序列可以唯一确定(qudng)此二叉树给定一棵二叉树的前序和后序序列不能唯一确定(qudng)此二叉树第14页/共52页第十四页，共53页。先序遍历(bin l)二叉树的递归算法Status PreOrderTr
7、averse(BiTree T,Status(* Visit)(TElemType e)/二叉链表存储结构，visit是对数据(shj)元素操作的函数/先序遍历二叉树T的递归算法，对每个数据(shj)元素调用visit if(T) if (Visit(T-data) / 访问当前结点 if ( PreOrderTraverse(T-lchild,Visit ) / 先序左子 if (PreOrderTraverser(T-rchild,Visit) return OK; / 先序右子 return ERROR; else return OK;第15页/共52页第十五页，共53页。/最简单的Vi
8、sit函数是： 输出元素e的值Status PrintElement (TElemType e) printf ( e );/实现(shxin)时，加上格式串 return OK;/调用实例：PreOrderTraverse (T, PrintElement);第16页/共52页第十六页，共53页。中序遍历(binl)二叉树的递归算法：StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)if(T)if(InOrderTraverse(T-lchild,Visit)if(Visit(T-data)if(InOrderTraverse(T
9、-rchild,Visit)returnOK;returnERROR;elsereturnOK;第17页/共52页第十七页，共53页。后序(hux)遍历二叉树的递归算法：StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)if(T)if(PostOrderTraverse(T-lchild,Visit)if(PostOrderTraverse(T-rchild,Visit)if(Visit(T-data)returnOK;returnERROR;elsereturnOK;第18页/共52页第十八页，共53页。中序遍历(binl)的
10、执行过程第19页/共52页第十九页，共53页。void PreOrder(BiTree T) if(T) printf(T-data); /访问结点(ji din) PreOrder(T-lchild); /先序左子 PreOrder(T-rchild); /先序右子 void InOrder(BiTree T) if(T) InOrder(T-lchild); /中序左子 printf(T-data); /访问结点(ji din) InOrder(T-rchild); /中序右子 void PostOrder(BiTree T) if(T) PostOrder(T-lchild); /后序左
11、子 PostOrder(T-rchild); /后序右子 printf(T-data); /访问结点(ji din) 三种遍历的简单(jindn)写法第20页/共52页第二十页，共53页。2.遍历算法(sunf)的应用举例 “遍历”是二叉树各种操作的基础，可以在遍历过程中对结点进行各种操作，如：对于一棵已知树求结点的双亲，求结点的孩子结点个数，判定(pndng)结点所在的层次等，也可在遍历过程中生成结点，建立二叉树的存储结构。第21页/共52页第二十一页，共53页。例1：求二叉树的深度(shnd)int getDepth(BiTree T) int depth,dLeft,dRight; if
12、 (!T) depth = 0; else dLeft = getDepth(T-lchild); dRight = getDepth(T-rchild); depth = (dLeft=dRight) ? (dLeft+1) : (dRight+1); return depth;第22页/共52页第二十二页，共53页。例2：统计二叉树中叶子(yzi)结点的个数void CountLeaf(BiTree T, int &count) if (T) if (T-lchild=NULL) & (T-rchild=NULL) +count; return; CountLeaf(T-lchild, c
13、ount); / 统计(tngj)左子树叶子结点个数 CountLeaf(T-rchild, count); / 统计(tngj)右子树叶子结点个数 count在调用(dioyng)此函数前已初始化为0第23页/共52页第二十三页，共53页。例3：按先序序列(xli)建立二叉树的二叉链表已知先序序列：A B C # # D E # G # # F # # #（其中#表示空格字符(z f)）建立相应的二叉链表。ABCEDGF第24页/共52页第二十四页，共53页。例3：按先序序列(xli)建立二叉树的二叉链表/按先序序列输入(shr)二叉树中结点的值，空格字符表示空树int CreateBiTr
14、ee(BiTree &T) char ch; scanf(%c,&ch); if (ch = ) T = NULL; else if (!(T=(BiTNode*)malloc(sizeof(BiTNode) exit(-1); T-data = ch; / 构造根结点 CreateBiTree(T-lchild); / 构造左子 CreateBiTree(T-rchild); / 构造右子 return 0;第25页/共52页第二十五页，共53页。从上述二叉树遍历的定义可知，三种遍历算法不同之处仅在于访问根结点和遍历左、右子树的先后关系。如果(rgu)在算法中暂且抹去和递归无关的visit语
15、句，则三个遍历算法完全相同。由此，从递归执行过程的角度来看先序、中序和后序遍历也是完全相同的。第26页/共52页第二十六页，共53页。三种遍历(binl)过程示意图n向下的箭头表示更深一层的递归调用，向上的箭头表示从递归调用退出返回。n虚线(xxin)旁的三角形、圆形和方形内的字符分别表示在先序、中序和后序遍历过程中访问结点时输出的信息。n只要沿虚线(xxin)从1出发到2结束，将沿途所见的三角形（或圆形、方形）内的字符记下，便得遍历二叉树的先序（或中序、后序）序列。第27页/共52页第二十七页，共53页。中序遍历(binl)二叉树的非递归算法递归算法虽然简洁，但是有时程序设计不允许用递归，且
16、递归效率(xiol)不高，这时就存在如何把递归程序转化成等价的非递归算法的问题。解决这个问题的关键是设置一个栈。仿照递归算法执行过程中编译栈的工作原理，可以写出相应的非递归算法。第28页/共52页第二十八页，共53页。访问结点(jidin)序列:B栈S内容(nirng):D A B中序遍历(binl)的非递归实现,算法6.2ADBC NULL D NULL NULL第29页/共52页第二十九页，共53页。访问(fngwn)结点序列:栈S内容(nirng):BD A中序遍历的非递归实现(shxin),算法6.2ADBCA C NULL NULLC第30页/共52页第三十页，共53页。1.栈s初始
17、化，根指针进栈；2.循环(xnhun)直到栈s为空2.1当指向栈顶元素的指针p不空时循环(xnhun)2.1.1p-lchild压栈；2.2空指针退栈2.3如果栈s不空，则2.3.1将栈顶元素弹出至p；2.3.2访问p-data;2.3.3p的右子树压栈；中序遍历非递归算法(sunf)6.2（伪代码）第31页/共52页第三十一页，共53页。中序遍历(binl)二叉树的非递归算法6.2/中序遍历的非递归算法Status InOrderTrav(BiTree T) InitStack(S); Push(S,T); /根指针入栈 while(!StackEmpty(S) while(GetTop(S
18、,p)&p) Push(S,p-lchild);/向左走到尽头(jntu) Pop(S,p); /空指针退栈 if(!StackEmpty(S) /栈非空，则出栈访问结点，右子入栈 Pop(S,p); printf(p-data); Push(S,p-rchild); return OK;第32页/共52页第三十二页，共53页。1.栈s初始化，p指向根结点；2.p非空或栈s非空时循环2.1如果p不空2.1.1p压栈；2.1.2继续遍历p的左子树（即p=p-lchild）;2.2否则2.2.1将栈顶元素弹出至p；2.2.2输出(shch)p-data;2.2.3准备遍历p的右子树（即p=p-rc
19、hild）；中序遍历(binl)非递归算法6.3（伪代码）第33页/共52页第三十三页，共53页。访问结点(jidin)序列:B栈S内容(nirng):D A B中序遍历的非递归实现(shxin),算法6.3ADBC D第34页/共52页第三十四页，共53页。访问结点(jidin)序列:栈S内容(nirng):BD A中序遍历的非递归实现(shxin),算法6.3ADBCA CC第35页/共52页第三十五页，共53页。中序遍历(bin l)的非递归算法6.3Status InOrderTrv(BiTree T) InitStack(S); p=T; while(p | !StackEmpty(
20、S) if (p) Push(S,p); p=p-lchild; else Pop(S,p); printf(p-data)； p=p-rchild; return OK;/根指针(zhzhn)进栈，遍历左子/根指针退栈，访问根结点(ji din)，遍历右子 第36页/共52页第三十六页，共53页。1.栈s初始化，p指向根结点；2.p非空或栈s非空时循环2.1当p不空时循环2.1.1输出p-data;2.1.2p压栈；2.1.3继续(jx)遍历p的左子树2.2如果栈s不空，则2.2.1将栈顶元素弹出至p；2.2.2准备遍历p的右子树；前序遍历非递归算法(sunf)（伪代码）中序第37页/共52
21、页第三十七页，共53页。访问(fngwn)结点序列:A栈S内容(nirng):BD A B前序遍历(binl)的非递归实现ADBC第38页/共52页第三十八页，共53页。访问(fngwn)结点序列:A栈S内容(nirng):B D A前序遍历(binl)的非递归实现ADBC D第39页/共52页第三十九页，共53页。访问结点(jidin)序列:A栈S内容(nirng):BD C前序遍历(binl)的非递归实现ADBCC第40页/共52页第四十页，共53页。void PreOrderTrv( BiTree T) InitStack(S); BiTree p = T; while (p!=NULL
22、 | | !StackEmpty(S) ) while (p != NULL) printf(p-data); Push(S, p); p = p-lchild; if (!StackEmpty(S) ) Pop(S, p); p = p-rchild; 第41页/共52页第四十一页，共53页。层序遍历(binl)1.队列Q初始化；2.2.如果二叉树非空，将根指针入队；3.3.循环直到队列为空4.3.1队头元素出队，q指向(zhxin)它；5.3.2访问结点q；6.3.3若结点q有左子，则将左子指针入队；7.3.4若结点q有右子，则将右子指针入队；第42页/共52页第四十二页，共53页。/ 层
23、序遍历(利用队列)void LevelOrderTraverse(BiTree T) LinkQueue q; BiTNode* p; if(T) InitQueue(q); / 初始化队列q EnQueue(q,T); / 根指针入队 while (!QueueEmpty(q) / 队列非空，循环(xnhun) DeQueue(q,p); / 队头元素出队, 赋给p printf(p-data); / 访问p所指结点 if (p-lchild!=NULL) / p有左子 EnQueue(q, p-lchild); / p的左子入队 if (p-rchild!=NULL) / p有右子 EnQ
24、ueue(q, p-rchild); / p的右子入队 printf(n); 第43页/共52页第四十三页，共53页。遍历(binl)的复杂度分析遍历算法的基本操作是访问(fngwn)结点，则不论哪种遍历算法，对于有n个结点的二叉树，时间复杂度均为O(n)只要对每个结点的处理（函数Visit的执行）时间是一个常数，那么遍历二叉树就可以在线性时间内完成所需要的辅助空间为遍历过程中栈的最大容量，即树的深度最坏情况下具有n个结点的二叉树高度为n，则所需要的空间复杂度为O(n)第44页/共52页第四十四页，共53页。习题(xt)6.27：假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为AB
25、CDEFGHIJK。画出该二叉树。【分析】由先序序列得到根结点，然后由中序序列得到左右子树的先序和中序序列。依次(yc)类推。JEBFAHDCGIK第45页/共52页第四十五页，共53页。作业(zuy)6.14 6.27 6.28 6.29 6.426.44 6.47本周五 下午(xiw)实验 二叉树的实现第46页/共52页第四十六页，共53页。习题(xt)1.按先序次序建立二叉树的算法，原型说明：2.void CreateBiTree(BiTree &T);3.2. 二叉树的打印，有缩进，并旋转了90度，本算法可以用于调试(dio sh)二叉树处理程序。h为T所在层数。原型：4.void p
26、rintBiTree(BiTree T, int h);5.main函数里的调用语句为：BiTree root; printBiTree(root, 0);第47页/共52页第四十七页，共53页。二叉树的打印(d yn)void printNode(TElemType e, int h) / 打印结点的值e，结点的高度为hfor (int i=0; irchild, h+1); / 先右后左printNode(T-data, h);printBiTree(T-lchild, h+1);第48页/共52页第四十八页，共53页。求双亲(shungqn)结点BiTNode* getParent(Bi
27、Tree T, TElemType e)BiTNode* p;if (T = NULL)return NULL;else if (T-lchild&T-lchild-data=e) | (T-rchild&T-rchild-data=e)return T;elsep = getParent(T-lchild, e);if (!p)p = getParent(T-rchild, e); return p;第49页/共52页第四十九页，共53页。左右(zuyu)子树交换void exchange(BiTree T) if (T) BiTNode* p; p = T-lchild; T-lchild
28、 = T-rchild; T-rchild = p; exchange(T-lchild); exchange(T-rchild); 第50页/共52页第五十页，共53页。后序(hux)非递归ifcurrentisleaf,printifcurrent.lchild=previous,lelfchildhasbeenvisited,pushrchildifcurrent.rchild=previous,wehavevisitedbothchild,printotherwise,pushlchild第51页/共52页第五十一页，共53页。感谢您的欣赏(xnshng)！第52页/共52页第五十二页，共53页。内容(nirng)总结本节内容。第1页/共52页。scanf(%c,&ch)。如果在算法中暂且抹去和递归无关的visit语句，则三个遍历(bin l)算法完全相同。中序遍历(bin l)非递归算法6.3（伪代码）。while(p |。前序遍历(bin l)非递归算法（伪代码）。3.3 若结点q有左子，则将左子指针入队。printf(n)。printf(%cn, e)。printNode(*, h)。第51页/共52页。感谢您的欣赏。第52页/共52页第五十三页，共53页。
