武漢軟件工程職業(yè)學(xué)院《數(shù)據(jù)結(jié)構(gòu)講義》第12講樹和2叉樹

1、第十二講樹和二叉樹1. 掌握樹、二叉樹的基本概念和術(shù)語(yǔ)，2 .掌握二叉樹的性質(zhì)。3. 理解二叉樹的存儲(chǔ)結(jié)構(gòu)4. 熟悉建立二叉樹的二叉鏈表的算法。? 教學(xué)重點(diǎn)：二叉樹的定義、二叉樹的性質(zhì)? 教學(xué)難點(diǎn)：二叉樹的性質(zhì)? 授課內(nèi)容4.1 樹的定義和基本術(shù)語(yǔ)前面討論線性結(jié)構(gòu)的表示及其應(yīng)用實(shí)例。然而，線性結(jié)構(gòu)在許多實(shí)際應(yīng)用中不能明確、方便地表示數(shù)據(jù)元素之間的復(fù)雜關(guān)系。樹型結(jié)構(gòu)是一種應(yīng)用十分廣泛的非線性結(jié)構(gòu)，其中以二叉樹最為常用，它是以分支定義的層次結(jié)構(gòu)。樹型結(jié)構(gòu)在客觀世界中廣泛存在，如家族的家譜、各種社會(huì)組織機(jī)構(gòu)，一般都可以用樹來形象地表示。在計(jì)算機(jī)領(lǐng)域中，編譯系統(tǒng)中源 程序的語(yǔ)法結(jié)構(gòu)、數(shù)據(jù)庫(kù)系統(tǒng)中信息的

2、組織形式也用到樹形結(jié)構(gòu)。本章重點(diǎn)討論二叉樹的存儲(chǔ)結(jié)構(gòu)、各種操作及其應(yīng)用實(shí)例。4.1.1 樹的定義1.定義樹(tree )是由n ( n>0)個(gè)結(jié)點(diǎn)組成的有限集合T且滿足以下條件。1) 有且僅有一個(gè)特定的結(jié)點(diǎn)被稱為該樹的根( Root )。2) 除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)可分為m(m >0)個(gè)互不相交的集合 T1, T2，. ，Tm且其中每個(gè)集合又是一棵樹，并稱之為根的子樹(Subtree )。這是一個(gè)遞歸的定義，即在定義中又用到了樹的概念，這也反映了樹的固有特性。圖4-1-1是兩棵樹的示例。(a)是只有一個(gè)根結(jié)點(diǎn) A的樹。(b)是一棵由11個(gè)結(jié)點(diǎn)組 成的樹T，其中A是根結(jié)點(diǎn)，其余結(jié)點(diǎn)分

3、為三個(gè)互不相交的子集：T仁B，E，F(xiàn)，G K，T2=C，H，T3= D，I，J。T1, T2, T3也都是樹，且是根 A的子樹，這三棵子樹的根結(jié)點(diǎn) 分別為B、C D,每棵子樹還可以繼續(xù)劃分。A(a)【例4.1】樹結(jié)構(gòu)和非樹結(jié)構(gòu)的舉例GCBO (DIII'EF -G(b) 個(gè)非樹結(jié)構(gòu)(c)一個(gè)非樹結(jié)構(gòu)(d) 一個(gè)非樹結(jié)構(gòu)圖4-1-1( b)所示的樹，還可以用圖4-1-2所示的方法表示。(a)集合包含關(guān)系文氏圖法法法ABG KC H DJ '(A(B(E,F,G(K),C(H),D(I,J)(c)凹入法(b)廣義表法樹的基本術(shù)語(yǔ)樹的結(jié)點(diǎn)樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干個(gè)指向其子樹的分

4、支。結(jié)點(diǎn)的度和樹的度結(jié)點(diǎn)的度是結(jié)點(diǎn)的子樹的個(gè)數(shù)。樹的度是樹中結(jié)點(diǎn)度的最大值。例如圖4 1 1 (b)中，結(jié)點(diǎn)A和B的度為3,結(jié)點(diǎn)D的度為2;而樹T的度為3。葉子和分支結(jié)點(diǎn)度為零的結(jié)點(diǎn)稱為葉子或終端結(jié)點(diǎn)。度不為零的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。圖 4 1 1 (b)中，結(jié)點(diǎn)E、F、H K、I、J是葉子結(jié)點(diǎn)，結(jié)點(diǎn) B、C D G 是分支結(jié)點(diǎn)。孩子、雙親及兄弟結(jié)點(diǎn)某結(jié)點(diǎn)的各子樹的根稱為該結(jié)點(diǎn)的孩子，而該結(jié)點(diǎn)稱為孩子的雙親。具有相同雙親的結(jié)點(diǎn)互稱為兄弟。圖4 1 1 (b)中，A是結(jié)點(diǎn)B C、D的雙親，B C、D均是結(jié)點(diǎn)A的孩子，B C D互為兄弟。此外，一棵樹上除根結(jié)點(diǎn)以外的其他結(jié)點(diǎn) 稱為根的子孫，

5、而根結(jié)點(diǎn)是其子孫的祖先。結(jié)點(diǎn)的層次和樹的深度結(jié)點(diǎn)的層次值從根算起，根的層次值為1，其余結(jié)點(diǎn)的層次值為雙親結(jié)點(diǎn)層次值加 1;樹中結(jié)點(diǎn)的最大層次值稱為樹的深度或高度。圖4 1 1 (b)中，結(jié)點(diǎn)A、B E、K的層次值分別為1、2、3、4。樹T的深度為4。此外，雙親在同一層的結(jié) 點(diǎn)互稱為堂兄弟，如 G和H互為堂兄弟。4.2 二叉樹4.2.1 二叉樹的定義二叉樹是N (NA 0)個(gè)結(jié)點(diǎn)的有限集合。它或?yàn)榭諛?Nh 0),或由一個(gè)根結(jié)點(diǎn)和兩個(gè)分別稱為左子樹和右子樹的互不相交的子樹構(gòu)成。這個(gè)定義是遞歸的。圖4-2-1中展現(xiàn)五種基本形態(tài)不同的二叉樹。 應(yīng)特別注意，二叉樹種左子樹和右子樹是嚴(yán)格區(qū)分的，圖4-2

6、-1 ( c)與(d)是兩棵不同的二叉樹。(d)左子樹為(e)左右子樹均非空的二叉樹空的二叉樹空二叉樹(b)僅有(c )右子樹為根結(jié)點(diǎn)空的二叉樹圖4-2-1二叉樹的五種基本形二叉樹的重要性質(zhì)性質(zhì)1 二叉樹i (i > 1)層上至多有2i 1個(gè)結(jié)點(diǎn)。有圖4 2 2 (a)可知，根結(jié) 點(diǎn)在第1層上，這層結(jié)點(diǎn)數(shù)最多為1個(gè)，即20個(gè)；顯然第2層上最多有2個(gè)結(jié)點(diǎn)，即21第四章樹亂據(jù)結(jié)拘個(gè)；假設(shè)第i 1層結(jié)點(diǎn)最多有2i 2個(gè)，且每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，那么第 i層 上結(jié)點(diǎn)最多有 2 x 2i 2 = 2i 1個(gè)。性質(zhì)2 深度為k ( k> 1 )的二叉樹至多有 2 k 1個(gè)結(jié)點(diǎn)。根據(jù)性質(zhì)1，顯

7、然深度為k的二叉樹的結(jié)點(diǎn)總數(shù)至多為：k(位于第i層上的結(jié)點(diǎn)的最多數(shù))2i 12k 1性質(zhì)3在任意二叉樹中，若葉子結(jié)點(diǎn)(即度為零的結(jié)點(diǎn))個(gè)數(shù)為n0,度為1的結(jié)點(diǎn)數(shù)為n 1,度為2的結(jié)點(diǎn)個(gè)數(shù)為n2,那么有：n0= n2 + 1。設(shè)n代表二叉樹結(jié)點(diǎn)總數(shù)，那么n= n0+ n1 + n2()由于有n個(gè)結(jié)點(diǎn)的二叉樹總分支數(shù)為n- 1條，于是得n 1 = 0 x n0+ 1 x n1 + 2 x n2 ()將式()代入式(),得n0= n2 + 1在研究后面的性質(zhì)之前，先介紹兩種特殊形態(tài)的二叉樹：滿二叉樹和完全二叉樹。一棵深度為k并且含有2k 1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹，這種數(shù)的特點(diǎn)是每層上的結(jié)點(diǎn)數(shù)都是

8、最大結(jié)點(diǎn)數(shù)，如圖4 2 2 (a)所示。對(duì)滿二叉樹的結(jié)點(diǎn)可以從根結(jié)點(diǎn)開始自上向下，自左向右順序編號(hào)，圖4 2 2 ( a)中每個(gè)結(jié)點(diǎn)斜上角的數(shù)字即是該結(jié)點(diǎn)的編號(hào)。深度為k，含有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每個(gè)結(jié)點(diǎn)的編號(hào)與相應(yīng)滿二叉樹結(jié)點(diǎn)順序編 號(hào)從1到n相對(duì)應(yīng)時(shí)，則稱此二叉樹為完全二叉樹，如圖4 2 2 (b)所示。而圖4 2 2(c)則不是完全二叉樹。(a)滿二叉樹(b)完全二叉樹(c)非完全二叉樹圖4 2 2滿二叉樹和完全二叉樹性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的完全二叉樹， 其深度為+ 1(其中表示不大于 x的最大整數(shù)) 性質(zhì)5 若對(duì)有n個(gè)結(jié)點(diǎn)的完全二叉樹進(jìn)行順序編號(hào)( K i <n),那么，對(duì)

9、于編號(hào)為 i (i > 1)的結(jié)點(diǎn)，有:當(dāng)i = 1時(shí)，該結(jié)點(diǎn)為根，它無(wú)雙親結(jié)點(diǎn)；當(dāng)i > 1時(shí)，該結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為；若2i v n,則有編號(hào)為2i的左孩子，否則沒有左孩子；霰禍結(jié)狗第四章樹若2i + 1 v n,則有編號(hào)為2i + 1的右孩子，否則沒有右孩子； 對(duì)照?qǐng)D4 2 2 (a)或圖4 2 2 ( b),讀者可看到右性質(zhì) 5所描述的結(jié)點(diǎn)與編號(hào)的對(duì) 應(yīng)關(guān)系。423二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹可以采用順序存儲(chǔ)結(jié)構(gòu)或鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。1順序存儲(chǔ)結(jié)構(gòu)用一組連續(xù)的存儲(chǔ)單元存放二叉樹中的元素，這對(duì)于滿二叉樹和完全二叉樹是非常合適的。假設(shè)將圖4-2-2 (a)所示的滿二叉樹存放在一維數(shù)組bt中

10、，可以發(fā)現(xiàn)結(jié)點(diǎn)的編號(hào)恰好與數(shù)組元素的下表相對(duì)應(yīng)(見圖 4-2-3 )。根據(jù)二叉樹性質(zhì)5,結(jié)點(diǎn)在一維數(shù)組中的相對(duì)位置隱含著結(jié)點(diǎn)之間的關(guān)系。因此在數(shù)組bt中可以方便地由某結(jié)點(diǎn)bti的下標(biāo)i找到它們的雙親結(jié)點(diǎn)bti/2，或左、右孩子結(jié)點(diǎn)2i 、bt2i+1.2. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中最常用的是二叉鏈表和三叉鏈表。二叉鏈表的每個(gè)結(jié)點(diǎn)有一個(gè)數(shù)據(jù)域和兩個(gè)指針域，一個(gè)指針指向左孩子，另一個(gè)指向右孩子。結(jié)點(diǎn)結(jié)構(gòu)描述為：typedef struct btno deELEMTP data;struct btnode *lchild,*rchlid;BTNode;例如圖4-2-4 (a)中的二叉樹 T

11、,它的二叉鏈表如圖 4-2-4 (b)所示，其中bt是一 個(gè)*BTNode類型的變量，并且指向根結(jié)點(diǎn)，通常對(duì)于二叉鏈表的操作都是從它開始的。在實(shí)際操作中，如經(jīng)常需要尋找結(jié)點(diǎn)的雙親，便可以采用三叉鏈表的形式。三叉鏈表的結(jié)點(diǎn)比二叉鏈表結(jié)點(diǎn)多一個(gè)指向雙親的指針域。其結(jié)點(diǎn)結(jié)構(gòu)描述為：typedef struct btnode _ p ELEMTP data;struct btnode * pare nt, *lchild, *rchild; BTNode_p;三叉鏈表如圖4-2-4 ( c)所示。(a)二叉樹T(b)二叉鏈表(c)三叉鏈表圖4-2-4二叉樹的鏈表存儲(chǔ)結(jié)構(gòu)424 二叉樹的存儲(chǔ)結(jié)構(gòu)建立二叉

12、鏈表的方法不止一種。這里介紹的方法的原理是利用二叉樹的性質(zhì)5。對(duì)于棵任意的二叉樹，先按滿二叉樹對(duì)其結(jié)點(diǎn)進(jìn)行編號(hào)，如圖4-2-5(a)所示。雖然此二叉樹并i1235714chABCEDF非滿二叉樹，結(jié)點(diǎn)的編號(hào)并不連續(xù)，但結(jié)點(diǎn)編號(hào)之間的關(guān)系是滿足二叉樹的性質(zhì)5的。(b)圖4 2 5二叉樹及數(shù)據(jù)表算法實(shí)現(xiàn)時(shí)，需設(shè)置一個(gè)輔助向量p,用于存放指向結(jié)點(diǎn)的指針，如pi中存放編號(hào)為i的結(jié)點(diǎn)的指針(該結(jié)點(diǎn)的地址)。圖4-2-5 (a)的原是數(shù)據(jù)序列如圖4-2-5 ( b)所示，按此表一一輸入數(shù)對(duì)(結(jié)點(diǎn)編號(hào)i和數(shù)據(jù)ch)。每輸入一對(duì)數(shù)(i , ch),便產(chǎn)生一個(gè)新的結(jié)點(diǎn)s,同時(shí)將該結(jié)點(diǎn)的指針保存在pi中。當(dāng)i = 1時(shí)，所產(chǎn)生的結(jié)點(diǎn)為根結(jié)點(diǎn)。當(dāng)i>1時(shí)，由性質(zhì)5可知：其雙親結(jié)點(diǎn)的編號(hào)j = i/2。如果i為偶數(shù)，則它是雙親的左孩子，就讓pj->lchild = s;如果i為奇數(shù)，則它是雙親的右孩子，就讓pj->rchild = s。這樣就將每個(gè)結(jié)點(diǎn)與其雙親結(jié)點(diǎn)相連，從而建立起了二叉鏈表。算法見算法4.1。算法4.1#defi ne MAXNUM 20】uno宀 蘭。03二03- P% P% : =ueos X = - II。二9U S: 汪 u_d宀 p