二叉树的遍历和应用.ppt

二叉树的遍历和应用二叉树的遍历和应用数据结构与算法1预备知识递归2什么是递归？递归是极强大的问题解决技术。递归是极强大的问题解决技术。当一个函数用它自己来定义时就是递归。当一个函数用它自己来定义时就是递归。递归将一个复杂问题分解为一些更小的递归将一个复杂问题分解为一些更小的问题。问题。3举例：查词典顺序查找：可以从词典第一页开始，按顺序查找：可以从词典第一页开始，按顺序查找每个单词，直到找到。顺序查找每个单词，直到找到。递归解决方案递归解决方案：分而治之的策略；把问：分而治之的策略；把问题划分成小问题，直到到达基例。题划分成小问题，直到到达基例。查找词典查找词典的前半部分查找词典的后半部分4递归解决方案的一般形式怎样按同类型的更小的问题来定义问题怎样按同类型的更小的问题来定义问题各个递归调用怎么减小问题规模各个递归调用怎么减小问题规模哪个问题实例可用做基例哪个问题实例可用做基例随着问题规模的减小，最终能否到达基例随着问题规模的减小，最终能否到达基例 5举例1：n的阶乘public static int fact(int n)/compute the factorial of a nonnegative integer/precondition:n must be greater than or equal to 0/postcondition:returns the factorial of n/-if(n=0)return 1;Else return n*fact(n-1);/end if/end fact6举例2：逆置字符串减小规模：去掉最后一个字符writeBackward(s)if(the string s is empty)do nothing this is the base caseElse Write the last character of swriteBackward(s minus its last character)/end if/end 减小规模：去掉第一个字符writeBackward2(s)if(the string s is empty)do nothing this is the base caseElse writeBackward2(s minus its first character)Write the first character of s /end if/end 7举例3：Hanoi塔solveTowers(count,source,destination,spare)if(count is 1)Move a disk directly from source to destination;Else sloveTowers(count-1,source,spare,destination)sloveTowers(1,source,destination,spare)sloveTowers(count-1,spare,destination,source)/end if/end8举例4：兔子繁殖(递归法)public static int rabbit(int n)if(n 29举例4：兔子繁殖(迭代法)public static int iterativeRabbit(int n)/iterative solution to the rabbit problem/initialize base cases:int previous=1;/rabbit(1)int current=1;/rabbit(2)int next=1;/result when n is 1 or 2/computer next rabbit values when n=3 for(int i=3;i=n;i+)next=current+previous;previous=current;current=next;/end forreturn next;/end10二叉树的遍历11一、问题的提出一、问题的提出二、遍历算法二、遍历算法三、算法的递归描述三、算法的递归描述四四、遍历算法的应用举例遍历算法的应用举例12 顺着某一条搜索路径巡访巡访二叉树中的结点，使得每个结点均被访问一均被访问一次次，而且仅被访问一次仅被访问一次。问题的提出“访问访问”的含义可以很广，如：输出结点的信息等。13 “遍历遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继每个结点有两个后继，则存在如何遍历存在如何遍历即按什么样的搜索搜索路径路径遍历的问题。14层次遍历1.首先首先创建一个队列创建一个队列；若二叉树非空，；若二叉树非空，将根将根放入队列放入队列；2.从队列取出一个元素并访问从队列取出一个元素并访问，如果该元素如果该元素有有左孩子左孩子就将它放入队列就将它放入队列，如果该元素有如果该元素有右孩子右孩子就将它放入队列就将它放入队列；3.若队列非空，继续第若队列非空，继续第2步，直至队列为空，步，直至队列为空，则二叉树的层次遍历过程结束。则二叉树的层次遍历过程结束。例如,图5.1中的二叉树按照层次遍历的结果为:A B C D E F G H I15前序周游前序周游(preorder traversal)若二叉树非空,则依次进行如下操作:(1)访问根结点;(2)前序周游左子树;(3)前序周游右子树。前序遍历二叉树(preorder traversal)例如,图5.1中的二叉树按照前序周游的结果为:A B D C E G F H I16中序周游中序周游(inorder traversal)若二叉树非空,则依次进行如下操作:(1)中序周游左子树;(2)访问根结点;(3)中序周游右子树。中序遍历二叉树(inorder traversal)例如,图5.1中的二叉树按照中序周游的结果为:B D A G E C H F I17后序周游后序周游(postorder traversal)若二叉树非空,则依次进行如下操作:(1)后序周游左子树;(2)后序周游右子树;(3)访问根结点。后序遍历二叉树(postorder traversal)例如,图5.1中的二叉树按照后序周游的结果为:D B G E H I F C A18已已知知二二叉叉树树的的前前序序和和中中序序周周游游序序列列如如下下,画出该二叉树。画出该二叉树。前序周游序列前序周游序列:ABCDEFGHIJ 中序周游序列中序周游序列:CBEDAGHFJI ABCDEFGHIJ课堂练习课堂练习19已已知知二二叉叉树树的的后后序序和和中中序序周周游游序序列列如如下下,画出该二叉树。画出该二叉树。后序周游序列后序周游序列:ABCDEFG 中序周游序列中序周游序列:ACBGEDF G CABFED课堂练习课堂练习20画画出出中中序序周周游游序序列列为为ABCDEFGHIJKL的的完全二叉树。完全二叉树。HDBFEKJILACG课堂练习课堂练习21上面三种周游方法都可以用递归函数来实现例如,前序周游二叉树的函数为:void preorder(BinNode*subroot)if(subroot=NULL)return;visit(subroot);preorder(subroot-left();preorder(subroot-right();遍历二叉树的递归实现22课后思考课后思考思考思考遍历算法的非递归遍历算法的非递归算法思想描述算法思想描述。由先序、中序和后序中由先序、中序和后序中任意两个序列能够唯一任意两个序列能够唯一确定一颗二叉树确定一颗二叉树？23遍历算法的应用举例1、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数 (先序遍历先序遍历)2、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)3、复制二叉树、复制二叉树(后序遍历后序遍历)4 4、建立二叉树的存储结构、建立二叉树的存储结构241、统计二叉树中叶子结点的个数算法基本思想算法基本思想:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个需在遍历算法中增添一个“计数计数”的参数，的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增若是叶子，则计数器增1 1。25void CountLeaf(BiTree T,int&count)if(T)if(!T-lchild)&(!T-rchild)count+;/对叶子结点计数 CountLeaf(T-lchild,count);CountLeaf(T-rchild,count);/if/CountLeaf26Traversal Example/Return the number of nodes in the treetemplate int count(BinNode*subroot)if(subroot=NULL)return 0;/Nothing to count if(subroot.isleaf()return 1;/the node is leaf return count(subroot-left()+count(subroot-right();272、求二叉树的深度算法基本思想算法基本思想:从二叉树深度的定义可知，二叉树的二叉树的深度应为其左、右子树深度的最大值加深度应为其左、右子树深度的最大值加1 1。由此，需先分别求得左、右子树的深度，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、求得左、右子树深度的最大值，然后加右子树深度的最大值，然后加 1 1。首先分析二叉树的深度二叉树的深度和它的左左、右子右子树深度树深度之间的关系。28求二叉树的深度的求二叉树的深度的伪代码设计。伪代码设计。请利用上课讲述的方法请利用上课讲述的方法设计出该问题的详细算法，设计出该问题的详细算法，多写几个多写几个课后复习课后复习29二叉树的存储30存于顺序存储结构BDEACFGA B C D EF G123 4 5678 9101112 13 14 1531以字符串的形式 根 左子树 右子树定义一棵二叉树例如:ABCD以空白字符“”表示A(B(,C(,),D(,)空树空树只含一个根结点只含一个根结点的二叉树的二叉树A以字符串“A ”表示以下列字符串表示32Status CreateBiTree(BiTree&T)scanf(&ch);if(ch=)T=NULL;else if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;/生成根结点 CreateBiTree(T-lchild);/构造左子树 CreateBiTree(T-rchild);/构造右子树 return OK;/CreateBiTree33A B C D A BCD上页算法执行过程举例如下：ATBCD34 仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，由二叉树的先序和中序序列建树 如果同时已知二叉树的中序序列“cbdaegf”，则会如何？二叉树的先序序列二叉树的中序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根根根35a b c d e f gc b d a e g f例如:aab bccddeeffggabcdefg先序序列中序序列36void CrtBT(BiTree&T,char pre,char ino,int ps,int is,int n)/已知preps.ps+n-1为二叉树的先序序列，/insis.is+n-1为二叉树的中序序列，本算 /法由此两个序列构造二叉链表 if(n=0)T=NULL;else k=Search(ino,preps);/在中序序列中查询 if(k=-1)T=NULL;else /CrtBT 37T=(BiTNode*)malloc(sizeof(BiTNode);T-data=preps;if(k=is)T-Lchild=NULL;else CrtBT(T-Lchild,pre,ino,ps+1,is,k-is);if(k=is+n-1)T-Rchild=NULL;else CrtBT(T-Rchild,pre,ino,ps+1+(k-is),k+1,n-(k-is)-1);38二叉树的线索化39何谓线索二叉树？遍历二叉树的结果是，求得结点的一个线性序列。ABCDEFGHK例如:先序先序序列:A B C D E F G H K中序中序序列:B D C A H G K F E后序后序序列:D C B H K G F E A40指向该线性序列中的“前驱”和 “后继”的指针指针，称作“线索线索”与其相应的二叉树，称作“线索二叉树线索二叉树”包含“线索”的存储结构，称作“线索链线索链表表”A B C D E F G H K D C B E 41 在二叉链表的结点中增加两个标志域增加两个标志域，并作如下规定：dataLTagRTag LChildRChildLTag=RTag=0 LChild 域指示结点的左孩子1 LChild 域指示结点的前驱0 RChild 域指示结点的右孩子1 RChild 域指示结点的后继42 在中序遍历过程中修改结点的在中序遍历过程中修改结点的左、右指针域，以保存当前访问结左、右指针域，以保存当前访问结点的点的“前驱前驱”和和“后继后继”信息。遍历过信息。遍历过程中，附设指针程中，附设指针pre,并始终保持指并始终保持指针针pre指向当前访问的、指针指向当前访问的、指针p所指所指结点的前驱。结点的前驱。如何建立线索链表？43 A 0 0 根结点 B 0 0 C 0 0 D 0 0 E 0 0 F 0 0 G 0 0 0 1 头结点PreP1PreP1Pre44void InThreading(BiThrTree p)if(p)/对以p为根的非空二叉树进行线索化 InThreading(p-lchild);/左子树线索化 if(!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/InThreading45Status InOrderThreading(BiThrTree&Thrt,BiThrTree T)/构建中序线索链表 if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)exit(OVERFLOW);Thrt-LTag=Link;Thrt-RTag=Thread;Thrt-rchild=Thrt;/添加头结点 return OK;/InOrderThreading 46if(!T)Thrt-lchild=Thrt;else Thrt-lchild=T;pre=Thrt;InThreading(T);pre-rchild=Thrt;/处理最后一个结点 pre-RTag=Thread;Thrt-rchild=pre;47父指针表示和等价类问题48父指针表示法49等价类问题父指针表示法可以有效的解答下述问题父指针表示法可以有效的解答下述问题:给出两个结点，它们是否在同一棵树中给出两个结点，它们是否在同一棵树中?/Return TRUE if nodes in different treesbool Gentree:differ(int a,int b)int root1=FIND(a);/Find root for a int root2=FIND(b);/Find root for b return root1!=root2;/Compare roots50Union/Findvoid Gentree:UNION(int a,int b)int root1=FIND(a);/Find root for a int root2=FIND(b);/Find root for b if(root1!=root2)arrayroot2=root1;int Gentree:FIND(int curr)const while(arraycurr!=ROOT)curr=arraycurr;return curr;/At root51等价类处理的例子(1)52等价类处理的例子(2)53重量权衡合并规则需要降低树的高度需要降低树的高度.Weighted union rule:两树归并时，将结两树归并时，将结点较少树的根结点指向结点较多树的根点较少树的根结点指向结点较多树的根结点结点.可以把树的整体深度限制在可以把树的整体深度限制在O(log n)54路径压缩Path Compressionint Gentree:FIND(int curr)const if(arraycurr=ROOT)return curr;return arraycurr=FIND(arraycurr);55要点回顾要点回顾递归算法的设计方法二叉树的遍历算法二叉树遍历算法的应用二叉树的建立56