【正文】 F G H K 對 線索鏈表 中結點的約定： 在二叉鏈表的結點中 增加兩個標志域 ， 并作如下規(guī)定： 若該結點的左子樹不空 ， 則 Lchild域的指針指向其左子樹， 且左標志域的值為 “ 指針 Link‖(0) ； 否則 ， Lchild域的指針指向其“前驅”， 且左標志域的值為 “ 線索 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 若利用二叉鏈表存儲二叉樹，則含 n個結點的二叉鏈表中有 (n+1) 個空指針域，利用這些指針域指向所在結點在某線性序列中的“前驅”或 “后繼” ，以便 于某些操作。 ： abc， 問有幾種形態(tài)的二叉樹可得到此遍歷結果？ 。 ：中序序列： BDCEAFHG 后序序列： DECBHGFA , 畫出二叉樹。 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)先級 高于 當前運算符 ch 建葉子結點的算法為： void CrtNode(BiTreeamp。 } if ( ch!= ?? ) Push( S, ch)。 ( precede(c,ch))) { CrtSubtree( t, c)。 defult : } // switch … … while(!Gettop(S, c) amp。 while (c!= ?(? ) { CrtSubtree( t, c)。 break。} } // while Pop(PND, T)。 // 非運算符 ,即字母 ,建葉子結點并入棧 PND else { } if ( ch!= ?? ) { p++。amp。 ch = *p。 InitStack(PND)。T, char exp[] ) { InitStack(S)。 否則建子樹 。 } else if (In(ch, 運算符集 )) { 和前一個運算符比較優(yōu)先級 。 if (In(ch, 字母集 )) { 建葉子結點 。 } 由前綴表示式建樹的算法的基本操作： 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 + / 算法的 基本操作 : scanf(amp。 遞歸建左子樹 。 if ( In(ch, 字母集 )) 建葉子結點 。 } // CreateBiTree A B C D B 上頁算法執(zhí)行過程舉例如下 : A T B C D ^ ^ ^ ^ ^ A B C ? ? D E ? G ? ? F ? ? ? 練習：按先序遍歷序列建立二叉樹的二叉鏈表， 已知先序序列為： A B C D E F G 按給定的表達式建相應二叉樹 ? 由前綴表示式建樹 例如：已知表達式的前綴表示式 + a b c / d e ? 由原表達式建樹 例如：已知表達式 (a+b) c – d/e 對應前綴表達式 + a b c / d e的二叉樹 a b c d e + / 特點 ： 操作數(shù) 為 葉子 結點， 運算符 為 分支 結點 scanf(amp。 // 構造左子樹 CreateBiTree(Trchild)。 Tdata = ch。) T = NULL。 if (ch==39。T) { scanf(amp。 } return depth。 depthRight= TreeDepth( Trchild )。 int TreeDepth (BiTree T ){ // 返回二叉樹的深度 if ( !T ) depth = 0。由此， 需先分別求得左、右子樹的深度， 算法中 “ 訪問結點 ” 的操作為 :求得左、右子樹深度的最大值，然后加 1 。 return (m+n)。 else{ m = CountLeaf( Tlchild)。amp。 } // if } // CountLeaf 算法一 int CountLeaf (BiTree T){ if (!T ) return 0。 // 對葉子結點計數(shù) CountLeaf( Tlchild, count)。amp。 void CountLeaf (BiTree T, intamp。 } 統(tǒng)計二叉樹中葉子結點的個數(shù) 算法基本思想 : 先序 (或中序或后序 )遍歷二叉樹，在遍歷過程中查找葉子結點，并計數(shù)。 else return(Preorder_Seek (Trchild, x, p)) 。p) {// 若二叉樹中存在和 x相同的元素，則 p指向該結點并返回 true if (T) { if (Tdata==x) { p=T。 } //else } // while return OK。 } // 根指針進棧，遍歷左子樹 else { //根指針退棧，遍歷右子樹 Pop(S,p)。 // 訪問根結點 Push(S,p)。 p=T。 } //else } // while void PreOrderTraverse (BiTree T, void (*visit) (TelemTypeamp。 遍歷左子樹 if( !visit(pdata) ) return ERROR。 p=plchild。 p=prchild。 } // 根指針進棧，遍歷左子樹 else { //根指針退棧，訪問根結點， Pop(S,p)。 } //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 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) ){ // 找到最左下的結點 if (p) { Push(S,p)。 遍歷左子樹 if( !visit(pdata) ) return ERROR。 p=plchild。 p=prchild。 } // 根指針進棧，遍歷左子樹 else { //根指針退棧，訪問根結點， Pop(S,p)。 }// InOrderTraverse 四、中序遍歷算法的非遞歸描述 非遞歸算法的執(zhí)行過程 A B C D E F G p i A (1) A B C D E F G p i A B (2) A B C D E F G p i A B C (3) p=NULL pC p=NULL A B C D E F G i A B 訪問： C (4) while ( p||!StackEmpty(S) ){ // 找到最左下的結點 if (p) { Push(S,p)。 p=prchild。 } // 根指針進棧，遍歷左子樹 else { //根指針退棧，訪問根結點，遍歷右子樹 Pop(S,p)。 while( p || !StackEmpty(S) ){ // 找到最左下的結點 if (p) { Push(S,p)。 e)) { InitStack(S)。 T 左是空返回 T 右是空返回 T 左是空返回 T 右是空返回 pre(T R)。 pre(T L)。 pre(T L)。 pre(T L)。 pre(T L)。 返回 返回 pre(T R)。 pre(trchild)。// 遍歷右子樹 } } void pre(BiTree t) { if (t!=NULL) { printf (%d\t,tdata)。 // 訪問結點 PreOrder(Tlchild, Visit)。 后 （根） 序的遍歷算法： 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 分 析 ： 先序序列： 中序序列： 后序序列： 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 作業(yè) 三、算法的遞歸描述 void PreOrder (BiTree T, void( *visit)(TElemTypeamp。 先 （根） 序的遍歷算法： A D B C D L R A D L R D L R B D C D L R 先序遍歷序列： A B D C 先序遍歷 : 若二叉樹為空樹，則空操作；否則， （ 1）中序遍歷左子樹； （ 2）訪問根結點； （ 3）中序遍歷右子樹。 對 “ 二叉樹 ” 而