1、第4章內(nèi)容回顧,單鏈表的基本操作，包括插入、刪除以及查找 雙向鏈表和循環(huán)鏈表的區(qū)別,樹和二叉樹,第五章,預(yù)習(xí)檢查,什么是二叉樹 樹的遍歷有哪幾種方式 樹有那些應(yīng)用,2020/9/7,4,本章目標(biāo),了解樹的定義和基本術(shù)語 了解二叉樹的定義、性質(zhì)、和存儲結(jié)構(gòu) 掌握二叉樹的遍歷,本章結(jié)構(gòu),樹的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu),樹和二叉樹,二叉樹,遍歷二叉樹,2020/9/7,6,5.1 .1 樹型結(jié)構(gòu)實例 1家族樹,5-1 樹的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu),圖5-1 家族樹,2020/9/7,7,2書的目錄結(jié)構(gòu),圖5-2 書的目錄,5-1 書的目錄結(jié)構(gòu),2020/9/7,8,5.1 .2 樹的定義 1樹的定義 樹(Tree

2、)是n (n0)個結(jié)點的有限集(記為T)，T為空時稱為空樹，否則它滿足以下兩個條件： (1) 有且僅有一個結(jié)點沒有前驅(qū)，稱該結(jié)點為根結(jié)點(Root)； (2) 除根結(jié)點以外，其余結(jié)點可分為m(m0)個互不相交的有限集合T0，Tl，Tm-1。其中每個集合又構(gòu)成一棵樹，樹T0，Tl ，Tm-1被稱為根結(jié)點的子樹(Subree)。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有0個或多個后繼。 樹的邏輯結(jié)構(gòu)表示數(shù)據(jù)之間的關(guān)系是一對多，或者多對一的關(guān)系。它的結(jié)構(gòu)特點具有明顯的層次關(guān)系，是一種十分重要的非線性的數(shù)據(jù)結(jié)構(gòu)。,5-1 樹的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu),2020/9/7,9,圖5-3 樹的示例,圖5-3

3、(a)是一棵只有一個根結(jié)點的樹； 圖5-3 (b)是一棵有12個結(jié)點的樹，即T=A，B，C，K，L 。A是棵根，除根結(jié)點A之外，其余的11個結(jié)點分為三個互不相交的集合。T1，T2和T3是根A的三棵子樹，且本身又都是一棵樹。所以樹的定義是遞歸的 。,2020/9/7,10,2樹的基本術(shù)語 樹的結(jié)點包含一個數(shù)據(jù)元素及若干指向其子樹的分支。 1. 樹的結(jié)點:包含一個數(shù)據(jù)元素和指向其子樹的所有分支; 2. 結(jié)點的度:一個結(jié)點擁有的子樹個數(shù),度為零的結(jié)點稱為葉結(jié)點; 3. 樹的度:樹中所有結(jié)點的度的最大值 Max(D(I) 含義:樹中最大分支數(shù)為樹的度; 4. 結(jié)點的層次及樹的深度:根為第一層,根的孩子

4、為第二層,若某結(jié)點為第k層,則其孩子為k+1層. 樹中結(jié)點的最大層次稱為樹的深度或高度 5.森林:是m(m=0)棵互不相的樹的集合 森林與樹概念相近,相互很容易轉(zhuǎn)換. 6 .有序樹、無序樹 如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹。,2020/9/7,11,7.森林: 是m（m0）棵互不相交的樹的集合。 在樹結(jié)構(gòu)中，結(jié)點之間的關(guān)系又可以用家族關(guān)系描述，定義如下： 8.孩子、雙親: 結(jié)點子樹的根稱為這個結(jié)點的孩子，而這個結(jié)點又被稱為孩子的雙親。 9.子孫: 以某結(jié)點為根的子樹中的所有結(jié)點都被稱為是該結(jié)點的子孫。 10.祖先: 從根結(jié)點到該結(jié)點路徑上的所

5、有結(jié)點。 11.兄弟: 同一個雙親的孩子之間互為兄弟。 12.堂兄弟: 雙親在同一層的結(jié)點互為堂兄弟。,2020/9/7,12,3. 樹的基本運算 樹的基本運算主要有： 初始化操作INITIATE(T)：創(chuàng)建一棵空樹。 求根函數(shù)ROOT(T)：求樹T的根；ROOT(X)：求結(jié)點x所在樹的根。 求雙親函數(shù)PARENT(T,x)：在樹T中求x的雙親。 求第i個孩子函數(shù)CHILD(T,x,i)：在樹T中求結(jié)點x的第i個孩子。 建樹函數(shù)CRT-TREE(x,F)：建立以結(jié)點x為根，森林F為子樹的樹。 6.遍歷樹操作TRAVERSE(T)：按順序訪問樹T中各個結(jié)點。,2020/9/7,13,樹的邏輯表示

6、方法有多種，常見的有 ： 1 樹形圖表示法 2 嵌套集合表示法（文氏圖表示法） 3 凹入表示法 4 廣義表表示法,5-1-3 樹的表示,2020/9/7,14,和線性表一樣，樹可以用順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu)。 樹的順序存儲結(jié)構(gòu)適合樹中結(jié)點比較“滿”的情況。根據(jù)樹的非線性結(jié)構(gòu)特點，常用鏈?zhǔn)酱鎯Ψ绞絹肀硎緲?。樹常用的存儲方法有：雙親存儲表示法、孩子鏈表表示法和孩子兄弟鏈表表示法。 1雙親存儲表示法 一般采用順序存儲結(jié)構(gòu)實現(xiàn)。用一組地址連續(xù)的存儲單元來存放樹的結(jié)點，每個結(jié)點有兩個域： data域-存放結(jié)點的信息； parent域-存放該結(jié)點雙親結(jié)點的位置,特點：求結(jié)點的雙親很容易，但求結(jié)點的孩子需要遍

7、歷整個向量。,5-1-4 樹的存儲結(jié)構(gòu),2020/9/7,15,存儲結(jié)構(gòu)描述為： #define MaxTreeSize 100 /定義數(shù)組空間的大小 typedef char DataType； /定義數(shù)據(jù)類型 typedef struct DataType data； /結(jié)點數(shù)據(jù) int parent； /雙親指針，指示結(jié)點的雙親在數(shù)組中的位置 PTreeNode； typedef struct PTreeNode nodesMaxTreeSize; int n； /結(jié)點總數(shù) PTree； PTree T； /T是雙親鏈表,2020/9/7,16,2孩子鏈表表示法 這是樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)。每

8、個結(jié)點的孩子用單鏈表存儲，稱為孩子鏈表。 n個結(jié)點可以有n個孩子鏈表（葉結(jié)點的孩子鏈表為空表）。 n個孩子鏈表的頭指針用一個向量表示。,圖5-4 樹的孩子鏈表結(jié)構(gòu),頭指針向量孩子鏈表,特點：與雙親相反，求孩子易，求雙親難。,A,B,C,F,G,D,E,A,B,C,D,E,F,G,(,a,),樹,(,b,),樹,的,孩,子,存,儲,結(jié),構(gòu),0,1,2,3,4,5,6,1,2,3,4,5,6,2020/9/7,17,孩子鏈表表示法的類型說明 typedef struct Cnode /DataType和MaxTreeSize由用戶定義 /孩子鏈表結(jié)點 int child; /孩子結(jié)點在數(shù)組中對應(yīng)的

9、下標(biāo) struct CNode *next; Cnode; typedef struct /孩子鏈表頭結(jié)點 DataType data; /存放樹中結(jié)點數(shù)據(jù) CNode *firstchild; /孩子鏈表的頭指針 PTNode; typedef struct PTNode nodesMaxTreeSize; Int n,root; /樹的結(jié)點數(shù)和根結(jié)點的位置 Ctree; Ctree T; /T的孩子鏈表表示,2020/9/7,18,3孩子兄弟鏈表表示法 孩子兄弟鏈表表示法也是樹的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。用二叉鏈表作為樹的存儲結(jié)構(gòu)，每個結(jié)點的左鏈域指向該結(jié)點的第一個孩子，右鏈域指向下一個兄弟結(jié)點。

10、 由于結(jié)點中的兩個指針指示的分別為“孩子”和“兄弟”，故稱為“孩子-兄弟鏈表”。這種結(jié)構(gòu)也稱為二叉鏈表。,圖5-5 樹的孩子-兄弟存儲結(jié)構(gòu),特點：雙親只管長子 長子連接兄弟,A,B,C,F,G,D,E,2020/9/7,19,樹的孩子兄弟鏈表的存儲結(jié)構(gòu)描述為： typedef struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree; 孩子兄弟存儲結(jié)構(gòu)的最大優(yōu)點是可以方便地實現(xiàn)樹和二叉樹的相互轉(zhuǎn)換和樹的各種操作。但是，孩子兄弟存儲結(jié)構(gòu)的缺點也是查找當(dāng)前結(jié)點的雙親結(jié)點比較麻煩，需要從

11、樹根結(jié)點開始逐個結(jié)點比較查找。,2020/9/7,20,1樹的遍歷 所謂樹的遍歷，就是按照某種順序依次訪問樹中各個結(jié)點，并使得每個結(jié)點只被訪問一次。也就是把非線性結(jié)構(gòu)的樹結(jié)點變成線性序列的一種方式 。 樹的遍歷可以按深度優(yōu)先遍歷，也可以按照廣度優(yōu)先（按層次）遍歷。深度優(yōu)先遍歷通常有兩種方式：前序遍歷和后序遍歷。 (1) 前序遍歷的遞歸定義： 若樹T非空，則： 訪問根結(jié)點R； 按照從左到右的順序依次前序遍歷根結(jié)點R的各子樹T1，T2，Tk。,5-1-5 樹的遍歷,2020/9/7,21,(2) 后序遍歷的遞歸定義： 若樹T非空，則： 按照從左到右的順序依次后序遍歷根T的各子樹Tl，T2，Tk；

12、訪問根結(jié)點R。 (3) 廣度優(yōu)先（按層）遍歷 廣度優(yōu)先（按層次）遍歷定義為：先訪問第一層結(jié)點（即樹根結(jié)點），再從左至右訪問第二層結(jié)點，依次按層訪問，直到樹中結(jié)點全部被訪問為止。對圖6-6 (a)中的樹進行按層次遍歷得到樹的廣度優(yōu)先遍歷序列為：ABCDEFG。 說明： 前序遍歷一棵樹恰好等價于前序遍歷該樹所對應(yīng)的二叉樹。（6.2節(jié)將介紹二叉樹） 后序遍歷樹恰好等價于中序遍歷該樹所對應(yīng)的二叉樹。,2020/9/7,22,樹的先序遍歷算法描述如下： void Preorder(Btree *root) /先根遍歷k叉樹 if (root!=NULL) printf(“%cn”,root-data);

13、 /訪問根結(jié)點 for(i=0;iti); /遞歸前序遍歷每一個子結(jié)點 ,2020/9/7,23,5.2.1二叉樹的定義與性質(zhì) 二叉樹(Binary Tree)是另一種重要的樹型結(jié)構(gòu)。是度為2的有序樹，它的特點是每個結(jié)點至多有兩棵子樹。和樹結(jié)構(gòu)的定義類似，二叉樹的定義也可以用遞歸形式給出。 1二叉樹的遞歸定義 二叉樹(BinaryTree)是n(n0)個結(jié)點的有限集。它或者是空集(n=0)，或者同時滿足以下兩個條件： (1) 有且僅有一個根結(jié)點； (2) 其余的結(jié)點分成兩棵互不相交的左子樹和右子樹。,5-2 二叉樹,2020/9/7,24,二叉樹與樹有區(qū)別：樹至少應(yīng)有一個結(jié)點，而二叉樹可以為空

14、；樹的子樹沒有順序，但如果二叉樹的根結(jié)點只有一棵子樹，必須明確區(qū)分它是左子樹還是右子樹，因為兩者將構(gòu)成不同形態(tài)的二叉樹。因此，二叉樹不是樹的特例。它們是兩種不同的數(shù)據(jù)結(jié)構(gòu)。 二叉樹有5種基本形態(tài)：,圖5-7 二叉樹的五種基本形態(tài),(a) 空二叉樹 (b) 只有根結(jié)點的二叉樹 (c) 右子樹為空的二叉樹 (d) 左子樹為空的二叉樹 (e) 左右子樹均不為空的二叉樹,2020/9/7,25,兩種特殊形態(tài)的二叉樹：滿二叉樹和完全二叉樹。 (1) 滿二叉樹(FullBinaryTree) 深度為k，且有2k-1個結(jié)點的二叉樹。 特點：（1）每一層上結(jié)點數(shù)都達到最大 （2）度為1的結(jié)點n1=0，樹葉都在

15、最下一層上。 結(jié)點層序編號方法：從根結(jié)點起從上到下逐層（層內(nèi)從左到右）對二叉樹的結(jié)點進行連續(xù)編號。,2020/9/7,26,(2) 完全二叉樹(Complete BinaryTree) 深度為k，結(jié)點數(shù)為n的二叉樹，當(dāng)且僅當(dāng)每個結(jié)點的編號都與相同深度的滿二叉樹中從1到n的結(jié)點一一對應(yīng)時，稱為完全二叉樹。,圖5-8 完全二叉樹,完全二叉樹的特點： （1）每個結(jié)點i的左子樹的深度Lhi-其結(jié)點i的右子樹的深度Rhi等于0或1，即葉結(jié)點只可能出現(xiàn)在層次最大或次最大的兩層上。 （2）完全二叉樹結(jié)點數(shù)n滿足2k-1-1n2k-1 （3）滿二叉樹一定是完全二叉樹，反之不成立。,2020/9/7,27,LH

16、1=3 RH1=1 LH1 -RH1=2,非完全二叉樹 非完全二叉樹,LH2=0 RH2=1 LH2-RH2=0-1=-1,2020/9/7,28,2二叉樹的性質(zhì) 性質(zhì)1 在二叉樹的第i層上至多有2i-1 個結(jié)點(i1)。 性質(zhì)2 深度為k的二叉樹至多有2k-1個結(jié)點(k1)。 （深度一定，二叉樹的最大結(jié)點數(shù)也確定） 性質(zhì)3 二叉樹中,終端結(jié)點數(shù)n0與度為2的結(jié)點數(shù)n2有如下關(guān)系: n0=n2+1 性質(zhì)4 結(jié)點數(shù)為n的完全二叉樹，其深度為 log2n + l 性質(zhì)5 在按層序編號的n個結(jié)點的完全二叉樹中，任意一結(jié)點i(1in)有： i=1時，結(jié)點i是樹的根；否則，結(jié)點i的雙親為結(jié)點 i/2 (

17、i1) 。 2in時，結(jié)點i無左孩子，為葉結(jié)點；否則，結(jié)點i的左孩子為結(jié)點2i。 2i+1n時，結(jié)點i無右孩子；否則，結(jié)點i的右孩子為結(jié)點2i+1。,2020/9/7,29,同線性表一樣，二叉樹的存儲結(jié)構(gòu)也有順序和鏈表兩種結(jié)構(gòu)。 1順序存儲結(jié)構(gòu) 用一組地址連續(xù)的存儲單元，以層序順序存放二叉樹的數(shù)據(jù)元素，結(jié)點的相對位置蘊含著結(jié)點之間的關(guān)系。,bt 3 的雙親為 3/2 =1， 即在bt1中； 其左孩子在bt2i=bt6中； 其右孩子在bt2i+1=bt7中。,5-2-2 二叉樹的存儲結(jié)構(gòu),2020/9/7,30,這種存儲結(jié)構(gòu)適合于完全二叉樹，既不浪費存儲空間，又能很快確定結(jié)點的存放位置、結(jié)點的雙

18、親和左右孩子的存放位置，但對一般二叉樹，可能造成存儲空間的大量浪費。,1 2 3 4 5 6 7 8 9 10 1112 A B C D E 0 0 0 0 F G 0 0 0 0,一般二叉樹也按完全二叉樹形式存儲，無結(jié)點處用0表示。,2020/9/7,31,例如：深度為k，且只有k個結(jié)點的右單枝樹(每個非葉結(jié)點只有右孩子)，需2k-1個單元，即有2k-1-k個單元被浪費。, 鏈?zhǔn)酱鎯Y(jié)構(gòu) （二叉鏈表） 設(shè)計不同的結(jié)點結(jié)構(gòu)，可以構(gòu)成不同的鏈?zhǔn)酱鎯Y(jié)構(gòu)。常用的有： 二叉鏈表 三叉鏈表 線索鏈表 用空鏈域存放指向前驅(qū)或后繼的線索,2020/9/7,32,由于二叉樹每個結(jié)點至多只有2個孩子，分別為左

19、孩子和右孩子。因此可以把每個結(jié)點分成三個域：一個域存放結(jié)點本身的信息，另外兩個是指針域，分別存放左、右孩子的地址。每個結(jié)點的結(jié)構(gòu)表示為：,其中左鏈域lchild為指向左孩子的指針，右鏈域rchild為指向右孩子的指針，數(shù)據(jù)域data表示結(jié)點的值。若某結(jié)點沒有左孩子或右孩子，其相應(yīng)的鏈域為空指針。,對應(yīng)的結(jié)構(gòu)類型定義如下： typedef struct node ElemType data; struct node *lchild; struct node *rchild; BTree,*tree; 其中，tree是指向根結(jié)點的指針。,2020/9/7,33,二叉鏈表的結(jié)點結(jié)構(gòu),二叉鏈表,說明：

20、 一個二叉鏈表由根指針root唯一確定。若二叉樹為空，則root=NULL；若結(jié)點的某個孩子不存在，則相應(yīng)的指針為空。 具有n個結(jié)點的二叉鏈表中，共有2n個指針域。其中只有n-1個用來指示結(jié)點的左、右孩子，其余的n+1個指針域為空。,2020/9/7,34,lchild data parent rchild,A,C,B,D,E,三叉鏈表,3帶雙親指針的二叉鏈表 由于經(jīng)常要在二叉樹中尋找某結(jié)點的雙親時，可在每個結(jié)點上再加一個指向其雙親的指針parent，形成一個帶雙親指針的二叉鏈表。就是三叉鏈表。 三叉鏈表的結(jié)點結(jié)構(gòu),性質(zhì)6 含有n個結(jié)點的二叉鏈表中，有n+1個空鏈域。 二叉樹存儲方法的選擇，主

21、要依賴于所要實施的各種運算的頻度。,2020/9/7,35,5.3.1遍歷二叉樹 在二叉樹的一些應(yīng)用中，常常要求在樹中查找具有某種特征的結(jié)點，或者對樹中全部結(jié)點逐一進行某種處理。這就引入了遍歷二叉樹的問題，即如何按某條搜索路徑訪問樹中的每一個結(jié)點，使得每一個結(jié)點僅切僅被訪問一次。 遍歷二叉樹：指按一定的規(guī)律對二叉樹的每個結(jié)點，訪問且僅訪問一次的處理過程。 遍歷對線性結(jié)構(gòu)是容易解決的。而二叉樹是非線性的，因而需要尋找一種規(guī)律，使二叉樹上的結(jié)點能排列在一個線性隊列上，從而便于遍歷。,5-3 遍歷二叉樹和線索二叉樹,2020/9/7,36,訪問是一種抽象操作，是對結(jié)點的某種處理，例如可以是求結(jié)點的度

22、、或?qū)哟?、打印結(jié)點的信息，或做其他任何工作。 一次遍歷后，使樹中結(jié)點的非線性排列，按訪問的先后順序變?yōu)槟撤N線性排列。 遍歷的次序：假如以L、D、R分別表示遍歷左子樹、遍歷根結(jié)點和遍歷右子樹，遍歷整個二叉樹則有DLR、LDR、LRD、DRL、RDL、RLD六種遍歷方案。若規(guī)定先左后右，則只有前三種情況，分別規(guī)定為： DLR先（根）序遍歷， LDR中（根）序遍歷， LRD后（根）序遍歷。 1遍歷方案 LDR 中序遍歷； LRD 后序遍歷； DLR 先序遍歷,2020/9/7,37,1）中序遍歷二叉樹 算法思想: 若二叉樹非空，則： 1）中序遍歷左子樹 2）訪問根結(jié)點 3）中序遍歷右子樹,算法描述:

23、 void Inorder (BiTree bt) /bt為根結(jié)點指針 if( bt)/根非空 Inorder (bt-lchild) ; visit (bt-data)； Inorder (bt-rchild) ; ,2）后序遍歷二叉樹 算法思想: 若二叉樹非空，則： 1）后序遍歷左子樹 2）后序遍歷右子樹 3）訪問根結(jié)點,算法描述: void Postorder (BiTree bt) /bt為根結(jié)點指針 if( bt) Postorder (bt-lchild) ; Postorder (bt-rchild) ; visit (bt -data)； ,2020/9/7,38,3）先序遍歷

24、二叉樹 算法思想: 若二叉樹非空，則： 1）訪問根結(jié)點 2）先序遍歷左子樹 3）先序遍歷右子樹,算法描述: void Preorder (BiTree bt) /bt為根結(jié)點指針 if( bt)/根非空 visit (bt-data)； Preorder (bt-lchild) ; Preorder (bt-rchild) ; ,例：表達式a+b (c-d)-e/f,遍歷結(jié)果: 中序: a+b c - d - e / f 后序: abcd - + ef / - 先序: - +a b - cd / ef,2020/9/7,39,（1）先序遍歷的遞歸算法如下（假定結(jié)點的元素值為字符型）： #inc

25、lude stdio.h typedef char ElemType; typedef struct node /定義鏈表結(jié)構(gòu) ElemType data; /定義結(jié)點值 struct node *lchild; /定義左子結(jié)點指針 struct node *rchild; /定義右子結(jié)點指針 BTree; preorder(BTree *root) /前序遍歷 if(root!= NULL) /如果不是空結(jié)點 printf(“%cn”,root-data); /輸出當(dāng)前結(jié)點值 preorder(root-lchild); /遞歸前序遍歷左子結(jié)點 preorder(root-rchild);

26、/遞歸前序遍歷右子結(jié)點 ,2遍歷算法,2020/9/7,40,void inorder(BTree *root) /中序遍歷 if(root!=NULL) /如果不是空結(jié)點 inorder(root-lchild); /遞歸中序遍歷左子結(jié)點 printf(“%cn”,root-data); /輸出當(dāng)前結(jié)點值 inorder(root-rchild); /遞歸中序遍歷右子結(jié)點 (3) 后序遍歷的算法實現(xiàn) void postorder(BTree *root) /后序遍歷 if(root!=NULL) /如果不是空結(jié)點 postorder(root-lchild); /遞歸后序遍歷左子結(jié)點 postorder(root-rchild); /遞歸后序遍歷右子結(jié)點 printf(“%cn”,root-data); /輸出當(dāng)前結(jié)點值 ,（2）中序遍歷的遞歸算法如下（假定結(jié)點的元素值為字符型）：,2020/9/7,41,通過上述三種不同的遍歷方式得到三種不同的線性序列，它們的共同的特點是有且僅有一個開始結(jié)點和一個終端結(jié)點，其余各結(jié)點都有且僅有一個前驅(qū)結(jié)點和一個后繼結(jié)點。 從二叉樹的遍歷定義可知，三種遍歷算法的不同之處僅在于訪問根結(jié)點和遍歷左右子樹的先后關(guān)系。如果在算法中隱去和遞歸無關(guān)的語句printf()，則三種遍歷算法是完全相同的。遍歷二叉樹的算法