【文章內(nèi)容簡介】 F G i A D 訪問： C B E G p while ( p||!StackEmpty(S) ){ // 找到最左下的結(jié)點(diǎn) if (p) { Push(S,p)。 p=plchild。 } // 根指針進(jìn)棧，遍歷左子樹 else { //根指針退棧，訪問根結(jié)點(diǎn)， Pop(S,p)。 遍歷左子樹 if( !visit(pdata) ) return ERROR。 p=prchild。 } //else } // while P=NULL P=NULL 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é)點(diǎn) if (p) { Push(S,p)。 p=plchild。 } // 根指針進(jìn)棧，遍歷左子樹 else { //根指針退棧，訪問根結(jié)點(diǎn)， Pop(S,p)。 遍歷左子樹 if( !visit(pdata) ) return ERROR。 p=prchild。 } //else } // while void PreOrderTraverse (BiTree T, void (*visit) (TelemTypeamp。 e)) { InitStack(S)。 p=T。 while( p || !StackEmpty(S) ){ if (p) {if ( !visit(pdata) ) return ERROR。 // 訪問根結(jié)點(diǎn) Push(S,p)。 p=plchild。 } // 根指針進(jìn)棧，遍歷左子樹 else { //根指針退棧，遍歷右子樹 Pop(S,p)。 p=prchild。 } //else } // while return OK。 }// PreOrderTraverse 非遞歸先序遍歷二叉樹 五 、 遍歷算法的應(yīng)用舉例 統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù) 求二叉樹的深度 建立二叉樹的存儲結(jié)構(gòu) 查詢二叉樹中某個(gè)結(jié) 點(diǎn) Status Preorder_Seek (BiTree T, ElemType x, BiTree amp。p) {// 若二叉樹中存在和 x相同的元素，則 p指向該結(jié)點(diǎn)并返回 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。 } 統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù) 算法基本思想 : 先序 (或中序或后序 )遍歷二叉樹，在遍歷過程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。 由此， 需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)， 并將算法中“訪問結(jié)點(diǎn)” 的操作改為 :若是葉子，則計(jì)數(shù)器增 1。 void CountLeaf (BiTree T, intamp。 count){ if ( T ) { if ((!Tlchild)amp。amp。 (!Trchild)) count++。 // 對葉子結(jié)點(diǎn)計(jì)數(shù) CountLeaf( Tlchild, count)。 CountLeaf( Trchild, count)。 } // if } // CountLeaf 算法一 int CountLeaf (BiTree T){ if (!T ) return 0。 if (!Tlchild amp。amp。 !Trchild) return 1。 else{ m = CountLeaf( Tlchild)。 n = CountLeaf( Trchild)。 return (m+n)。 } //else } // CountLeaf 算法二 123456789 求二叉樹的深度 算法基本思想 : 從二叉樹深度的定義可知， 二叉樹的深度應(yīng)為其左、右子樹深度的最大值加 1。由此， 需先分別求得左、右子樹的深度， 算法中 “ 訪問結(jié)點(diǎn) ” 的操作為 :求得左、右子樹深度的最大值，然后加 1 。 首先分析 二叉樹的深度 和它的 左 、 右子樹深度 之間的關(guān)系。 int TreeDepth (BiTree T ){ // 返回二叉樹的深度 if ( !T ) depth = 0。 else { depthLeft = TreeDepth( Tlchild )。 depthRight= TreeDepth( Trchild )。 depth = 1 + (depthLeft depthRight ? depthLeft : depthRight)。 } return depth。 } 算法 建立二叉樹的存儲結(jié)構(gòu) 不同的定義方法對應(yīng)不同的建立存儲結(jié)構(gòu)的算法 ? 按先序遍歷序列建二叉樹 ? 按給定的表達(dá)式建二叉樹 ? 由先序和中序序列建二叉樹 作業(yè) 以先序遍歷序列的形式 根 左子樹 右子樹 定義一棵二叉樹 例如 : A B C D 以空白字符“ ”表示 A(B( ,C( , )),D( , )) 空樹 只含一個(gè)根結(jié)點(diǎn)的二叉樹 A 以字符串“ A ” 表示 以下列字符串表示 A B C D 算法 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 上頁算法執(zhí)行過程舉例如下 : A T B C D ^ ^ ^ ^ ^ A B C ? ? D E ? G ? ? F ? ? ? 練習(xí)：按先序遍歷序列建立二叉樹的二叉鏈表， 已知先序序列為： A B C D E F G 按給定的表達(dá)式建相應(yīng)二叉樹 ? 由前綴表示式建樹 例如：已知表達(dá)式的前綴表示式 + a b c / d e ? 由原表達(dá)式建樹 例如：已知表達(dá)式 (a+b) c – d/e 對應(yīng)前綴表達(dá)式 + a b c / d e的二叉樹 a b c d e + / 特點(diǎn) ： 操作數(shù) 為 葉子 結(jié)點(diǎn)， 運(yùn)算符 為 分支 結(jié)點(diǎn) scanf(amp。ch)。 if ( In(ch, 字母集 )) 建葉子結(jié)點(diǎn) 。 else { 建根結(jié)點(diǎn) 。 遞歸建左子樹 。 遞歸建右子樹 。 } 由前綴表示式建樹的算法的基本操作： a+b (a+b) c – d/e a+b c 分析表達(dá)式和二叉樹的關(guān)系 : a b + a b c + a b c + (a+b) c a b c d e + / 算法的 基本操作 : scanf(amp。ch)。 if (In(ch, 字母集 )) { 建葉子結(jié)點(diǎn) 。 入操作數(shù)棧 。 } else if (In(ch, 運(yùn)算符集 )) { 和前一個(gè)運(yùn)算符比較優(yōu)先級 。 若當(dāng)前的優(yōu)先級“高”，則入運(yùn)算符棧 。 否則建子樹 。 } PND S 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 )。 // 非運(yùn)算符 ,即字母 ,建葉子結(jié)點(diǎn)并入棧 PND else { } if ( ch!= ?? ) { p++。 ch = *p。} } // while Pop(PND, T)。 } // CrtExptree … … switch (ch) { case ?(? : Push(S, ch)。 break。 case ?)? : Pop(S, c)。 while (c!= ?(? ) { CrtSubtree( t, c)。 // 建子樹并入棧 PND Pop(S, c) } break。 defult : } // switch … … while(!Gettop(S, c) amp。amp。 ( precede(c,ch))) { CrtSubtree( t, c)。 // 建子樹并入棧 PND Pop(S, c)。 } if ( ch!= ?? ) Push( S, ch)。 break。 //棧頂元素 c優(yōu)先級 高于 當(dāng)前運(yùn)算符 ch 建葉子結(jié)點(diǎn)的算法為： void CrtNode(BiTreeamp。 T,char ch) { if (!(T= new BiTNode)) exit(OVERFLOW)。 Tdata = char。 Tlchild = Trchild = NULL。 Push( PND, T )。 } 建子樹的算法為： void CrtSubtree (Bitreeamp。 T, char c) { if (!(T= new BiTNode)) exit(OVERFLOW)。 Tdata = c。 Pop(PND, rc)。 Trchild = rc。 Pop(PND, lc)。 Tlchild = lc。 Push(PND, T)。 } 僅知二叉樹的先序序列“ abcdefg” 不能唯一確定一棵二叉樹， 由二叉樹的先序和中序序列建樹