【文章內(nèi)容簡介】 Preorder(rootrchild)。 } 輸出二叉樹中的結(jié)點(diǎn) 說明：輸出二叉樹中結(jié)點(diǎn)無次序要求， 三 種遍歷都可用。 53 輸出二叉樹中的葉子結(jié)點(diǎn) void PreOrder(BiTree root) /* 先序遍歷輸出二叉樹中葉結(jié)點(diǎn) , root為二叉樹根結(jié)點(diǎn)的指針 */ { if (root!=NULL) {if (root LChild==NULL amp。amp。 root RChild==NULL) printf (root data)。 /* 輸出葉結(jié)點(diǎn) */ PreOrder(root LChild)。 /* 先序遍歷左子樹 */ PreOrder(root RChild)。 /* 先序遍歷右子樹 */ } } 54 統(tǒng)計二叉樹中葉子結(jié)點(diǎn)的個數(shù) 算法基本思想 : 先序 (或中序或后序 )遍歷二叉樹，在遍歷過程中查找葉子結(jié)點(diǎn)，并計數(shù)。 由此， 需在遍歷算法中增添一個“計數(shù)”的參數(shù)， 并將算法中“訪問結(jié)點(diǎn)” 的操作改為 :若是葉子，則計數(shù)器增 1。 55 void leaf(BiTree root) { if(root!=NULL) {leaf(rootLChild)。 leaf(rootRChild)。 if (root LChild==NULL amp。amp。 root RChild==NULL) LeafCount++。 } } 方法一：設(shè)全局變量 LeafCount計葉子結(jié)點(diǎn)數(shù)目， 調(diào)用前賦初值為 0 56 方法二：空樹：返回 0；葉子結(jié)點(diǎn)，返回 1； 否則為左右子樹的葉子結(jié)點(diǎn)數(shù)之和 。 Int leaf (BiTree root) { int LeafCount,L,R。 if (root==NULL) LeafCount = 0。 else if ((rootLChild==NULL) amp。amp。(rootRChild==NULL)) LeafCount =1。 else {L= leaf(rootLChild)。 R= leaf(rootRChild)。 LeafCount=L+R。} return (LeafCount)。 } 57 求二叉樹的深度 算法基本思想 : 從二叉樹深度的定義可知， 二叉樹的深度應(yīng)為其左、右子樹深度的最大值加 1。由此，需先分別求得左、右子樹的深度， 算法中“訪問結(jié)點(diǎn)”的操作為 :求得左、右子樹深度的最大值，然后加 1 。 首先分析 二叉樹的深度 和它的 左 、 右子樹深度 之間的關(guān)系。 后序遍歷！ 58 int Depth (BiTree T ){ // 返回二叉樹的深度 if (T ==NULL) depthval = 0。 else { depthLeft = Depth( Tlchild )。 depthRight= Depth( Trchild )。 depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight)。 } return depthval。 } 59 五、由遍歷序列確定二叉樹 在對一棵二叉樹進(jìn)行遍歷，只要遍歷的策略已確定，就可以得到一個唯一的結(jié)點(diǎn)序列。 那么，給定一個遍歷的結(jié)點(diǎn)序列，能否唯一的確定一棵二叉樹？ 答案： 不能！ 61 先序序列： A B C 結(jié)點(diǎn)序列確定二叉樹的不唯一性 A B C A B C A B C A B C 中序序列： B A C 后序序列： C B A 62 ?由擴(kuò)展的結(jié)點(diǎn)序列恢復(fù)二叉樹 在前面講述的結(jié)點(diǎn)序列中，我們忽略了 空子樹 的輸出。假如 在遍歷二叉樹時，我們使用某個特定的符號表示空子樹，則稱得到的序列為擴(kuò)展的結(jié)點(diǎn)序列 。如： 擴(kuò)展的先序序列： ABCDE A D B E C 63 建立一棵二叉樹 算法基本思想 : 首先 讀入當(dāng)前根結(jié)點(diǎn)數(shù)據(jù)， 如果是 ’＃ ’，則表示當(dāng)前樹根置為空 ， 否則 申請一個新結(jié)點(diǎn) ，存入當(dāng)前根結(jié)點(diǎn)的數(shù)據(jù)， 分別用當(dāng)前根結(jié)點(diǎn)的左子域和右子域進(jìn)行遞歸調(diào)用， 創(chuàng)建左、右子樹 。 64 BiTree CreateBiTree() { char ch。 BiTreeNode *p。 ch=getchar()。 if (ch==??) return NULL。 else { p=(BiTreeNode *) malloc(sizeof(BiTreeNode))。 pdata=ch。 pLChild=CreateBiTree()。 pRChild=CreateBiTree()。 return (p)。 } } 創(chuàng)建二叉樹的算法 65 從二叉樹的遍歷可知，任意一棵二叉樹結(jié)點(diǎn)的遍歷序列是唯一的。但是，給定結(jié)點(diǎn)的遍歷序列，卻不能唯一確定一棵二叉樹！ ? 由遍歷序列確定二叉樹 二叉樹的先序序列 二叉樹的中序序列 左子樹 左子樹 右子樹 右子樹 根 根 那么，給定一棵二叉樹結(jié)點(diǎn)的先序序列和中序序列，能否唯一確定一棵二叉樹呢？ 66 二叉樹先序遍歷是先訪問根結(jié)點(diǎn) D,即 第一結(jié)點(diǎn)必是根 ；另一方面，中序遍歷是先左子樹，其次是根，最后是右子樹，則 根結(jié)點(diǎn) D將中序序列分割成兩部分 ： D之前是左子樹結(jié)點(diǎn)的中序序列，D之后是右子樹結(jié)點(diǎn)的中序序列。 對 左子樹 及 右子樹 仍可按此方式進(jìn)一步分解 . 依次類推，便可遞歸得到整棵二叉樹。 分析： 67 由結(jié)點(diǎn)序列恢復(fù)二叉樹 ?可 恢復(fù)二叉樹的結(jié)點(diǎn)序列組合： （ 1） 先序 序列和 中序 序列 （ 2） 中序 序列和 后序 序列 ?不可 恢復(fù)二叉樹的結(jié)點(diǎn)序列組合： 先序 序列和 后序 序列 68 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 fgg a b c d e f g ^ ^ ^ ^ ^ ^ ^ ^ 先序序列中序序列 69 由遍歷序列確定二叉樹 練習(xí)： 由 先序 和 中序 序列恢復(fù)二叉樹， 并寫出后序遍歷序列。 先序序列： 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 由遍歷序列確定二叉樹 由 中序 和 后序 序列恢復(fù)二叉樹 中序序列： 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ù)的關(guān)系及轉(zhuǎn)換 1. 樹和森林的表示方法 2. 樹、森林和二叉樹的轉(zhuǎn)換 72 樹的三種存儲結(jié)構(gòu) 一、 雙親表示法 二、 孩子鏈表表示法 三、 樹的二叉鏈表 (孩子 兄弟） 存儲表示法 1. 樹和森林的表示方法 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ù)的空間來存儲樹中的結(jié)點(diǎn)，每個結(jié)點(diǎn)附設(shè)一個指示器指示其雙親結(jié)點(diǎn)在表中的位置，其結(jié)點(diǎn)的結(jié)構(gòu)如下： 雙親表示法的優(yōu)點(diǎn)： 利用了樹中每個結(jié)點(diǎn)（根結(jié)點(diǎn)除外）只有一個雙親結(jié)點(diǎn)的性質(zhì)，使得查找某個結(jié)點(diǎn)的雙親結(jié)點(diǎn)非常容易。 雙親表示法的缺點(diǎn)： 求某個結(jié)點(diǎn)的孩子時，需要遍歷整個表。 75 通常是把 每個結(jié)點(diǎn)的孩子 結(jié)點(diǎn)排列起來， 構(gòu)成一個單鏈表 ，稱為孩子鏈表。n個結(jié)點(diǎn)共有 n個孩子鏈表（葉結(jié)點(diǎn)的孩子鏈表為空表）。 n個結(jié)點(diǎn)的數(shù)據(jù) 和 n個孩子鏈表的頭指針又 組成一個順序表 。 二、孩子鏈表表示法 : 76 data firstchild A