《二叉树遍历》ppt课件

《《二叉树遍历》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、子树）后右（子树）的遍历；3．先右（子树）后左（子树）的遍历。二、先左后右的遍历算法先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：typedefstructBiTNode{//

3、结点结构TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;lchilddatarchild结点结构:二叉树C语言的类型描述如下:若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：三、算法的递归描述StatusPreorder(BiTreeT,void(*visit)(TElemType&e)){//先序遍历二叉树if(T){visit(T->data);//访问结点Preorder(

4、T->lchild,visit);//遍历左子树Preorder(T->rchild,visit);//遍历右子树}}说明访问函数的示例和preOrder函数调用的方法算法6.1所示.同理可以实现中序遍历二叉树和后序遍历二叉树.3种遍历思想一致,不同之处在于访问根结点的时机先序:访问左子树之前访问根中序:访问右子树之前访问根后序:访问右子树之后访问根ABCDFEHI四、用堆栈实现二叉树中序遍历ABCDFEHIABCDFEHIAABABDDBABA^DA^BACCA^C^AFFEFEIIEF^EFI^FE^FHH^H^用堆栈实现二叉树

5、中序遍历的规律将根结点设置为待入栈结点p如果p不为空,则p入栈,将p的左孩子设置为待入栈结点如果p为空,则栈顶元素出栈,访问栈顶元素,然后将栈顶元素的右孩子设置为待入栈结点直到P为空且栈为空结束算法见书上6.3五、遍历算法的应用举例2、建立二叉树的存储结构1、求二叉树的深度(后序遍历)1、求二叉树的深度(后序遍历)算法基本思想:从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加1。首先分析二叉树的深度和它的左、右子树

6、深度之间的关系。intDepth(BiTreeT){//返回二叉树的深度if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);depthval=1+(depthLeft>depthRight?depthLeft:depthRight);}returndepthval;}2、建立二叉树的存储结构不同的定义方法相应有不同的存储结构的建立算法以字符串的形式根左子树右子树定义一棵二叉树例如:ABCD以空白字符“”表示A(B(,C(,)),D(

7、,))空树只含一个根结点的二叉树A以字符串“A”表示以下列字符串表示ABCDABCD基本的构造过程举例如下：ATBCD^^^^^StatusCreateBiTree(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);//构造右子树}retur

8、nOK;}//CreateBiTree仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，由二叉树的先序和中序序列建树如果同时已知二叉树的中序序列“cbdaegf”，则会如何？二叉树的先序序列二叉树的中序序列左子树左子树右子