【正文】 將森林中的每棵樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的二叉樹(shù)； 按照給出的森林中樹(shù)的次序，依次將 后一棵二叉樹(shù)插入 為前一棵 二叉樹(shù)根結(jié)點(diǎn) 的右子樹(shù) ； G H I J A B C D E F A B D C F E G H I J A B D C F E G H I J 86 二叉樹(shù)轉(zhuǎn)化成樹(shù) 前提：二叉樹(shù)的根結(jié)點(diǎn) 無(wú)右孩子 加線 ：若某結(jié)點(diǎn) i是雙親結(jié)點(diǎn)的左孩子，則將該結(jié)點(diǎn)的右孩子以及連續(xù)地沿著此右孩子的 右鏈 不斷搜索到的所有右孩子都分別與結(jié)點(diǎn) i的 雙親用虛線連起來(lái) 。 ?以根結(jié)點(diǎn)為軸；左孩子不再旋轉(zhuǎn)。 【 注意 】 ： 和樹(shù)對(duì)應(yīng)的二叉樹(shù)，其左、右子樹(shù)的概念已改變?yōu)椋? 左是孩子，右是兄弟 。 結(jié)點(diǎn)結(jié)構(gòu) : firstchild data nextsibling 三、樹(shù)的二叉鏈表 (孩子 兄弟）存儲(chǔ)表示法 孩子兄弟表示法 又稱(chēng) 二叉鏈表表示法 ，表中每個(gè)結(jié)點(diǎn)設(shè)有兩個(gè)鏈域，分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟（右兄弟）結(jié)點(diǎn)。 struct CSNode *firstchild, *nextsibling。 n個(gè)結(jié)點(diǎn)的數(shù)據(jù) 和 n個(gè)孩子鏈表的頭指針又 組成一個(gè)順序表 。 75 通常是把 每個(gè)結(jié)點(diǎn)的孩子 結(jié)點(diǎn)排列起來(lái)， 構(gòu)成一個(gè)單鏈表 ，稱(chēng)為孩子鏈表。 先序序列： E B A D C F H G I K J 中序序列： A B C D E F G H I J K E B A D F H G 后序序列： A C D B G J K I H F E C I K J 70 由遍歷序列確定二叉樹(shù) 由 中序 和 后序 序列恢復(fù)二叉樹(shù) 中序序列： D C B G E A H F I J K 后序序列： D C E G B F H K J I A A 練習(xí)： I J K H F B G E C D 71 樹(shù)、森林和二叉數(shù)的關(guān)系及轉(zhuǎn)換 1. 樹(shù)和森林的表示方法 2. 樹(shù)、森林和二叉樹(shù)的轉(zhuǎn)換 72 樹(shù)的三種存儲(chǔ)結(jié)構(gòu) 一、 雙親表示法 二、 孩子鏈表表示法 三、 樹(shù)的二叉鏈表 (孩子 兄弟） 存儲(chǔ)表示法 1. 樹(shù)和森林的表示方法 73 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 一、雙親表示法 : 結(jié)點(diǎn)結(jié)構(gòu) : data parent 74 用一組連續(xù)的空間來(lái)存儲(chǔ)樹(shù)中的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)在表中的位置，其結(jié)點(diǎn)的結(jié)構(gòu)如下： 雙親表示法的優(yōu)點(diǎn)： 利用了樹(shù)中每個(gè)結(jié)點(diǎn)（根結(jié)點(diǎn)除外）只有一個(gè)雙親結(jié)點(diǎn)的性質(zhì)，使得查找某個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)非常容易。 對(duì) 左子樹(shù) 及 右子樹(shù) 仍可按此方式進(jìn)一步分解 . 依次類(lèi)推，便可遞歸得到整棵二叉樹(shù)。 } } 創(chuàng)建二叉樹(shù)的算法 65 從二叉樹(shù)的遍歷可知，任意一棵二叉樹(shù)結(jié)點(diǎn)的遍歷序列是唯一的。 pRChild=CreateBiTree()。 pdata=ch。 if (ch==??) return NULL。 BiTreeNode *p。如： 擴(kuò)展的先序序列： ABCDE A D B E C 63 建立一棵二叉樹(shù) 算法基本思想 : 首先 讀入當(dāng)前根結(jié)點(diǎn)數(shù)據(jù)， 如果是 ’＃ ’，則表示當(dāng)前樹(shù)根置為空 ， 否則 申請(qǐng)一個(gè)新結(jié)點(diǎn) ，存入當(dāng)前根結(jié)點(diǎn)的數(shù)據(jù)， 分別用當(dāng)前根結(jié)點(diǎn)的左子域和右子域進(jìn)行遞歸調(diào)用， 創(chuàng)建左、右子樹(shù) 。 那么，給定一個(gè)遍歷的結(jié)點(diǎn)序列，能否唯一的確定一棵二叉樹(shù)？ 答案： 不能！ 61 先序序列： A B C 結(jié)點(diǎn)序列確定二叉樹(shù)的不唯一性 A B C A B C A B C A B C 中序序列： B A C 后序序列： C B A 62 ?由擴(kuò)展的結(jié)點(diǎn)序列恢復(fù)二叉樹(shù) 在前面講述的結(jié)點(diǎn)序列中，我們忽略了 空子樹(shù) 的輸出。 } return depthval。 depthRight= Depth( Trchild )。 后序遍歷！ 58 int Depth (BiTree T ){ // 返回二叉樹(shù)的深度 if (T ==NULL) depthval = 0。由此，需先分別求得左、右子樹(shù)的深度， 算法中“訪問(wèn)結(jié)點(diǎn)”的操作為 :求得左、右子樹(shù)深度的最大值，然后加 1 。} return (LeafCount)。 R= leaf(rootRChild)。(rootRChild==NULL)) LeafCount =1。 else if ((rootLChild==NULL) amp。 Int leaf (BiTree root) { int LeafCount,L,R。 root RChild==NULL) LeafCount++。 if (root LChild==NULL amp。 55 void leaf(BiTree root) { if(root!=NULL) {leaf(rootLChild)。 /* 先序遍歷右子樹(shù) */ } } 54 統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù) 算法基本思想 : 先序 (或中序或后序 )遍歷二叉樹(shù)，在遍歷過(guò)程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。 /* 輸出葉結(jié)點(diǎn) */ PreOrder(root LChild)。amp。 } 輸出二叉樹(shù)中的結(jié)點(diǎn) 說(shuō)明：輸出二叉樹(shù)中結(jié)點(diǎn)無(wú)次序要求， 三 種遍歷都可用。 Preorder(rootlchild)。 輸出二叉樹(shù)中的結(jié)點(diǎn) 算法基本思想 : 3. 輸出二叉樹(shù)的右子樹(shù) 。 /*訪問(wèn)根結(jié)點(diǎn) */ } } 49 作業(yè) ? P135 ? 2 ?補(bǔ)充 1：有 3個(gè)結(jié)點(diǎn)的樹(shù)有幾種形態(tài) ?有 3個(gè)結(jié)點(diǎn)的二叉樹(shù)有幾種形態(tài) ? 50 四 、 二叉樹(shù)的應(yīng)用舉例 統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù) 求二叉樹(shù)的深度 輸出二叉樹(shù)中的結(jié)點(diǎn) (先序遍歷 ) 輸出二叉樹(shù)中的葉子結(jié)點(diǎn) 51 1. 在二叉樹(shù)不空的前提下 ,輸出二叉樹(shù)的根節(jié)點(diǎn) 。 /*后序遍歷左子樹(shù) */ PostOrder(root RChild)。 /*訪問(wèn)根結(jié)點(diǎn) */ InOrder(root RChild)。 /*先序遍歷右子樹(shù) */ } } 47 void InOrder(BiTree root) / *中序遍歷二叉樹(shù) , root為二叉樹(shù)根結(jié)點(diǎn)的指針 */ {if (root!=NULL) { InOrder(root LChild)。 /*訪問(wèn)根結(jié)點(diǎn) */ PreOrder(root LChild)。 42 后序遍歷（ LRD）操作過(guò)程 若二叉樹(shù)為空樹(shù)，則空操作；否則， （ 1）后序遍歷左子樹(shù)； （ 2）后序遍歷右子樹(shù)； （ 3）訪問(wèn)根結(jié)點(diǎn)。 二叉樹(shù)的基本結(jié)構(gòu)由 根結(jié)點(diǎn) 、 左子樹(shù) 和 右子樹(shù) 組成 : RChild Data LChild Data LChild RChild 38 二叉樹(shù)的搜索路徑 (先左后右 )： 39 B D C E F 第一次經(jīng)過(guò) B 第二次經(jīng)過(guò) B 第三次經(jīng)過(guò) B 問(wèn)題：那一次經(jīng)過(guò)時(shí)訪問(wèn) B ? 二、先左后右的遍歷算法 先 （根）序的遍歷算法 DLR 中 （根）序的遍歷算法 LDR 后 （根）序的遍歷算法 LRD 根 左 子樹(shù) 右 子樹(shù) 根根根根根40 先序遍歷（ DLR）操作過(guò)程 若二叉樹(shù)為空樹(shù)，則空操作；否則， （ 1）訪問(wèn)根結(jié)點(diǎn)； （ 2）先序遍歷左子樹(shù)； （ 3）先序遍歷右子樹(shù)。 “訪問(wèn) ”的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。 }BiTNode, *BiTree。 struct Node *lchild。 typedef struct Node { DataType data。 // 左右孩子指針 } BiTNode, *BiTree。 1. 二叉鏈表 32 typedef struct BiTNode { // 結(jié)點(diǎn)結(jié)構(gòu) TElemType data。 1. 二叉鏈表 2． 三叉鏈表 有時(shí)，為了找到父結(jié)點(diǎn)，可以在二叉鏈表中增加一個(gè) Parent域 ， Parent域指向該結(jié)點(diǎn)的父結(jié)點(diǎn)。 一、二叉樹(shù)的順序存