【文章內(nèi)容簡介】 Pop(S,p)。 遍歷左子樹 if( !visit(pdata) ) return ERROR。 p=prchild。 } //else } // while 68 while ( p||!StackEmpty(S) ){ // 找到最左下的結(jié)點 if (p) { Push(S,p)。 p=plchild。 } // 根指針進棧，遍歷左子樹 else { //根指針退棧，訪問根結(jié)點， Pop(S,p)。 遍歷左子樹 if( !visit(pdata) ) return ERROR。 p=prchild。 } //else } // while p A B C D E F G i A 訪問： C B (5) A B C D E F G i A D 訪問： C B p (6) A B C D E F G i A D E 訪問： C B p (7) A B C D E F G i A D 訪問： C B E p (8) p=NULL pE pG 69 A B C D E F G i A D G 訪問： C B E P=NULL A B C D E F G i A 訪問： C B E G D p (11) A B C D E F G i A F 訪問： C B E G D p (12) A B C D E F G i A D 訪問： C B E G p while ( p||!StackEmpty(S) ){ // 找到最左下的結(jié)點 if (p) { Push(S,p)。 p=plchild。 } // 根指針進棧，遍歷左子樹 else { //根指針退棧，訪問根結(jié)點， Pop(S,p)。 遍歷左子樹 if( !visit(pdata) ) return ERROR。 p=prchild。 } //else } // while P=NULL P=NULL 70 A B C D E F G i A 訪問： C B E G D F pF p=NULL (13) A B C D E F G i 訪問： C B E G D F A p (14) A B C D E F G i 訪問： C B E G D F A p=NULL (15) while ( p||!StackEmpty(S) ){ // 找到最左下的結(jié)點 if (p) { Push(S,p)。 p=plchild。 } // 根指針進棧，遍歷左子樹 else { //根指針退棧，訪問根結(jié)點， Pop(S,p)。 遍歷左子樹 if( !visit(pdata) ) return ERROR。 p=prchild。 } //else } // while 71 void PreOrderTraverse (BiTree T, void (*visit) (TelemTypeamp。 e)) { InitStack(S)。 p=T。 while( p || !StackEmpty(S) ){ if (p) {if ( !visit(pdata) ) return ERROR。 // 訪問根結(jié)點 Push(S,p)。 p=plchild。 } // 根指針進棧，遍歷左子樹 else { //根指針退棧，遍歷右子樹 Pop(S,p)。 p=prchild。 } //else } // while return OK。 }// PreOrderTraverse 非遞歸先序遍歷二叉樹 72 五 、 遍歷算法的應用舉例 統(tǒng)計二叉樹中葉子結(jié)點的個數(shù) 求二叉樹的深度 建立二叉樹的存儲結(jié)構(gòu) 查詢二叉樹中某個結(jié) 點 73 Status Preorder_Seek (BiTree T, ElemType x, BiTree amp。p) {// 若二叉樹中存在和 x相同的元素，則 p指向該結(jié)點并返回 true if (T) { if (Tdata==x) { p=T。 return OK,} else { if (Preorder_Seek (Tlchild, x, p) return OK。 else return(Preorder_Seek (Trchild, x, p)) 。 }//else }//if else return FALSE。 } 74 統(tǒng)計二叉樹中葉子結(jié)點的個數(shù) 算法基本思想 : 先序 (或中序或后序 )遍歷二叉樹，在遍歷過程中查找葉子結(jié)點，并計數(shù)。 由此， 需在遍歷算法中增添一個“計數(shù)”的參數(shù)， 并將算法中“訪問結(jié)點” 的操作改為 :若是葉子，則計數(shù)器增 1。 75 void CountLeaf (BiTree T, intamp。 count){ if ( T ) { if ((!Tlchild)amp。amp。 (!Trchild)) count++。 // 對葉子結(jié)點計數(shù) CountLeaf( Tlchild, count)。 CountLeaf( Trchild, count)。 } // if } // CountLeaf 76 求二叉樹的深度 算法基本思想 : 從二叉樹深度的定義可知， 二叉樹的深度應為其左、右子樹深度的最大值加 1。由此， 需先分別求得左、右子樹的深度， 算法中 “ 訪問結(jié)點 ” 的操作為 :求得左、右子樹深度的最大值，然后加 1 。 首先分析 二叉樹的深度 和它的 左 、 右子樹深度 之間的關系。 77 int TreeDepth (BiTree T ){ // 返回二叉樹的深度 if ( !T ) depth = 0。 else { depthLeft = TreeDepth( Tlchild )。 depthRight= TreeDepth( Trchild )。 depth = 1 + (depthLeft depthRight ? depthLeft : depthRight)。 } return depth。 } 算法 78 建立二叉樹的存儲結(jié)構(gòu) 不同的定義方法對應不同的建立存儲結(jié)構(gòu)的算法 79 ? 按先序遍歷序列建二叉樹 ? 按給定的表達式建二叉樹 ? 由先序和中序序列建二叉樹 80 以先序遍歷序列的形式 根 左子樹 右子樹 定義一棵二叉樹 例如 : A B C D 以空白字符“ ”表示 A(B( ,C( , )),D( , )) 空樹 只含一個根結(jié)點的二叉樹 A 以字符串“ A ” 表示 以下列字符串表示 A B C D 算法 81 Status CreateBiTree(BiTree amp。T) { scanf(amp。ch)。 if (ch==39。 39。) T = NULL。 else { if (!(T = new BiTNode)) exit(OVERFLOW)。 Tdata = ch。 // 生成根結(jié)點 CreateBiTree(Tlchild)。 // 構(gòu)造左子樹 CreateBiTree(Trchild)。 // 構(gòu)造右子樹 } return OK。 } // CreateBiTree 82 A B C D B 上頁算法執(zhí)行過程舉例如下 : A T B C D ^ ^ ^ ^ ^ 83 A B C ? ? D E ? G ? ? F ? ? ? 練習：按先序遍歷序列建立二叉樹的二叉鏈表， 已知先序序列為： A B C D E F G 84 按給定的表達式建相應二叉樹 ? 由前綴表示式建樹 例如：已知表達式的前綴表示式 + a b c / d e ? 由原表達式建樹 例如：已知表達式 (a+b) c – d/e 85 對應前綴表達式 + a b c / d e的二叉樹 a b c d e + / 特點 ： 操作數(shù) 為 葉子 結(jié)點， 運算符 為 分支 結(jié)點 86 scanf(amp。ch)。 if ( In(ch, 字母集 )) 建葉子結(jié)點 。 else { 建根結(jié)點 。 遞歸建左子樹 。 遞歸建右子樹 。 } 由前綴表示式建樹的算法的基本操作： 87 a+b (a+b) c – d/e a+b c 分析表達式和二叉樹的關系 : a b + a b c + a b c + (a+b) c a b c d e + / 88 算法的 基本操作 : scanf(amp。ch)。 if (In(ch, 字母集 )) { 建葉子結(jié)點 。 入操作數(shù)棧 。 } else if (In(ch, 運算符集 )) { 和前一個運算符比較優(yōu)先級 。 若當前的優(yōu)先級“高”，則入運算符棧 。 否則建子樹 。 } PND S 89 void CrtExptree(BiTree amp。T, char exp[] ) { InitStack(S)。 Push(S, ??)。 InitStack(PND)。 p = exp。 ch = *p。 while (!(GetTop(S)==?? amp。amp。 ch==??)) { if (!IN(ch, OP)) CrtNode( t, ch )。 // 非運算符 ,即字母 ,建葉子結(jié)點并入棧 PND else { } if ( ch!= ?? ) { p++。 ch = *p。} } // while Pop(PND, T)。 } // CrtExptree … … 90 switch (ch) { case ?(? : Push(S, ch)。 break。 case ?)? : Pop(S, c)。 while (c!= ?(? ) { CrtSubtree( t, c)。 // 建子樹并入棧