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

1、武漢軟件工程職業(yè)學(xué)院 數(shù)據(jù)結(jié)構(gòu)講義第 12 講- 樹和 2 叉樹第四章樹第十二講樹和二叉樹1掌握樹、二叉樹的基本概念和術(shù)語，。2掌握 二叉樹的性質(zhì) 。3. 理解二叉樹的存儲結(jié)構(gòu)4. 熟悉建立二叉樹的二叉鏈表的算法。教學(xué)重點：二叉樹的定義、二叉樹的性質(zhì)教學(xué)難點：二叉樹的性質(zhì)授課內(nèi)容4.1樹的定義和基本術(shù)語前面討論線性結(jié)構(gòu)的表示及其應(yīng)用實例。 然而，線性結(jié)構(gòu)在許多實際應(yīng)用中不能明確、 方便地表示數(shù)據(jù)元素之間的復(fù)雜關(guān)系。 樹型結(jié)構(gòu)是一第四章樹種應(yīng)用十分廣泛的非線性結(jié)構(gòu)， 其中以二叉樹最為常用，它是以分支定義的層次結(jié)構(gòu)。 樹型結(jié)構(gòu)在客觀世界中廣泛存在， 如家族的家譜、 各種社會組織機構(gòu)， 一般都可以用

2、樹來形象地表示。 在計算機領(lǐng)域中，編譯系統(tǒng)中源程序的語法結(jié)構(gòu)、數(shù)據(jù)庫系統(tǒng)中信息的組織形式也用到樹形結(jié)構(gòu)。本章重點討論二叉樹的存儲結(jié)構(gòu)、 各種操作及其應(yīng)用實例。樹的定義1. 定義樹（tree ）是由 n（n0）個結(jié)點組成的有限集合 T 且滿足以下條件。1）有且僅有一個特定的結(jié)點被稱為該樹的根（ Root）。2）除根結(jié)點之外的其余結(jié)點可分為m（m 0）個互不相交的集合T1，T2，.，Tm，且其中每個集合又是一棵樹，并稱之為根的子樹（ Subtree ）。這是一個遞歸的定義， 即在定義中又用到了樹的概念，這也反映了樹的固有特性。圖 4-1-1 是兩棵樹的示例。（a）是只有一個第四章樹根結(jié)點 A 的樹

3、。（b）是一棵由 11 個結(jié)點組成的樹 T，其中 A 是根結(jié)點，其余結(jié)點分為三個互不相交的子集： T1=B，E，F(xiàn)，G，K，T2C，H，T3D，I ，J 。T1，T2，T3 也都是樹，且是根 A 的子樹，這三棵子樹的根結(jié)點分別為 B、C、D，每棵子樹還可以繼續(xù)劃分。TAA（ aT1BT2CT3 DE FGH IJK（ b圖 4-1-1樹的示例【例 4.1 】樹結(jié)構(gòu)和非樹結(jié)構(gòu)的舉例AAAABCBCBCDBCD第四章樹DEFGDEFEEFGFGHI一棵樹結(jié)構(gòu)(c) 一個非樹結(jié)構(gòu)一個非樹結(jié)構(gòu)(d)一個非樹結(jié)構(gòu)圖 4-1-1 （b）所示的樹，還可以用圖 4-1-2 所示的方法表示。ABABDEGFFI

4、GKJKCCHHDI（ a）集合包含關(guān)系文氏圖法法法J（ c）凹入法(A(B(E,F,G(K),C(H),D(I,J)第四章樹樹的基本術(shù)語樹的結(jié)點 樹的結(jié)點包含一個數(shù)據(jù)元素及若干個指向其子樹的分支。結(jié)點的度和樹的度 結(jié)點的度是結(jié)點的子樹的個數(shù)。 樹的度是樹中結(jié)點度的最大值。 例如圖 411（b）中，結(jié)點 A 和 B 的度為 3，結(jié)點 D 的度為 2；而樹 T 的度為 3。葉子和分支結(jié)點度為零的結(jié)點稱為葉子或終端結(jié)點。度不為零的結(jié)點稱為分支結(jié)點或非終端結(jié)點。 圖 411（b）中，結(jié)點 E、F、H、K、I 、J 是葉子結(jié)點，結(jié)點 B、C、D、G是分支結(jié)點。孩子、雙親及兄弟結(jié)點 某結(jié)點的各子樹的根稱

5、為該結(jié)點的孩子， 而該結(jié)點稱為孩子的雙親。具有相同雙親的結(jié)點互稱為兄弟。圖 4 1 1（b）中， A 是結(jié)點 B、C、D的雙親， B、C、D均是結(jié)點 A 的孩子， B、C、D互為兄弟。此外，一棵樹上除根結(jié)點以外的其他結(jié)點稱為根的子孫，而根結(jié)點是其子孫的祖先。結(jié)點的層次和樹的深度 結(jié)點的層次值從根算起，根的層次值為 1，其余結(jié)點的層次值第四章樹為雙親結(jié)點層次值加 1；樹中結(jié)點的最大層次值稱為樹的深度或高度。圖 411（b）中，結(jié)點 A、B、E、K 的層次值分別為 1、2、3、4。樹 T 的深度為 4。此外，雙親在同一層的結(jié)點互稱為堂兄弟，如 G和 H 互為堂兄弟。4.2二叉樹二叉樹的定義二叉樹是

6、 N（N0）個結(jié)點的有限集合。它或為空樹（ N0），或由一個根結(jié)點和兩個分別稱為左子樹和右子樹的互不相交的子樹構(gòu)成。 這個定義是遞歸的。 圖 4-2-1 中展現(xiàn)五種基本形態(tài)不同的二叉樹。 應(yīng)特別注意， 二叉樹種左子樹和右子樹是嚴格區(qū)分的，圖 4-2-1 （c）與（ d）是兩棵不同的二叉樹。?(a) 空 二 叉(b) 僅(c) 右 子 樹(d) 左 子 樹(e) 左 右子樹 均有為為非圖 4-2-1二叉樹的五種基本形第四章樹二叉樹的重要性質(zhì)性質(zhì) 1二叉樹 i （i 1）層上至多有 2i1 個結(jié)點。有圖 422（a）可知，根結(jié)點在第 1 層上，這層結(jié)點數(shù)最多為 1 個，即 20 個；顯然第 2 層

7、上最多有 2 個結(jié)點，即 21 個；假設(shè)第 i 1 層結(jié)點最多有 2i 2 個，且每個結(jié)點最多有兩個孩子，那么第 i 層上結(jié)點最多有 2× 2i 22i 1 個。性質(zhì) 2深度為 k（k1）的二叉樹至多有 2 k 1 個結(jié)點。根據(jù)性質(zhì) 1，顯然深度為 k 的二叉樹的結(jié)點總數(shù)至多為：kk(位于第 i 層上的 結(jié)點的最多 數(shù)）2i 12k 1i 1i 1性質(zhì) 3 在任意二叉樹中，若葉子結(jié)點（即度為零的結(jié)點）個數(shù)為 n0，度為 1 的結(jié)點數(shù)為n1，度為 2 的結(jié)點個數(shù)為 n2，那么有： n0n2 1。設(shè) n 代表二叉樹結(jié)點總數(shù)，那么nn0n1n2（）第四章樹由于有 n 個結(jié)點的二叉樹總分支數(shù)

8、為 n 1 條，于是得n10×n01×n12×n2（）將式（）代入式（）, 得n0n21在研究后面的性質(zhì)之前， 先介紹兩種特殊形態(tài)的二叉樹：滿二叉樹和完全二叉樹。一棵深度為 k 并且含有 2k1 個結(jié)點的二叉樹稱為滿二叉樹， 這種數(shù)的特點是每層上的結(jié)點數(shù)都是最大結(jié)點數(shù)，如圖 422（a）所示。對滿二叉樹的結(jié)點可以從根結(jié)點開始自上向下，自左向右順序編號，圖 422（a）中每個結(jié)點斜上角的數(shù)字即是該結(jié)點的編號。深度為 k，含有 n 個結(jié)點的二叉樹， 當且僅當其每個結(jié)點的編號與相應(yīng)滿二叉樹結(jié)點順序編號從 1 到 n 相對應(yīng)時，則稱此二叉樹為完全二叉樹，如圖 4 2 2（

9、b）所示。而圖 422（c）則不是完全二叉樹。第四章樹21 A1A1 A32323BCBCBC456456456D EFGDEFE FD（a）滿二叉樹（ b）完全二叉樹（ c）非完全二叉樹圖4 22滿二叉樹和完全二叉樹性質(zhì) 4 具有 n 個結(jié)點的完全二叉樹，其深度為 1（其中表示不大于 x 的最大整數(shù)）。性質(zhì) 5 若對有 n 個結(jié)點的完全二叉樹進行順序編號（1i n），那么，對于編號為 i （ i 1）的結(jié)點，有：當 i 1 時，該結(jié)點為根，它無雙親結(jié)點；當 i 1 時，該結(jié)點的雙親結(jié)點編號為；若 2i n，則有編號為 2i 的左孩子，否則沒有左孩子；若 2i 1n，則有編號為 2i 1 的右

10、孩子，否則沒有右孩子；對照圖 422（ a）或圖 422（b）,讀者可看到右性質(zhì) 5 所描述的結(jié)點與編號的對應(yīng)關(guān)系。第四章樹二叉樹的存儲結(jié)構(gòu)二叉樹可以采用順序存儲結(jié)構(gòu)或鏈式存儲結(jié)構(gòu)。1. 順序存儲結(jié)構(gòu)用一組連續(xù)的存儲單元存放二叉樹中的元素，這對于滿二叉樹和完全二叉樹是非常合適的。假設(shè)將圖 4-2-2 （ a）所示的滿二叉樹存放在一維數(shù)組 bt 中，可以發(fā)現(xiàn)結(jié)點的編號恰好與數(shù)組元素的下表相對應(yīng)（見圖 4-2-3 ）。根據(jù)二叉樹性質(zhì) 5，結(jié)點在一維數(shù)組中的相對位置隱含著結(jié)點之間的關(guān)系。因此在數(shù)組 bt 中可以方便地由某結(jié)點 bti 的下標 i 找到它們的雙親結(jié)點 bti/2 ，或左、右孩子結(jié)點 2

11、i 、bt2i+1.2. 鏈式存儲結(jié)構(gòu)在二叉樹鏈式存儲結(jié)構(gòu)中最常用的是二叉鏈表和三叉鏈表。 二叉鏈表的每個結(jié)點有一個數(shù)據(jù)域和兩個指針域， 一個指針指向左孩子， 另一個指向右孩子。結(jié)點結(jié)構(gòu)描述為：typedef struct btnodeELEMTP data;第四章樹struct btnode *lchild,*rchlid;BTNode;例如圖 4-2-4 （a）中的二叉樹 T，它的二叉鏈表如圖 4-2-4 （b）所示，其中 bt 是一個*BTNode類型的變量，并且指向根結(jié)點，通常對于二叉鏈表的操作都是從它開始的。在實際操作中，如經(jīng)常需要尋找結(jié)點的雙親，便可以采用三叉鏈表的形式。三叉鏈表的

12、結(jié)點比二叉鏈表結(jié)點多一個指向雙親的指針域。其結(jié)點結(jié)構(gòu)描述為：typedef struct btnode _ p ELEMTPdata;struct btnode * parent, *lchild,*rchild; BTNode_p;三叉鏈表如圖 4-2-4 （c）所示。第四章樹btbtAAABB CBCD D E D EFFF（ a）二叉樹 T（b）二叉鏈表（ c）三叉鏈表圖4-2-4二叉樹的鏈表存儲二叉樹的存儲結(jié)構(gòu)建立二叉鏈表的方法不止一種。 這里介紹的方法的原理是利用二叉樹的性質(zhì) 5。對于一棵任意的二叉樹，先按滿二叉樹對其結(jié)點進行編號，如圖 4-2-5(a) 所示。雖然此二叉樹并非滿二叉

13、樹，結(jié)點的編號并不連續(xù)， 但結(jié)點編號之間的關(guān)系是滿足二叉樹的性質(zhì) 5 的。1A23BCi123571457chABCEDFED14（a）F（b）圖 425 二叉樹及數(shù)據(jù)表算法實現(xiàn)時，需設(shè)置一個輔助向量 p，用于第四章樹存放指向結(jié)點的指針，如 pi 中存放編號為 i 的結(jié)點的指針（該結(jié)點的地址） 。圖 4-2-5 （a）的原是數(shù)據(jù)序列如圖 4-2-5 （b）所示，按此表一一輸入數(shù)對（結(jié)點編號 i 和數(shù)據(jù) ch）。每輸入一對數(shù)（ i ，ch），便產(chǎn)生一個新的結(jié)點 s，同時將該結(jié)點的指針保存在 pi 中。當 i 1 時，所產(chǎn)生的結(jié)點為根結(jié)點。 當 i>1 時，由性質(zhì) 5 可知：其雙親結(jié)點的編號 j i/2 。如果 i 為偶數(shù)，則它是雙親的左孩子，就讓 pj->lchild s；如果 i 為奇數(shù)，則它是雙親的右孩子，就讓 pj->rchild s。這樣就將每個結(jié)點與其雙親結(jié)點相連，從而建立起了二叉鏈表。 算法見算法4.1 。算法 4.1#define MAXNUM 20BtNode *pMAXNUM+1;BtNode *Creat_Bt (void)printf(n enter i