1、,6.4 二叉樹的算法描述,Void lnorderTraverse(BiTree BT) 采用二叉鏈表存儲結(jié)構(gòu)，中序遍歷二叉樹T的非遞歸算法. InitStack(S)； p=BT； while(p|!StackEmpty(S) if(p) push(S，p)； p=p-lchild；/根指針進棧，遍歷左子樹 else 根指針退棧，訪問根結(jié)點，遍歷右子樹 pop(S，p)； visit(p); p=p-rchild； /else InOrderTraverse,6.4.1非遞歸中序遍歷BT的算法:,我們先觀察一下三種遍歷行走的路線,*,*,*,*,*,*,*,*,*,前序遍歷NLR,#,#,

2、#,#,#,#,#,#,#,中序遍歷LNR,三種遍歷的訪問位置對比：,三種遍歷的路線完全一樣，只是訪問時間不同；,前序：第一次經(jīng)過* 時訪問,中序：第二次經(jīng)過# 時訪問,后序：第三次經(jīng)過 push(S,p); pop(S,p); Boolean StackEmpty(S); 下面給出基于邏輯結(jié)構(gòu)的算法描述,非遞歸中序遍歷二叉樹的算法思想 建立棧 stack； P指向根； 當p不空 且 stack 不空時反復做： 若 p不空 ,p 入 棧; p指向左子女； 否則： 出棧頂元素到p中； 訪問p； p指向右子女； 4. 結(jié)束,非遞歸中序遍歷BT的算法:,非遞歸中序遍歷BT的算法:,非遞歸中序遍歷BT

3、的算法:,非遞歸中序遍歷BT的算法:,非遞歸中序遍歷BT的算法:,非遞歸中序遍歷BT的算法:,非遞歸中序遍歷BT的算法:,非遞歸中序遍歷BT的算法:,非遞歸中序遍歷BT的算法:,非遞歸中序遍歷BT的算法:,非遞歸中序遍歷BT的算法:,非遞歸中序遍歷BT的算法:,非遞歸中序遍歷BT的算法:,非遞歸中序遍歷BT的算法:,7/28/2020,二叉樹與表達式：,表達式 : ( a + b ) c d / e 二叉樹的先序遍歷序列為： + a b c / d e 二叉樹的中序遍歷序列為： a + b c d / e 二叉樹的后序遍歷序列為： a b + c d e / ,前綴表達式 中綴表達式 后綴表達

4、式,void PreOrderTraverse (BiTree T, void (*visit) (TelemType / PreOrderTraverse,非遞歸先序遍歷二叉樹,6.4.2遍歷算法的應用舉例,1、查詢二叉樹中某個結(jié)點,7/28/2020,Status Preorderelem (BiTree T, ElemType x, BiTree ,7/28/2020,2、統(tǒng)計二叉樹中葉子結(jié)點的個數(shù),7/28/2020,算法基本思想: 先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結(jié)點并計數(shù)。在遍歷算法中增加一個參數(shù)用于計數(shù)，并將算法中“VISIT()” 的操作改為:若是葉子，則計

5、數(shù)器增1。,void CountLeaf (BiTree T, int / if / CountLeaf,3 按先序遍歷序列建二叉樹,Status CreateBiTree(BiTree / CreateBiTree,A B C D E G F ,按先序遍歷序列建立二叉樹的二叉鏈表， 已知先序序列為：,7/28/2020,4、求二叉樹的深度,7/28/2020,int TreeDepth (BiTree T ) / 返回二叉樹的深度 if ( !T ) depth = 0; else depthLeft = TreeDepth( T-lchild ); depthRight= TreeDepth( T-rchild ); depth = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depth; ,算法：,1 前序遍歷序列：EDACBGFH