1、1,一、樹的概念：是n（n=0）個結(jié)點(diǎn)的有限集合。,第四章 樹 4.1 樹的結(jié)構(gòu)定義和基本術(shù)語,其中每一個集合Ti(i=1,2,.,m)本身又是一棵樹，并且稱為根的子樹。,2,A是根 T1 = B,E,F T2 = C,G,I,J T3 = D,H 在樹中，每個結(jié)點(diǎn)被定義為它的每個子樹的根結(jié)點(diǎn)的前驅(qū)。,二、樹的表示： 結(jié)點(diǎn)連線。 隱含：上方結(jié)點(diǎn)是下方結(jié)點(diǎn)的前驅(qū)。,3,(2)集合圖表示法:每棵樹對應(yīng)一個圓形，圓內(nèi)包含根結(jié)點(diǎn)和子樹。,A E B D H F C G,I,J,4,（3）凹入表示法:每棵樹的根對應(yīng)著一個條形，子樹的根對應(yīng)著一個較短的條形。,A B E F C G I J D H,5,(

2、1)樹的結(jié)點(diǎn)：包含一個數(shù)據(jù)元素及若干指向其子樹的分支。 (2)結(jié)點(diǎn)的度（degree）：結(jié)點(diǎn)擁有的子樹數(shù)。 (3)根結(jié)點(diǎn)：無前驅(qū)。 (4)葉子（終端結(jié)點(diǎn)）：度為零的結(jié)點(diǎn)。無后繼。 (5)分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)）：度不為零的結(jié)點(diǎn)。除根結(jié)點(diǎn)外，分支結(jié)點(diǎn)也稱內(nèi)部結(jié)點(diǎn) （一個前驅(qū)，多個后繼）。 (6)樹的度:樹內(nèi)各結(jié)點(diǎn)的度的最大值。,A B C D E F G H I J,三、基本術(shù)語,6,(7)孩子：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子。相應(yīng)地，該結(jié)點(diǎn)稱為孩子的雙親。 (8)兄弟：同一雙親的孩子之間互為兄弟。 (9)堂兄弟:有相同的祖父 (10)祖先：結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。 (11)

3、子孫：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。,7,(12)結(jié)點(diǎn)的層次：根為第一層，根的孩子為第二層。 (13)樹的深度（高度）：樹中結(jié)點(diǎn)的最大層次。 (14)有序樹及無序樹： 如： A A B C C B,8,(15)森林：是m棵互不相交的樹的集合。 對樹中每個結(jié)點(diǎn)而言，其子樹的集合即為森林。樹和森林可以互相遞歸定義： Tree=(root, F) F = (T1, T2, ,Tm) (m0) Ti = (ri,Fi) 當(dāng)m0時，樹根和子樹森林之間存在下列關(guān)系：RF = |1im, m0,9,四、樹的基本操作： 求根：ROOT(T); 結(jié)果：樹T的根結(jié)點(diǎn)。 求雙親： PARENT(

4、T, X); 結(jié)果：結(jié)點(diǎn)X在樹T的雙親。 求孩子：CHILD(T，X，i); 結(jié)果：樹T上X結(jié)點(diǎn)的第i個孩子。 建樹：CREATE(X,T1,T2,Tn); 結(jié)果：建立一棵以X為根，以T1，T2，TN為子樹的樹 剪枝：DELETE(T,X,i); 結(jié)果：刪除樹T上結(jié)點(diǎn)X的第i棵子樹。,10,線性結(jié)構(gòu) (1)第一個數(shù)據(jù)元素(無前驅(qū)) (2)最后一個數(shù)據(jù)元素(無后繼) (3)其它數(shù)據(jù)元素(一個前驅(qū)、一個后繼),樹結(jié)構(gòu) (1)根結(jié)點(diǎn)(無前驅(qū)) (2)多個葉子結(jié)點(diǎn) (無后繼) (3)樹中其它結(jié)點(diǎn)（有一個直接前驅(qū)和多個直接后繼）,樹結(jié)構(gòu)與線性結(jié)構(gòu)的比較,11,二叉樹是一種特殊的樹結(jié)構(gòu)。 特點(diǎn)：每個結(jié)點(diǎn)至

5、多只有兩棵子樹，子樹有左右之分，其次序不能任意顛倒，分別稱為左右子樹。 五種形態(tài)：,4.2 二叉樹4.2.1 二叉樹的定義和基本操作,二叉樹的基本操作與樹的基本操作相類似。,12,特殊的二叉樹： (1)滿二叉樹：二叉樹中每一層的結(jié)點(diǎn)數(shù)都達(dá)到最大。 (2)完全二叉樹： 特點(diǎn)：葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn); 對任一結(jié)點(diǎn)，若其右分支下的子孫的最大層次為L,則其左分支下的子孫的最大層次必為L或L+1。,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,1 2 3 4 5 6 7 8 9 10 11 12,滿二叉樹,完全二叉樹,13,4.2.2 二叉樹的性質(zhì),性質(zhì)1:在二叉

6、樹的第i層上至多有2i-1個結(jié)點(diǎn)（i1）。 用歸納法證明： (1)i=1時, 2i-1=1，即只有一個根結(jié)點(diǎn)。 (2)設(shè)對1ji-1,命題成立，則可以證明j=i時命題也成立。 由于第i-1層上至多有2i-2個結(jié)點(diǎn)，由于二叉樹中每個結(jié)點(diǎn)的度至多為2，故第i層上的結(jié)點(diǎn)數(shù)最多為 2i-2*2= 2i-1。,14,性質(zhì)2：深度為k的二叉樹至多有2k-1個結(jié)點(diǎn)， （k1）。 k （第i層上的最大結(jié)點(diǎn)數(shù)） i=1 k = 2i-1 i=1 =( 1 + 2 + 22 + + 2k-1)=2k-1,15,性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有n0=n2+1。 設(shè)度為1

7、的結(jié)點(diǎn)數(shù)為n1, 總結(jié)點(diǎn)數(shù)為n，則有 n = n0 + n1 + n2 設(shè)分支數(shù)為B， n = B + 1（除根結(jié)點(diǎn)外，每一個結(jié) 點(diǎn)都有一個分支到達(dá)） 又由于這些分支數(shù)是由度為1和度為2的結(jié)點(diǎn)發(fā)出的，因此，B = n1 + 2n2 n0 + n1 + n2 = n1 + 2n2 + 1 n0 = n2 + 1,16,性質(zhì)4：具有n個結(jié)點(diǎn)的完全二叉樹的深度為 log2(n+1) (不小于log2(n+1)的整數(shù)) 或log2n（不大于log2n的整數(shù)) + 1。 假設(shè)深度為k，由性質(zhì)2，最大結(jié)點(diǎn)數(shù)為2k-1, 深度為k-1的最大結(jié)點(diǎn)數(shù)為2k-1-1。 2k-1-1 n 2k-1 或 2k-1 n

8、 2k-1 2k-1 n+1 2k k-1 log2(n+1) k log2(n+1) k log2(n+1) +1 k = log2(n+1) ,17,性質(zhì)5：如果對一棵有n個結(jié)點(diǎn)的完全二叉樹，其深度為log2n + 1的結(jié)點(diǎn)按層序編號，則對任一結(jié)點(diǎn)i(1in)，有 (1)如果i = 1, 則結(jié)點(diǎn)i是根。如果i1, 則其雙親parent(i)是結(jié)點(diǎn)i/2 (2)如果2*in，則結(jié)點(diǎn) i 為葉子，否則其左孩子Lchild(i)是結(jié)點(diǎn)2*i。 (3)如果2*i+1n, 則結(jié)點(diǎn)i無右孩子，否則其右孩子是結(jié)點(diǎn)2*i+1。,18,證明(2),(3): 對于i=1,左孩子是2, 右孩子是3。 對于i1,

9、可分兩種情況討論： 第一種情況：設(shè)第j層的第1個結(jié)點(diǎn)的編號為i(i=2j-1),則其左孩子必為第j+1層的第1個結(jié)點(diǎn)，其編號為 2j =2* 2j-1 =2i。 若2in，則無左孩子。右孩子編號為2i+1， 若2i+1n，則無右孩子。,19,第二種情況：假設(shè)第j層上某個結(jié)點(diǎn)的編號為i, 且2i+1n，則其左孩子為2i，右孩子為2i+1。 則編號為i+1的結(jié)點(diǎn)是編號為i的結(jié)點(diǎn)的右兄弟或堂兄弟，若它有左孩子，其編號必為2i+2=2(i+1),若它有右孩子，其編號必為2i+3=2(i+1)+1。,20,A B C D E F G H I J K L,完全二叉樹,（1）用性質(zhì)5驗證編號為6的結(jié)點(diǎn)的左右

10、孩子的情況。 （2）用性質(zhì)5驗證編號為7的結(jié)點(diǎn)的左右孩子的情況。,n=12,21,4.2.3 二叉樹的存儲結(jié)構(gòu),一、順序存儲結(jié)構(gòu),對于左圖所示的完全二叉樹，可用一維數(shù)組A10來存儲。,1 2 3 4 5 6 7 8 9 10,22,二叉樹的順序存儲表示 / 二叉樹的最大結(jié)點(diǎn)數(shù) #define MAX_TREE_SIZE 100 / 0號單元存儲根結(jié)點(diǎn) typedef DataType SqBiTreeMAX_TREE_SIZE; 如： SqBiTree bt; bt可用來存放一棵完全二叉樹。 顯然，這種順序存儲結(jié)構(gòu)僅適用于完全二叉樹。因為，在最壞的情況下，一棵深度為 k 且只有 k 個結(jié)點(diǎn)的單

11、支樹（樹中不存在度為 2 的結(jié)點(diǎn)）卻需要長度為2k-1的一維數(shù)組。,23,1 2 3 4 5 6 7 8,對于一般二叉樹，如果用數(shù)組存，則必須按完全二叉樹的形式來存儲。,存儲順序： 1 2 3 4 5 0 6 0 0 7 8,24,二、鏈?zhǔn)酱鎯Y(jié)構(gòu) 結(jié)點(diǎn)的結(jié)構(gòu)： lc data rc T,A B D C E H F G I 二叉鏈表,25,三叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)：,A B D C E H F G I 三叉鏈表,lc data p rc,T,26,二叉樹的鏈?zhǔn)酱鎯Ρ硎?1. 二叉鏈表 typedef struct BiTNode TElemType data; struct BiTNode *lchild, *r