【正文】 ( T ) { if ((!Tlchild)amp。 77 int TreeDepth (BiTree T ){ // 返回二叉樹的深度 if ( !T ) depth = 0。 if (ch==39。 } // 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ù) 為 葉子 結點， 運算符 為 分支 結點 86 scanf(amp。 if (In(ch, 字母集 )) { 建葉子結點 。 InitStack(PND)。} } // while Pop(PND, T)。 ( precede(c,ch))) { CrtSubtree( t, c)。 Push( PND, T )。 Push(PND, T)。 struct BiThrNode *lchild, *rchild。 103 rtag rightChild = = 0（右子女指針） = = 1（后繼線索） = = NULL 無此情況 無后繼 != NULL 后繼為當前結點右子樹的中序下的第一個結點 后繼為右子女結點 尋找當前結點在中序序列下的后繼 尋找當前結點在中序序列下的前驅 ltag LeftChild == 0（左子女指針） == 1（前驅線索） = = NULL 無此情況 無前驅 != NULL 前驅為當前結點左子樹中序下的最后一個結點 前驅為左子女結點 104 寫出中序線索二叉樹中找指針 p所指結點后繼的算法。amp。 // 左子樹線索化 if (!plchild) // 建前驅線索 { pLTag = Thread。 116 樹和森林 117 樹的三種存儲結構 一、 雙親表示法 （順序存儲） 二、 孩子鏈表表示法 三、 孩子 兄弟表示法 (二叉鏈表存儲） 118 A B C D E F G 0 A 1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 data parent 一、雙親表示法 : (順序存儲結構 ) 利用每個結點至多有一個雙親的性質(zhì)。 樹結構 : r=0 n=7 0 A 1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 121 A B C D E F G 二、孩子鏈表表示法 : 樹中每個結點可能包含多棵子樹， 所以可以采用 多叉鏈表 表示。較實用的方法是 為樹中每個結點建立一個孩子鏈表 ，而 n個頭指針又組成一個線性表，為了便于查找，可采用順序存儲結構。 // 孩子鏈的頭指針 } CTBox。 練習： A B C E D F G I H 孩子 兄弟表示法 130 樹、森林和二叉樹的對應關系 (一 ) 樹與二叉樹之間的轉換 二叉樹和樹都可以用二叉鏈表作為存儲結構。 森林轉換成二叉樹的規(guī)則 135 H D G F C I E B J 如： J H D G F C I E B J H D G F I E B C 136 H D G F C I E B J 以上我們給出了：樹和森林轉化為二叉樹的規(guī)則， 那么二叉樹如何轉化為樹或森林？看下面例子： 二叉樹轉換成樹或森林的規(guī)則 若結點 x是其雙親 p的左孩子，則把 x的右孩子、右孩子的右孩子、 …… 都與 p用線連起來。 140 層次遍歷時頂點的訪問序列： A B C D E F G H I J K 先根遍歷時頂點的訪問序列： A B E F C D G H I J K 后根遍歷時頂點的訪問序列： E F B C I J K H G D A A B C D E F G H I J K 141 若森林不空，則 訪問 森林中第一棵樹的根結點 。 143 樹、森林的遍歷和二叉樹遍歷的對應關系 ？ 先根遍歷 后根遍歷 樹 二叉樹 森林 先序遍歷 先序遍歷 中序遍歷 中序遍歷 144 A B C D E F G H I J K L M N O 先序遍歷： 后序遍歷： 層次遍歷： A B E F I G C D H J K L N O M E I F G B C J K N O L M H D A A B C D E F G H I J K L M N O 寫出下面樹的先根、后根及按層次遍歷的遍歷序列。 a60 a90 a80 a70 E Y N D Y N C Y N B Y N A 等級 分數(shù)段 比例 A B C D E 0~59 60~69 70~79 80~89 90~100 5% 15% 40% 30% 10% 設實際學生成績的分布規(guī)律如下： (設成績?yōu)? a) 引例 ： 百分制成績轉換成五級分制成績 等級分數(shù)段比例ABCDE0~ 59 60~ 69 70~ 79 80~ 89 90~ 1000. 05 0. 15 0. 40 0. 30 0. 10等級分數(shù)段比例如何設計程序才能使得 比較的總次數(shù) 最少 ？ 問題： 程序執(zhí)行的時間 ,與什么因素有關？ CPU的處理速度 (硬件因素 )； 程序中執(zhí)行基本運算的次數(shù) ,即比較的次數(shù) (軟件因素 )。 先序遍歷 森林中 (除第一棵樹之外 )其 余樹構成的森林。最后作適當?shù)恼{(diào)整即可。這樣就可以得到二叉樹與樹之間的對應關系。 int n, r。 Ⅳ. 為了方便各種操作，可以把雙親表示法和孩子表示法結合起來，即 帶雙親的孩子鏈表 。但由于樹中很多結點的度都小于 d，一棵度為 d且含有 n個結點的樹必有 ？ 個空指針域。 119 typedef struct PTNode { TElemType data。 } if (!prerchild) // 建后繼線索 { preRTag = Thread。 Visit(pdata)。 //從 *p的右孩子開始查找 while (!qltag) q=qlchild。 // 左右標志 } BiThrNode, *BiThrTree。 例如 : 先序序列 : 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 若利用二叉鏈表存儲二叉樹，則含 n個結點的二叉鏈表中有 (n+1) 個空指針域，利用這些指針域指向所在結點在某線性序列中的“前驅”或 “后繼” ，以便 于某些操作。 T, char c) { if (!(T= new BiTNode)) exit(OVERFLOW)。 } if ( ch!= ?? ) Push( S, ch)。 break。 ch = *p。 } else if (In(ch, 運算符集 )) { 和前一個運算符比較優(yōu)先級 。 if ( In(ch, 字母集 )) 建葉子結點 。) T = NULL。 depthRight= TreeDepth( Trchild )。 (!Trchild)) count++。 return OK,} else { if (Preorder_Seek (Tlchild, x, p) return OK。 while( p || !StackEmpty(S) ){ if (p) {if ( !visit(pdata) ) return ERROR。 } //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) ){ // 找到最左下的結點 if (p) { Push(S,p)。 } // 根指針進棧，遍歷左子樹 else { //根指針退棧，訪問根結點， Pop(S,p)。 } //else } // while return OK。 先序序列： A B D C 遞歸算法的執(zhí)行過程 T 65 a b c d e + / 如圖二叉樹表示表達式 : ( a + b ) c – d / e 二叉樹的先序遍歷序列為： – + a b c / d e 二叉樹的中序遍歷序列為： a + b c – d / e 二叉樹的后序遍歷序列為： a b + c d e / – 前綴表達式 中綴表達式 后綴表達式 二叉樹與表達式 66 void InOrderTraverse (BiTree T, void (*visit) (TelemTypeamp。 T A printf(A)。 DispLeaf(brchild)。 // 訪問結點 PreOrder(Tlchild, Visit)。 一、問題的提出 “訪問 ”的含義可以很廣， 如：輸出結點的信息等。 struct BiTNode *lchild, *rchild。 特點 : (1)葉子結點只可能在層次最底的兩層上出現(xiàn) .(2)對任一結點，若其右分支下子孫的最大層次為 l， 則其左分支下子孫的最大層次必為 l 或 l+1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 a b c d e f g h i j 37 證明： 設 完全二叉樹的深度為 k 即 k1 ≤ log2 n k 因為 k 只能是整數(shù)，因此， k = ?