【文章內(nèi)容簡介】
Preorder(rootrchild)。 } 輸出二叉樹中的結(jié)點 說明:輸出二叉樹中結(jié)點無次序要求, 三 種遍歷都可用。 53 輸出二叉樹中的葉子結(jié)點 void PreOrder(BiTree root) /* 先序遍歷輸出二叉樹中葉結(jié)點 , root為二叉樹根結(jié)點的指針 */ { if (root!=NULL) {if (root LChild==NULL amp。amp。 root RChild==NULL) printf (root data)。 /* 輸出葉結(jié)點 */ PreOrder(root LChild)。 /* 先序遍歷左子樹 */ PreOrder(root RChild)。 /* 先序遍歷右子樹 */ } } 54 統(tǒng)計二叉樹中葉子結(jié)點的個數(shù) 算法基本思想 : 先序 (或中序或后序 )遍歷二叉樹,在遍歷過程中查找葉子結(jié)點,并計數(shù)。 由此, 需在遍歷算法中增添一個“計數(shù)”的參數(shù), 并將算法中“訪問結(jié)點” 的操作改為 :若是葉子,則計數(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é)點數(shù)目, 調(diào)用前賦初值為 0 56 方法二:空樹:返回 0;葉子結(jié)點,返回 1; 否則為左右子樹的葉子結(jié)點數(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é)點”的操作為 :求得左、右子樹深度的最大值,然后加 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 五、由遍歷序列確定二叉樹 在對一棵二叉樹進行遍歷,只要遍歷的策略已確定,就可以得到一個唯一的結(jié)點序列。 那么,給定一個遍歷的結(jié)點序列,能否唯一的確定一棵二叉樹? 答案: 不能! 61 先序序列: A B C 結(jié)點序列確定二叉樹的不唯一性 A B C A B C A B C A B C 中序序列: B A C 后序序列: C B A 62 ?由擴展的結(jié)點序列恢復(fù)二叉樹 在前面講述的結(jié)點序列中,我們忽略了 空子樹 的輸出。假如 在遍歷二叉樹時,我們使用某個特定的符號表示空子樹,則稱得到的序列為擴展的結(jié)點序列 。如: 擴展的先序序列: ABCDE A D B E C 63 建立一棵二叉樹 算法基本思想 : 首先 讀入當(dāng)前根結(jié)點數(shù)據(jù), 如果是 ’# ’,則表示當(dāng)前樹根置為空 , 否則 申請一個新結(jié)點 ,存入當(dāng)前根結(jié)點的數(shù)據(jù), 分別用當(dāng)前根結(jié)點的左子域和右子域進行遞歸調(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é)點的遍歷序列是唯一的。但是,給定結(jié)點的遍歷序列,卻不能唯一確定一棵二叉樹! ? 由遍歷序列確定二叉樹 二叉樹的先序序列 二叉樹的中序序列 左子樹 左子樹 右子樹 右子樹 根 根 那么,給定一棵二叉樹結(jié)點的先序序列和中序序列,能否唯一確定一棵二叉樹呢? 66 二叉樹先序遍歷是先訪問根結(jié)點 D,即 第一結(jié)點必是根 ;另一方面,中序遍歷是先左子樹,其次是根,最后是右子樹,則 根結(jié)點 D將中序序列分割成兩部分 : D之前是左子樹結(jié)點的中序序列,D之后是右子樹結(jié)點的中序序列。 對 左子樹 及 右子樹 仍可按此方式進一步分解 . 依次類推,便可遞歸得到整棵二叉樹。 分析: 67 由結(jié)點序列恢復(fù)二叉樹 ?可 恢復(fù)二叉樹的結(jié)點序列組合: ( 1) 先序 序列和 中序 序列 ( 2) 中序 序列和 后序 序列 ?不可 恢復(fù)二叉樹的結(jié)點序列組合: 先序 序列和 后序 序列 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é)點結(jié)構(gòu) : data parent 74 用一組連續(xù)的空間來存儲樹中的結(jié)點,每個結(jié)點附設(shè)一個指示器指示其雙親結(jié)點在表中的位置,其結(jié)點的結(jié)構(gòu)如下: 雙親表示法的優(yōu)點: 利用了樹中每個結(jié)點(根結(jié)點除外)只有一個雙親結(jié)點的性質(zhì),使得查找某個結(jié)點的雙親結(jié)點非常容易。 雙親表示法的缺點: 求某個結(jié)點的孩子時,需要遍歷整個表。 75 通常是把 每個結(jié)點的孩子 結(jié)點排列起來, 構(gòu)成一個單鏈表 ,稱為孩子鏈表。n個結(jié)點共有 n個孩子鏈表(葉結(jié)點的孩子鏈表為空表)。 n個結(jié)點的數(shù)據(jù) 和 n個孩子鏈表的頭指針又 組成一個順序表 。 二、孩子鏈表表示法 : 76 data firstchild A