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

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

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

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

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

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

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

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

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

9、于編號為 i (i > 1)的結點，有:當i = 1時，該結點為根，它無雙親結點；當i > 1時，該結點的雙親結點編號為；若2i v n,則有編號為2i的左孩子，否則沒有左孩子；霰禍結狗第四章樹若2i + 1 v n,則有編號為2i + 1的右孩子，否則沒有右孩子； 對照圖4 2 2 (a)或圖4 2 2 ( b),讀者可看到右性質(zhì) 5所描述的結點與編號的對 應關系。423二叉樹的存儲結構二叉樹可以采用順序存儲結構或鏈式存儲結構。1順序存儲結構用一組連續(xù)的存儲單元存放二叉樹中的元素，這對于滿二叉樹和完全二叉樹是非常合適的。假設將圖4-2-2 (a)所示的滿二叉樹存放在一維數(shù)組bt中

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

11、,它的二叉鏈表如圖 4-2-4 (b)所示，其中bt是一 個*BTNode類型的變量，并且指向根結點，通常對于二叉鏈表的操作都是從它開始的。在實際操作中，如經(jīng)常需要尋找結點的雙親，便可以采用三叉鏈表的形式。三叉鏈表的結點比二叉鏈表結點多一個指向雙親的指針域。其結點結構描述為：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二叉樹的鏈表存儲結構424 二叉樹的存儲結構建立二叉

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