【正文】 struct TriTNode *lchild, *rchild。 一、問(wèn)題的提出 “訪問(wèn) ”的含義可以很廣，如：輸出結(jié) 點(diǎn)的信息等。 二、先左后右的遍歷算法 先 （根）序的遍歷算法 中 （根）序的遍歷算法 后 （根）序的遍歷算法 若二叉樹(shù)為空樹(shù)，則空操作；否則， （ 1）訪問(wèn)根結(jié)點(diǎn)； （ 2）先序遍歷左子樹(shù)； （ 3）先序遍歷右子樹(shù)。 e)) { // 先序遍歷二叉樹(shù) if (T) { visit(Tdata)。 push(S,T)。 pop(S,p)。} return OK。p=plchild。 } 五 、 遍歷算法的應(yīng)用舉例 統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù) (先序遍歷 ) 求二叉樹(shù)的深度 (后序遍歷 ) 建立二叉樹(shù) 統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù) 算法基本思想 : 先序 (或中序或后序 )遍歷二叉樹(shù)，在遍歷過(guò)程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。amp。 } // if } // CountLeaf 求二叉樹(shù)的深度 (后序遍歷 ) 算法基本思想 : 從二叉樹(shù)深度的定義可知， 二叉樹(shù)的深度應(yīng)為其左、右子樹(shù)深度的最大值加 1。 else { depthLeft = Depth( Tlchild )。 } 不同的定義方法相應(yīng)有不同的存儲(chǔ)結(jié)構(gòu)的建立算法 建立二叉樹(shù) （ 1） 以字符串的形式 根 左子樹(shù) 右子樹(shù) 定義一棵二叉樹(shù) 例如 : A B C D 以空白字符“ ”表示 A(B( ,C( , )),D( , )) 空樹(shù) 只含一個(gè)根結(jié)點(diǎn)的二叉樹(shù) A 以字符串“ A ” 表示 以下列字符串表示 Status CreateBiTree(BiTree amp。 39。 // 生成根結(jié)點(diǎn) CreateBiTree(Tlchild)。ch)。 遞歸建右子樹(shù) 。 暫存 。 } void CrtExptree(BiTree amp。 p = exp。 ch==??)) { if (!IN(ch, OP)) CrtNode( t, ch )。 } // CrtExptree … … switch (ch) { case ?(? : Push(S, ch)。 // 建二叉樹(shù)并入棧 Pop(S, c) } break。 Pop(S, c)。 T,char ch) { T=(BiTNode*)malloc(sizeof(BiTNode))。 } 建子樹(shù)的算法為： void CrtSubtree (Bitreeamp。 Trchild = rc。 } 僅知二叉樹(shù)的先序序列“ abcdefg” 不能唯一 確定一棵二叉樹(shù)， （ 3）由二叉樹(shù)的先序和中序序列建樹(shù) 如果同時(shí)已知二叉樹(shù)的中序序列“ cbdaegf”， 則會(huì)如何？ 二叉樹(shù)的先序序列 二叉樹(shù)的中序序列 左子樹(shù) 左子樹(shù) 右子樹(shù) 右子樹(shù) 根 根 a b c d e f g c b d a e g f 例如 : a a b b c c d d e e f fg a b c d e f g ^ ^ ^ ^ ^ ^ ^ ^ 先序序列中序序列 void CrtBT(BiTreeamp。 else { } } // } // CrtBT … … T=(BiTNode*)malloc(sizeof(BiTNode))。 if (k=is+n1) TRchild = NULL。 若該結(jié)點(diǎn)的右子樹(shù)不空， 則 rchild域的指針指向其右子樹(shù)， 且右標(biāo)志域的值為 “ 指針 Link”； 否則， rchild域的指針指向其“后繼”， 且右標(biāo)志的值為“ 線索 Thread”。 // 雙親位置域 } PTNode。 樹(shù)結(jié)構(gòu) : 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 r=0 n=6 data firstchild 1 2 3 4 5 6 二、孩子鏈表表示法 : 4 typedef struct CTNode { int child。 ChildPtr firstchild。 // 結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置 } CTree。 C語(yǔ)言的類(lèi)型描述 : 結(jié)點(diǎn)結(jié)構(gòu) : firstchild data nextsibling 森林和二叉樹(shù)的對(duì)應(yīng)關(guān)系 設(shè) 森林 F = ( T1, T2, …, T n )。 由二叉樹(shù)轉(zhuǎn)換為森林 的轉(zhuǎn)換規(guī)則為： 若 B = Φ， 則 F = Φ； 否則， 由 Node(root) 對(duì)應(yīng)得到 ROOT( T1 )； 由 LBT 對(duì)應(yīng)得到 ( t11, t12, … ， t1m)； 由 RBT 對(duì)應(yīng)得到 (T2, T3, …, T n)。 若樹(shù)不空，則先依次后根遍歷各棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)。 即： 依次從左至右 對(duì)森林中的每一棵樹(shù) 進(jìn)行 先根遍歷 。 結(jié)點(diǎn)的路徑長(zhǎng)度 定義為： 從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上 分支的數(shù)目。 (3) (4) 9 例如 : 已知權(quán)值 W={ 5, 6, 2, 9, 7 } 5 6 2 7 5 2 7 6 9 7 6 7 13 9 5 2 7 6 7 13 9 5 2 7 9 5 2 7 16 6 7 13 29 0 0 0 0 1 1 1 1 00 01 10 110 111 指的是， 任何一個(gè)字符的編碼都 不是同一字符集中另一個(gè)字符的編碼 的前綴 。 3. 遍歷二叉樹(shù)是二叉樹(shù)各種操作的基礎(chǔ)。 4. 理解二叉樹(shù)線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟練掌握二叉樹(shù)的線索化過(guò)程以及在中序線索化樹(shù)上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。 6. 學(xué)會(huì)編寫(xiě)實(shí)現(xiàn)樹(shù)的各種操作的算法。 A）圖（ a） B）圖（ b） C）圖（ c） D）圖（ d） （ a） （ b） （ c） （ d） 在一棵二叉樹(shù)中，雙分支的結(jié)點(diǎn)數(shù)為 15，單分支結(jié)點(diǎn)數(shù)為 30， 則葉子結(jié)點(diǎn)數(shù)為 ________。 A） abdgcefh B） dgbaechf C） gdbehfca D） abcdefgh 深度為 5的二叉樹(shù)至多有 ____________________個(gè)結(jié)點(diǎn)。 A） n在 m右方 B） n是 m祖先 C） n在 m左方 D） n是 m子孫 1有 n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為 ____________________。在同一個(gè)結(jié)點(diǎn)的左、右孩子中，其左孩子的編號(hào)小于 其右孩子的編號(hào)，則可采用 __________遍歷實(shí)現(xiàn)編號(hào)。 已知一棵二叉樹(shù)的中序遍歷序列為 DBEHAFCIG，后序遍歷序列為 DHEBFIGCA，該二叉樹(shù)的前序序列為 _______________，層次遍歷序 列是 _____________________。 （ 1）已知一棵二叉樹(shù)的前序序列和中序序列分別為 ABDGHCEFI和 GDHBAECIF，請(qǐng)畫(huà)出此二叉樹(shù)。 對(duì)如下圖所示的森林： （ 1）求各樹(shù)的前序序列和后序序列； （ 2）求森林的前序序列和后序序列； （ 3）將此森林轉(zhuǎn)換為相應(yīng)的二叉樹(shù)； （ 4）給出（ a）所示樹(shù)的雙親鏈表表示、孩子鏈表表示、帶雙親的孩子 鏈表表示及孩子兄弟鏈表表示等四種存儲(chǔ)結(jié)構(gòu)，并指出哪些存儲(chǔ)結(jié)構(gòu)易 于求指定結(jié)點(diǎn)的祖先，哪些易于求指定結(jié)點(diǎn)的后代？ F C D E B A K H I J G O L M N Q P R （ a） （ b） （ c） 畫(huà)出如下圖所示的二叉樹(shù)所對(duì)應(yīng)的森林。 （ 2）畫(huà)出該二叉樹(shù)的中序線索二叉樹(shù)。 設(shè)一棵二叉樹(shù)的先序遍歷序列為 ABDFCEGH，中序遍歷序列 為 BFDAGEHC。