高級篇第五章樹和二叉樹

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

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

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

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

5、結點的孩子，而這個結點又中的所有結點都被稱為是該結點的子祖先: 從根結點到該結點路徑上的所有結點。兄弟: 同一個雙親的孩子之間互為兄弟。12.堂兄弟:雙親在同一層的結點互為堂兄弟。家園20111家園-開發(fā)板商城/3.樹的基本運算樹的基本運算主要有： 初始化操作INITIATE(T)：創(chuàng)建一棵空樹。 求根函數ROOT(T)：求樹T的根；ROOT(X)：求結點x所在樹的根。 求雙親函數PARENT(T,x)：在樹T中求x的雙親。 求第i個孩子函數CHILD(T,x,i)：在樹T中求結點x的第i個孩子。 建樹函數CREATETREE(x,F)：建立以結點x為根，森林F為子樹的樹。6.遍歷樹操作TRA

6、VERSE(T)：按順序樹T中各個結點。家園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樹的結構和線性表一樣，樹可以用順序和鏈式兩種結構。結構適合樹中結點比較“滿”的情況。根據樹的非線性樹的順序結構特點，常用鏈式方式來表示樹。樹常用的方法有：雙親存儲表示法、孩子鏈表表示法和孩

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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