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

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

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

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

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

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

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

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

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

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

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

12、結點比二叉鏈表結點多一個指向雙親的指針域。其結點結構描述為：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二叉樹的鏈表存儲二叉樹的存儲結構建立二叉鏈表的方法不止一種。 這里介紹的方法的原理是利用二叉樹的性質 5。對于一棵任意的二叉樹，先按滿二叉樹對其結點進行編號，如圖 4-2-5(a) 所示。雖然此二叉樹并非滿二叉

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