高級篇第五章樹和二叉樹

1、上章顧單鏈表的基本操作，包括、刪除以及查找雙向鏈表和循環(huán)鏈表的區(qū)別家園家園-開發(fā)板商城/回第五章樹和二叉樹家園家園-開發(fā)板商城/預(yù)習(xí)檢查二叉樹樹的遍歷有哪幾種方式樹有哪些應(yīng)用家園家園-開發(fā)板商城/本章結(jié)構(gòu)家園家園-開發(fā)板商城/遍歷二叉樹二叉樹樹和二叉樹樹的邏輯結(jié)構(gòu)和結(jié)構(gòu)課程目標了解樹的定義和基本術(shù)語了解二叉樹的定義、性質(zhì)、和結(jié)構(gòu)掌握二叉樹的遍歷家園2015家園-開發(fā)板商城/5.1樹的邏輯結(jié)構(gòu)和結(jié)構(gòu)5.1 .1樹型結(jié)構(gòu)實例1樹祖父關(guān)系表示：R=,，,，,伯父父親叔父堂兄堂姐本人堂弟侄兒(b)譜系的關(guān)系表示(a)樹圖5-1樹家園2016家園-開發(fā)板商城/5.1書的目錄結(jié)構(gòu)2書的目錄結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)線性

2、表和廣義表棧和隊列樹圖線性表廣義表隊列棧樹二叉樹圖5-2 書的目錄家園2017家園-開發(fā)板商城/5.1樹的邏輯結(jié)構(gòu)和結(jié)構(gòu)5.1 .2樹的定義1樹的定義樹(Tree)是n (n0)個結(jié)點的有限集(記為T)，T為空時稱為空樹，否則它滿足以下兩個條件：有且僅有一個結(jié)點沒有前驅(qū)，稱該結(jié)點為根結(jié)點(Root)；除根結(jié)點以外，其余結(jié)點可分為m(m0)個互不相交的有限集合T0，Tl，Tm-1。其中每個集合又一棵樹，樹T0，Tl ，Tm-的根結(jié)點有且僅有一個直接1被稱為根結(jié)點的(SubTree)。每棵前驅(qū)，但可以有0個或多個后繼。樹的邏輯結(jié)構(gòu)表示數(shù)據(jù)之間的關(guān)系是一對多，或者多對一的關(guān)系。它的結(jié)構(gòu)特點具有明顯的

3、層次關(guān)系，是一種十分重要的非線性的數(shù)據(jù)結(jié)構(gòu)。家園2018家園-開發(fā)板商城/ATT3T1T2BDCAEGHJKFIL( a)只有根結(jié)點的樹( b) 有12個結(jié)點的樹圖5-3 樹的示例圖5-3 (a)是一棵只有一個根結(jié)點的樹；圖5-3 (b)是一棵有12個結(jié)點的樹，即T=A，B，C，K， L 。A是根，除根結(jié)點A之外，其余的11個結(jié)點分為三個互不相交的集合。T1，T2和T3是根A的三棵，且本身又都是一棵樹。所以樹的201家遞園歸w的ww9家園-開發(fā)板商城/2樹的基本術(shù)語樹的結(jié)點包含一個數(shù)據(jù)元素及若干指向其的分支。的所有分支;1.2.3.樹的結(jié)點:包含一個數(shù)據(jù)元素和指向其結(jié)點的度:一個結(jié)點擁有的個數(shù)

4、,度為零的結(jié)點稱為葉子;樹的度:樹中所有結(jié)點的度的最大值 Max(D(I)含義:樹中最大分支數(shù)為樹的度;結(jié)點的層次及樹的深度:根為第一層,根的孩子為第二層,若某結(jié)4.點為第k層,則其孩子為k+1層.樹中結(jié)點的最大層次稱為樹的深度或高度 5.森林:是m(m 0)棵互不相交的樹的集合森林與樹概念相近,相互很容易轉(zhuǎn)換.6 .有序樹、無序樹順序，不得互換如果樹中每棵家為園有從左向右的排列擁有一定的序樹。20110家園-開發(fā)板商城/7.森林: 是m（m0）棵互不相交的樹的集合。在樹結(jié)構(gòu)中，結(jié)點之間的關(guān)系又可以用下：關(guān)系描述，定義如孩子、雙親: 結(jié)點被稱為孩子的雙親。子孫: 以某結(jié)點為根的孫。的根稱為這個

5、結(jié)點的孩子，而這個結(jié)點又中的所有結(jié)點都被稱為是該結(jié)點的子祖先: 從根結(jié)點到該結(jié)點路徑上的所有結(jié)點。兄弟: 同一個雙親的孩子之間互為兄弟。12.堂兄弟:雙親在同一層的結(jié)點互為堂兄弟。家園20111家園-開發(fā)板商城/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ù)CREATETREE(x,F)：建立以結(jié)點x為根，森林F為子樹的樹。6.遍歷樹操作TRA

6、VERSE(T)：按順序樹T中各個結(jié)點。家園20112家園-開發(fā)板商城/5.1.3樹的表示樹的邏輯表示方法有多種，常見的有 ：樹形圖表示法嵌套集合表示法（文氏圖表示法）3 凹入表示法A4 廣義表表示法DBEHKGFILJC(a)嵌套集合表示法(A (B(E (F), G),C ,D(H (I),J ,K(L ) ( b) 凹入表示法家c) 園廣20113家園-開發(fā)板商城/ABEFGC DHIJ KL5.1.4樹的結(jié)構(gòu)和線性表一樣，樹可以用順序和鏈式兩種結(jié)構(gòu)。結(jié)構(gòu)適合樹中結(jié)點比較“滿”的情況。根據(jù)樹的非線性樹的順序結(jié)構(gòu)特點，常用鏈式方式來表示樹。樹常用的方法有：雙親存儲表示法、孩子鏈表表示法和孩

7、子兄弟鏈表表示法。1雙親表示法一般采用順序結(jié)構(gòu)實現(xiàn)。用一組地址連續(xù)的單元來存放樹的結(jié)點，每個結(jié)點有兩個域：data域存放結(jié)點的信息；parent域存放該結(jié)點雙親結(jié)點的位置A序 號da t a p ar en t01特點：求結(jié)點的雙2345678BC親很容易，但求結(jié)點的孩子需要遍歷DEFGHI整個向量。家園的 雙 親/結(jié) 構(gòu)20114家園-開發(fā)板商城A-1 B0C0D1E1F1G2H4I4結(jié)構(gòu)描述為：/定義數(shù)組空間的大小/定義數(shù)據(jù)類型#define typedef typedefMaxTreeSize100char Dastructype；ype data；parent；/結(jié)點數(shù)據(jù)/雙親位置域，

8、指示結(jié)點的雙親在數(shù)組中Da的位置 PTreeNode；typedefstructPTreeNoden； PTree；nodesMaxTreeSize;/結(jié)點總數(shù)T；是雙親鏈表PTree家園20115家園-開發(fā)板商城/2孩子鏈表表示法這是樹的鏈式結(jié)構(gòu)。每個結(jié)點的孩子用單鏈表，稱為孩子鏈表。n個結(jié)點可以有n個孩子鏈表（葉結(jié)點的孩子鏈表為空表）。n個孩子鏈表的頭指針用一個向量表示。頭指針向量孩子鏈表0123456ABCDEF特 點 ： 與 雙 親 相反，求孩子易，求雙親難。G(a)樹(b)樹的孩子結(jié)構(gòu)5家-4園樹20116家園-開發(fā)板商城/6543ABCDEFG12孩子鏈表表示法的類型說明typed

9、ef struct CNodechild;ype和MaxTreeSize由用戶定義/Da/ 孩子鏈表結(jié)點/孩子結(jié)點在數(shù)組中對應(yīng)的下標uct CNode *next; CNode; typedef struct/孩子鏈表頭結(jié)點Da CN PTNode;ype data;/存放樹中結(jié)點數(shù)據(jù)/孩子鏈表的頭指針*child;typedef structPTNode nodesMaxTreeSize;/樹的結(jié)點數(shù)和根結(jié)點的位置n,root; Ctree;CtreeT;/T的孩子鏈表表示家園20117家園-開發(fā)板商城/3孩子兄弟鏈表表示法孩子兄弟鏈表表示法也是樹的一種鏈式結(jié)構(gòu)。用二叉鏈表作為樹的結(jié)構(gòu)，每個

10、結(jié)點的左鏈域指向該結(jié)點的第一個孩子，右鏈域指向下一個兄弟結(jié)點。由于結(jié)點中的兩個指針指示的分別為“孩子”和“兄弟”，故稱為“孩子-兄弟鏈表”。這種結(jié)構(gòu)也稱為二叉鏈表。特點：雙親長子連接兄弟長子圖5-5樹的孩子-兄弟結(jié)構(gòu)家園20118家園-開發(fā)板商城/GFEDCBA樹的孩子兄弟鏈表的結(jié)構(gòu)描述為：typedefstruct CSNodeElemTypedata;structCSNode*child,*nextsibling;CSNode,*CSTree;孩子兄弟的相互轉(zhuǎn)換和樹的結(jié)構(gòu)的最大優(yōu)點是可以方便地實現(xiàn)樹和二叉樹。但是，孩子兄弟結(jié)構(gòu)的缺點也是查找當前結(jié)點的雙親結(jié)點比較麻煩，需要從樹根結(jié)點開始逐個

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

12、按層次）遍歷定義為：先第一層結(jié)點（即樹根結(jié)點），直到樹中結(jié)點全部被再從左至右第二層結(jié)點，依次按層為止。對圖6-6 (a)中的樹進行按層次遍歷得到樹的廣度優(yōu)先遍歷序列為：ABCDEFG。說明： 前序遍歷一棵樹恰好等價于前序遍歷該樹所對應(yīng)的二叉樹。（6.2節(jié)將介紹二叉樹）家價園于中ww序w遍 后序遍歷樹的二叉樹。20121家園-開發(fā)板商城/樹的先序遍歷算法描述如下：/先根遍歷k叉樹voidPreorder(Btree(root!=NULL)*root)iff(“%cn”,root-data);根結(jié)點pr/for(i=0;iti);個子結(jié)點/遞歸前序遍歷每一家園20122家園-開發(fā)板商城/5.2二叉

13、樹5.2.1二叉樹的定義與性質(zhì)二叉樹(Binary Tree)是另一種重要的樹型結(jié)構(gòu)。是度為2的有序樹，它的特點是每個結(jié)點至多有兩棵類似，二叉樹的定義也可以用遞歸形式給出。1二叉樹的遞歸定義。和樹結(jié)構(gòu)的定義二叉樹(BinaryTree)是n(n0)個結(jié)點集(n=0)，或者同時滿足以下兩個條件：的有限集。它或者是空(1)(2)有且僅有一個根結(jié)點；其余的結(jié)點分成兩棵互不相交的樹和右。家園20123家園-開發(fā)板商城/二叉樹與樹有區(qū)別：樹至少應(yīng)有一個結(jié)點，而二叉樹可以為空；樹的它是沒有順序，但如果二叉樹的根結(jié)點只有一棵，必須明確區(qū)分樹還是右，因為兩者將不同形態(tài)的二叉樹。因此，二叉樹不是樹的特例。它們是

14、兩種不同的數(shù)據(jù)結(jié)構(gòu)。二叉樹有5種基本形態(tài)：(a)(b)( c)( d)(e)(a)空二叉樹(b)只有根結(jié)點的二叉樹(c)右為空的二叉樹(d)(e) 左右樹為空的二叉樹不為空的二叉樹-7 二家園20124家園-開發(fā)板商城/兩種特殊形態(tài)的二叉樹：滿二叉樹和完全二叉樹。(1) 滿二叉樹(FullBinaryTree)深度為k，且有2k-1個結(jié)點的二叉樹。特點：（1）每一層上結(jié)點數(shù)都達到最大（2）度為1的結(jié)點n1=0，樹葉都在最下一層上。結(jié)點層序結(jié)點進行連續(xù)方法：從根結(jié)點起從上到下逐層（層內(nèi)從左到右）對二叉樹的K=3n=23-1=7。1235467家園20125家園-開發(fā)板商城/(2) 完全二叉樹(C

15、omplete BinaryTree)深度為k，結(jié)點數(shù)為n的二叉樹，當且僅當每個結(jié)點的都與相同深度的滿二叉樹中從1到n的結(jié)點一一對應(yīng)時，稱為完全二叉樹。1圖5-8 完全二叉樹2354完全二叉樹的特點：（1）每個結(jié)點i的樹的深度Lhi- 其結(jié)點i的右的深度Rhi等于0或1; 葉結(jié)點只可能出現(xiàn)在層次最大或次最大的兩層上。k-1 k （2）完全二叉樹結(jié)點數(shù)n滿家園（3）201滿一定是完全二叉樹，反之26家園-開發(fā)板商城/11LH2=0RH2=1LH1=3RH1=13232LH2-RH2=0-1=-14-RH =2LH51146非完全二叉樹非完全二叉樹家園20127家園-開發(fā)板商城/2二叉樹的性質(zhì)性質(zhì)

16、1性質(zhì)2在二叉樹的第i層上至多有2i-1 個結(jié)點(i1)。深度為k的二叉樹至多有2k-1個結(jié)點(k1)。（深度一定，二叉樹的最大結(jié)點數(shù)也確定）二叉樹中,終端結(jié)點數(shù)n0與度為2的結(jié)點數(shù)n2有如下關(guān)系: n0=n2+1結(jié)點數(shù)為n的完全二叉樹，其深度為 log2n + l性質(zhì)3性質(zhì)4性質(zhì)5在按層序的n個結(jié)點的完全二叉樹中，任意一結(jié)點i(1in)有： i=1時，結(jié)點i是樹的根；否則，結(jié)點i的雙親為結(jié)點 i/2 (i1) 。 2in時，結(jié)點i無左孩子，為葉結(jié)點；否則，結(jié)點i的左孩子為結(jié)點2i。家i無園右2012i+1n時的右孩子為結(jié)點2i+1。28家園-開發(fā)板商城/5.2.2二叉樹的結(jié)構(gòu)同線性表一樣，二

17、叉樹的結(jié)構(gòu)也有順序和鏈表兩種結(jié)構(gòu)。1順序結(jié)構(gòu)用一組地址連續(xù)的單元，以層序順序存放二叉樹的數(shù)據(jù)元素，結(jié)點的相對位置蘊含著結(jié)點之間的關(guān)系。1234 5 6 7 8 9 10 11完全二叉樹ABCbt 3 的雙親為 3/2 =1，即在bt1中；其左孩子在bt2i=bt6中；子在bt2i+1=bt7中。DEFG家園20129家園-開發(fā)板商城/ABCDEFG0000，無結(jié)點處用0表示。一般二叉樹也按完全二叉樹形式二叉樹ABC123456 7 8 9 10 1112DEFG這種結(jié)構(gòu)僅適合于完全二叉樹，既不浪費空間，又能很快確定結(jié)點的存放位置、結(jié)點的雙親和左右孩子的存放位置，但對一般二叉樹，可能造成空間的大

18、量浪費。家園20130家園-開發(fā)板商城/ABCDE0000FG0000例如：深度為k，且只有k個結(jié)點的右單枝樹(子)，需2k-1個單元，即有2k-1-k個單元被浪費。每個非葉結(jié)點只有右孩鏈式結(jié)構(gòu) （二叉鏈表）設(shè)計不同的結(jié)點結(jié)構(gòu)，可以有：二叉鏈表三叉鏈表不同的鏈式結(jié)構(gòu)。常用的線索鏈表201用家存園放w指w向w e前mb驅(qū)ed或clu后b c繼om的線索31家園-開發(fā)板商城/由于二叉樹每個結(jié)點至多只有2個孩子，分別為左孩子和右孩子。因此可以把每個結(jié)點分成三個域：一個域存放結(jié)點本身的信息，另外兩個是指針域，分別存放左、右孩子的地址。每個結(jié)點的結(jié)構(gòu)表示為：其中左鏈域lchild為指向左孩子的指針，右鏈

19、域rchild為指向右孩子的指針，數(shù)據(jù)域data表示結(jié)點的值。若某結(jié)點沒有左孩子或右孩子，其相應(yīng)的鏈域為空指針。對應(yīng)的結(jié)構(gòu)類型定義如下：typedef struct nodeElemType structstructdata;nodenode*lchild;*rchild;BTree,*tree;其中，tree根結(jié)點家園20132家園-開發(fā)板商城/Lchilddatarchild二叉鏈表的結(jié)點結(jié)構(gòu)二叉鏈表二叉樹ACBDE說明：一個二叉鏈表由根指針root唯一確定。若二叉樹為空，則root=NULL；若結(jié)點的某個孩子不存在，則相應(yīng)的指針為空。具有n個結(jié)點的二叉鏈表有2n個指針域。其中只有n-1個

20、用來指示結(jié)點的左、右孩其余的家園20133家園-開發(fā)板商城/EDCBAlchilddatarchild3帶雙親指針的二叉鏈表由于經(jīng)常要在二叉樹中尋找某結(jié)點的雙親時，可在每個結(jié)點上再加一個指向其雙親的指針parent，形成一個帶雙親指針的二叉鏈表。就是三叉鏈表。三叉鏈表的結(jié)點結(jié)構(gòu)三叉鏈表二叉樹ACBDE性質(zhì)6 含有n個結(jié)點的二叉鏈表中，有n+1個空鏈域。，家主園要二叉樹201方法運算的頻度。/34家園-開發(fā)板商城EDCBAlchilddataparentrchild5.2.3二叉樹的基本運算實現(xiàn)1二叉樹的基本運算Inittree (&T)功能：初始化操作 (建立一棵空的二叉樹)。Root(T)功

21、能：求二叉樹的根。Parent(T,x)功能：求二叉樹T中值為x的結(jié)點的雙親。Lchild(T,x)功能：求結(jié)點的左孩子。Rchild(T,x)功能：求結(jié)點的右孩子。Traverse(T)功能：遍歷或二叉樹T。（7）Creatree(&T)功能：創(chuàng)建二叉樹T家園20135家園-開發(fā)板商城/5.3遍歷二叉樹和線索二叉樹5.3.1遍歷二叉樹在二叉樹的一些應(yīng)用中，常常要求在樹中查找具有某種特征的結(jié)點，或者對樹中全部結(jié)點逐一進行某種處理。這就引入了遍歷二叉樹，即如何按某條搜索路徑樹中的每一個結(jié)點，使得每一個結(jié)點僅切僅被一次。遍歷二叉樹：指按一定的規(guī)律對二叉樹的每個結(jié)點，一次的處理過程。且僅遍歷對線性結(jié)

22、構(gòu)是容易解決的。而二叉樹是非線性的，因而需要尋找一種規(guī)律，使二叉樹上的結(jié)點能排列在一個線性隊列上，從而便于遍歷。家園20136家園-開發(fā)板商城/是一種抽象操作，是對結(jié)點的某種處理，例如可以是求結(jié)點的度、或?qū)哟?、打印結(jié)點的信息，或做其他任何工作。一次遍歷后，使樹中結(jié)點的非線性排列，按種線性排列。遍歷的次序：假如以L、D、R分別表示遍歷的先后順序變?yōu)槟硺洹⒈闅v根結(jié)點和遍樹，遍歷整個二叉樹則有DLR、LDR、LRD、DRL、RDL、RLD六種遍歷方案。若規(guī)定先左后右，則只有前三種情況，分別規(guī)定為： DLR先（根）序遍歷，LDR中（根）序遍歷， LRD后（根）序遍歷。1遍歷方案LDR中序遍歷；LRD

23、后序遍歷；DLR先序遍歷家園20137家園-開發(fā)板商城/1）中序遍歷二叉樹2）后序遍歷二叉樹算法:算法:若二叉樹非空，則：若二叉樹非空，則：1）中序遍歷樹后序遍歷后序遍樹樹2）根結(jié)點3）中序遍算法描述:void Inorder (BiTree bt)/bt為根結(jié)點指針 if( bt)/根非空Inorder (bt-lchild) ; visit (bt-data)； Inorder (bt-rchild) ;樹3）根結(jié)點算法描述:voidtorder (BiTree bt)/bt為根結(jié)點指針if( bt)torder (bt-lchild) ; torder (bt-rchild) ;visi

24、t (bt -data)；201家園38家園-開發(fā)板商城/3）先序遍歷二叉樹算法:若二叉樹非空，則：1）根結(jié)點先序遍歷先序遍樹樹例：表達式 a+b (c-d)-e/f遍歷結(jié)果:中序: a+b c - d - e / f后序: abcd - + ef / -+bc/aef先序: -+a b - cd / ef家園20139家園-開發(fā)板商城/算法描述:void Preorder (BiTree bt)/bt為根結(jié)點指針 if( bt)/根非空visit (bt-data)； Preorder (bt-lchild) ; Preorder (bt-rchild) ;2遍歷算法（1）先序遍歷的遞歸算法

25、如下（假定結(jié)點的元素值為字符型）：#include typedef char ElemType;typedef struct node ElemType data; struct node *lchild; struct node *rchild;BTree; preorder(BTree *root) if(root!= NULL)/定義鏈表結(jié)構(gòu)/定義結(jié)點值/定義結(jié)點指針/定義右子結(jié)點指針/前序遍歷/如果不是空結(jié)點/輸出當前結(jié)點值/遞歸前序遍歷/遞歸前序遍f(“%cn”,root-data);der(root-lchild); prpre結(jié)點結(jié)點preorder(root-rchild);r

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