【正文】 e(T)。 // 左右標(biāo)志 } BiThrNode, *BiThrTree。 struct BiThrNode *lchild, *rchild。 如此定義的二叉樹的存儲(chǔ)結(jié)構(gòu)稱作“ 線索鏈表 ”。 與其相應(yīng)的二叉樹，稱作 “ 線索二叉樹 ” 包含 “線索” 的存儲(chǔ)結(jié)構(gòu)，稱作 “ 線索鏈表 ” A B C D E F G H K （先序序列） ^ D ^ C ^ ^ B E ^ A B C D E F G H K 99 對(duì) 線索鏈表 中結(jié)點(diǎn)的約定： 在二叉鏈表的結(jié)點(diǎn)中 增加兩個(gè)標(biāo)志域 ， 并作如下規(guī)定： 若該結(jié)點(diǎn)的左子樹不空 ， 則 Lchild域的指針指向其左子樹， 且左標(biāo)志域的值為 “ 指針 Link‖(0) ； 否則 ， Lchild域的指針指向其“前驅(qū)”， 且左標(biāo)志域的值為 “ 線索 Thread‖(1) 。 例如 : 先序序列 : A B C D E F G H K 中序序列 : B D C A H G K F E 后序序列 : D C B H K G F E A A B C D E F G H K 98 若利用二叉鏈表存儲(chǔ)二叉樹，則含 n個(gè)結(jié)點(diǎn)的二叉鏈表中有 (n+1) 個(gè)空指針域，利用這些指針域指向所在結(jié)點(diǎn)在某線性序列中的“前驅(qū)”或 “后繼” ，以便 于某些操作。 Push(PND, T)。 Pop(PND, lc)。 Pop(PND, rc)。 T, char c) { if (!(T= new BiTNode)) exit(OVERFLOW)。 Push( PND, T )。 Tdata = char。 //棧頂元素 c優(yōu)先級(jí) 高于 當(dāng)前運(yùn)算符 ch 92 建葉子結(jié)點(diǎn)的算法為： void CrtNode(BiTreeamp。 } if ( ch!= ?? ) Push( S, ch)。 ( precede(c,ch))) { CrtSubtree( t, c)。 defult : } // switch … … 91 while(!Gettop(S, c) amp。 while (c!= ?(? ) { CrtSubtree( t, c)。 break。} } // while Pop(PND, T)。 // 非運(yùn)算符 ,即字母 ,建葉子結(jié)點(diǎn)并入棧 PND else { } if ( ch!= ?? ) { p++。amp。 ch = *p。 InitStack(PND)。T, char exp[] ) { InitStack(S)。 否則建子樹 。 } else if (In(ch, 運(yùn)算符集 )) { 和前一個(gè)運(yùn)算符比較優(yōu)先級(jí) 。 if (In(ch, 字母集 )) { 建葉子結(jié)點(diǎn) 。 } 由前綴表示式建樹的算法的基本操作： 87 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 + / 88 算法的 基本操作 : scanf(amp。 遞歸建左子樹 。 if ( In(ch, 字母集 )) 建葉子結(jié)點(diǎn) 。 } // CreateBiTree 82 A B C D B 上頁算法執(zhí)行過程舉例如下 : A T B C D ^ ^ ^ ^ ^ 83 A B C ? ? D E ? G ? ? F ? ? ? 練習(xí)：按先序遍歷序列建立二叉樹的二叉鏈表， 已知先序序列為： A B C D E F G 84 按給定的表達(dá)式建相應(yīng)二叉樹 ? 由前綴表示式建樹 例如：已知表達(dá)式的前綴表示式 + a b c / d e ? 由原表達(dá)式建樹 例如：已知表達(dá)式 (a+b) c – d/e 85 對(duì)應(yīng)前綴表達(dá)式 + a b c / d e的二叉樹 a b c d e + / 特點(diǎn) ： 操作數(shù) 為 葉子 結(jié)點(diǎn)， 運(yùn)算符 為 分支 結(jié)點(diǎn) 86 scanf(amp。 // 構(gòu)造左子樹 CreateBiTree(Trchild)。 Tdata = ch。) T = NULL。 if (ch==39。T) { scanf(amp。 } return depth。 depthRight= TreeDepth( Trchild )。 77 int TreeDepth (BiTree T ){ // 返回二叉樹的深度 if ( !T ) depth = 0。由此， 需先分別求得左、右子樹的深度， 算法中 “ 訪問結(jié)點(diǎn) ” 的操作為 :求得左、右子樹深度的最大值，然后加 1 。 CountLeaf( Trchild, count)。 (!Trchild)) count++。 count){ if ( T ) { if ((!Tlchild)amp。 由此， 需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)， 并將算法中“訪問結(jié)點(diǎn)” 的操作改為 :若是葉子，則計(jì)數(shù)器增 1。 }//else }//if else return FALSE。 return OK,} else { if (Preorder_Seek (Tlchild, x, p) return OK。 }// PreOrderTraverse 非遞歸先序遍歷二叉樹 72 五 、 遍歷算法的應(yīng)用舉例 統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù) 求二叉樹的深度 建立二叉樹的存儲(chǔ)結(jié)構(gòu) 查詢二叉樹中某個(gè)結(jié) 點(diǎn) 73 Status Preorder_Seek (BiTree T, ElemType x, BiTree amp。 p=prchild。 p=plchild。 while( p || !StackEmpty(S) ){ if (p) {if ( !visit(pdata) ) return ERROR。 e)) { InitStack(S)。 p=prchild。 } // 根指針進(jìn)棧，遍歷左子樹 else { //根指針退棧，訪問根結(jié)點(diǎn)， Pop(S,p)。 } //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é)點(diǎn) if (p) { Push(S,p)。 遍歷左子樹 if( !visit(pdata) ) return ERROR。 p=plchild。 p=prchild。 } // 根指針進(jìn)棧，遍歷左子樹 else { //根指針退棧，訪問根結(jié)點(diǎn)， Pop(S,p)。 } //else } // while 68 while ( p||!StackEmpty(S) ){ // 找到最左下的結(jié)點(diǎn) if (p) { Push(S,p)。 遍歷左子樹 if( !visit(pdata) ) return ERROR。 p=plchild。 } //else } // while return OK。 if ( !visit(pdata) ) return ERROR。 p=plchild。 p=T。 先序序列： A B D C 遞歸算法的執(zhí)行過程 T 65 a b c d e + / 如圖二叉樹表示表達(dá)式 : ( a + b ) c – d / e 二叉樹的先序遍歷序列為： – + a b c / d e 二叉樹的中序遍歷序列為： a + b c – d / e 二叉樹的后序遍歷序列為： a b + c d e / – 前綴表達(dá)式 中綴表達(dá)式 后綴表達(dá)式 二叉樹與表達(dá)式 66 void InOrderTraverse (BiTree T, void (*visit) (TelemTypeamp。 返回 T 左是空返回 pre(T R)。 T C printf(C)。 T D printf(D)。 T A printf(A)。 A C B D T B printf(B)。 } } 主程序 Pre( T ) 返回 返回 pre(T R)。 pre(tlchild)。 DispLeaf(brchild)。 brchild==NULL) printf(%c ,bdata)。f(brchild) 其他情況 63 void DispLeaf(BTNode *b) { if (b!=NULL) { if (blchild==NULL amp。// 遍歷右子樹 } } 62 例 假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ) ,試設(shè)計(jì)一個(gè)算法 ,輸出一棵給定二叉樹的所有葉子結(jié)點(diǎn) 。 // 訪問結(jié)點(diǎn) PreOrder(Tlchild, Visit)。 后 （根） 序的遍歷算法： 59 A D B C L R D L R D L R D A D C L R D 后序遍歷序列： D B C A 后序遍歷 : B 60 A B C D E F G H K 分 析 ： 先序序列： 中序序列： 后序序列： 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 61 三、算法的遞歸描述 void PreOrder (BiTree T, void( *visit)(TElemTypeamp。 先 （根） 序的遍歷算法： 55 A D B C D L R A D L R D L R B D C D L R 先序遍歷序列： A B D C 先序遍歷 : 56