【文章內(nèi)容簡(jiǎn)介】 是訪問(wèn)結(jié)點(diǎn)的時(shí)機(jī)不同。 從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑 上，每個(gè)結(jié)點(diǎn)經(jīng)過(guò) 3次。 A F E D C B G 第 1次經(jīng)過(guò)時(shí)訪問(wèn)＝先序遍歷 第 2次經(jīng)過(guò)時(shí)訪問(wèn)＝中序遍歷 第 3次經(jīng)過(guò)時(shí)訪問(wèn)＝后序遍歷 2. 二叉樹遍歷的時(shí)間效率和空間效率 時(shí)間效率 :O(n) //每個(gè)結(jié)點(diǎn)只訪問(wèn)一次 空間效率 :O(n) //棧占用的最大輔助空間 （精確值：樹深為 k的遞歸遍歷需要 k+1個(gè)輔助單元！） A D B C D L R A D L R D L R B D C D L R 先序遍歷序列： A B D C 先序遍歷 : A D B C L D R B L D R L D R A D C L D R 中序遍歷序列： B D A C 中序遍歷 : A D B C L R D L R D L R D A D C L R D 后序遍歷序列： D B C A 后序遍歷 : B A B C D E F G H K 復(fù)習(xí)回顧： 先序序列： 中序序列： 后序序列： A B C D E F G H K B D C A E H G K F D C B H K G F E A lchild data rchild parent lchild data rchild void Preorder (BiTree T, void( *visit)(TElemTypeamp。 e)) { // 先序遍歷二叉樹 if (T) { visit(Tdata)。 // 訪問(wèn)根結(jié)點(diǎn) Preorder(Tlchild, visit)。 // 遍歷左子樹 Preorder(Trchild, visit)。// 遍歷右子樹 } } void pre(BiTree T) { if(T) { printf(%d\t,Tdata)。 pre(TL)。 pre(TR)。 } } 主程序 Pre( T ) 返回 返回 pre(T R)。 返回 返回 pre(T R)。 A C B D T B printf(B)。 pre(T L)。 T A printf(A)。 pre(T L)。 T D printf(D)。 pre(T L)。 T C printf(C)。 pre(T L)。 返回 T 左是空返回 pre(T R)。 T 左是空返回 T 右是空返回 T 左是空返回 T 右是空返回 pre(T R)。 先序序列： A B D C 四、遍歷二叉樹的非遞歸實(shí)現(xiàn)： ?中序 遍歷 的 非遞歸 實(shí)現(xiàn)： 結(jié)點(diǎn)（初始時(shí)是根結(jié)點(diǎn)）進(jìn)棧，沿左指針查找左 孩 子。 若有左 孩 子，返回第一步。 若無(wú)左 孩 子，判棧空？空則結(jié)束。非空，棧頂結(jié)點(diǎn)出棧 訪問(wèn)。轉(zhuǎn)向右子樹，返回 1。 例如 : B C D E L A X W 中序： B、 L、 E、 A、 C、 W、 X、 D Status InOrderTraverse(BiTree t, Visit){ initstack(s)。 push(s,t)。 // t 是根結(jié)點(diǎn) while (!stackempty(s)) { while (Gettop(s,p)) amp。amp。 p ) //有值且非空時(shí) push(s, plchild)； //null 值可能進(jìn)棧 pop (s,p)。 // 空指針退棧 if (!stackempty(s)) // 訪問(wèn)結(jié)點(diǎn)，向右一步 { pop(s, p)。 visit( pdata)。 push(s,prchild)。 } } //While return OK。 } //InOrderTraverse Status InOrderTraverse(BiTree t, Visit){ initstack(s)。 p=T。 while ( p || !StackEmpty(s) ) { if ( p ) { push(s,p)； p = plchild。 } //根指針進(jìn)棧，遍歷左子樹 else { //根指針退棧，訪問(wèn)根結(jié)點(diǎn)，遍歷右子樹 pop(s,p)。 if (!Visit(pdata) ) return ERROR。 p=prchild。 } } return OK。 } //InOrderTraverse 中序非遞歸算法演示 A B C D E F G p i PA (1) A B C D E F G p i PA PB (2) A B C D E F G p i PA PB PC (3) p=NULL A B C D E F G i PA PB 訪問(wèn)： C (4) p A B C D E F G i PA 訪問(wèn)： C B (5) A B C D E F G i PA PD 訪問(wèn)： C B p (6) A B C D E F G i PA PD PE 訪問(wèn)： C B p (7) A B C D E F G i PA PD 訪問(wèn)： C B E p (8) A B C D E F G i PA PD PG 訪問(wèn)： C B E P=NULL (9) A B C D E F G i PA 訪問(wèn)： C B E G D p (11) A B C D E F G i PA PF 訪問(wèn)： C B E G D p (12) A B C D E F G i PA PD 訪問(wèn)： C B E G p (10) A B C D E F G i PA 訪問(wèn)： C B E G D F p=NULL (13) A B C D E F G i 訪問(wèn)： C B E G D F A p (14) A B C D E F G i 訪問(wèn)： C B E G D F A p=NULL (15) 五、建立二叉樹的存儲(chǔ)結(jié)構(gòu) 不同的定義方法相應(yīng)有不同的存儲(chǔ)結(jié)構(gòu)的建立算法 以字符串的形式 “ 根 左子樹 右子樹 ” 定義一棵二叉樹 例如 : 以空白字符“ ”表示 A B C D A(B( ,C( , )),D( , )) 空樹 只含一個(gè)根結(jié)點(diǎn)的二叉樹 A 以字符串“ A ” 表示 以下列字符串表示 Status CreateBiTree(BiTree amp。T) { scanf(amp。ch)。 if (ch==39。 39。) T = NULL。 else { if (!(T = new BiTNode)) exit(OVERFLOW)。 Tdata = ch。 // 生成根結(jié)點(diǎn) CreateBiTree(Tlchild)。 // 構(gòu)造左子樹 CreateBiTree(Trchild)。 // 構(gòu)造右子樹 } return OK。 } // CreateBiTree A B C D B 上頁(yè)算法執(zhí)行過(guò)程舉例如下 : A T B C D ^ ^ ^ ^ ^ scanf(amp。ch)。 if (ch==39。 39。) T = NULL。 else { if (!(T = new BiTNode)) exit(OVERFLOW)。 Tdata = ch。 CreateBiTree(Tlchild)。 CreateBiTree(Trchild)。 六、 遍歷算法的應(yīng)用舉例 統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù) 求二叉樹的深度 (后序遍歷 ) 復(fù)制二叉樹 (后序遍歷 ) 建立二叉樹的存儲(chǔ)結(jié)構(gòu) 查詢二叉樹中某個(gè)結(jié)點(diǎn) 1) 在二叉樹不空的前提下 ,和根結(jié)點(diǎn)的元素進(jìn)行比較 ,若相等 ,則找到返回 TRUE。 2) 否則在左子樹中進(jìn)行查找 ,若找到 , 則返回 TRUE。 3) 否則繼續(xù)在右子樹中進(jìn)行查找 ,若找到 ,則返回 TRUE,否則返回 FALSE。 查詢二叉樹中某個(gè)結(jié)點(diǎn) Status Preorder (BiTree T, ElemType x, BiTree amp。p) { //若二叉樹中存在和 x 相同的元素，則 p指向該結(jié)點(diǎn)并返回 OK, 否則返回 FALSE } if (T) { if (Tdata==x) { p = T。 return OK,} }//if else return FALSE。 else { if (Preorder(Tlchild, x, p) return OK。 else return(Preorder(Trchild, x, p)) 。 }//else 統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù) 算法基本思想 :先序 (或中序或后序 )遍歷二叉樹，在遍歷過(guò)程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。由此，需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)，并將算法中“訪問(wèn)結(jié)點(diǎn)” 的操作改為 :若是葉子，則計(jì)數(shù)器增 1。 void CountLeaf (BiTree T, intamp。 count){ if ( T ) { if ((!Tlchild)amp。amp。 (!Trchild)) count++。 // 對(duì)葉子結(jié)點(diǎn)計(jì)數(shù) CountLeaf( Tlchild, count)。 CountLeaf( Trchild, count)。 } // if } // CountLeaf int CountLeaf (BiTree T) { //返回指針 T所指二叉樹中所有葉子結(jié)點(diǎn)個(gè)數(shù) if (!T ) return 0。 if (!Tlchild amp。amp。 !Trchild) return 1。 else { m = CountLeaf( Tlchild)。 n = CountLeaf( Trchild)。 return (m+n)。 } //else } // CountLeaf int Count (BiTree T) { //返回指針 T所指二叉樹中所有結(jié)點(diǎn)個(gè)數(shù) if (!T ) return 0。 if (!Tlchild amp。amp。 !Trchild) return 1。 else { m = Count ( Tlchild)。 n = Count ( Trchild)。 return (m+n+1)。 } //else } //CountLeaf 求二叉樹的深度 (后序遍歷 ) 算法基本思想 :首先分析 二叉樹的深度 和它的 左 、 右子樹深度 之間的關(guān)系。 從二叉樹深度的定義可知， 二叉樹的深度應(yīng)為其左、右子樹深度的最大值加 1。由此， 需先分別求得左、右子樹的深度， 算法中訪問(wèn)結(jié)點(diǎn)的操作為 :求得左、右子樹深度的最大值，然后加 1 。 int Depth (BiTree T ) { // 返回二叉樹的深度 if (!T) depthval