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