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

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

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

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

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

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

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

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

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

9、b）所示。而圖 422（c）則不是完全二叉樹(shù)。第四章樹(shù)21 A1A1 A32323BCBCBC456456456D EFGDEFE FD（a）滿二叉樹(shù)（ b）完全二叉樹(shù)（ c）非完全二叉樹(shù)圖4 22滿二叉樹(shù)和完全二叉樹(shù)性質(zhì) 4 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，其深度為 1（其中表示不大于 x 的最大整數(shù)）。性質(zhì) 5 若對(duì)有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)進(jìn)行順序編號(hào)（1i n），那么，對(duì)于編號(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 n，則有編號(hào)為 2i 的左孩子，否則沒(méi)有左孩子；若 2i 1n，則有編號(hào)為 2i 1 的右

10、孩子，否則沒(méi)有右孩子；對(duì)照?qǐng)D 422（ a）或圖 422（b）,讀者可看到右性質(zhì) 5 所描述的結(jié)點(diǎn)與編號(hào)的對(duì)應(yīng)關(guān)系。第四章樹(shù)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)可以采用順序存儲(chǔ)結(jié)構(gòu)或鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。1. 順序存儲(chǔ)結(jié)構(gòu)用一組連續(xù)的存儲(chǔ)單元存放二叉樹(shù)中的元素，這對(duì)于滿二叉樹(shù)和完全二叉樹(shù)是非常合適的。假設(shè)將圖 4-2-2 （ a）所示的滿二叉樹(shù)存放在一維數(shù)組 bt 中，可以發(fā)現(xiàn)結(jié)點(diǎn)的編號(hào)恰好與數(shù)組元素的下表相對(duì)應(yīng)（見(jiàn)圖 4-2-3 ）。根據(jù)二叉樹(shù)性質(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) 2

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

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

13、樹(shù)，結(jié)點(diǎn)的編號(hào)并不連續(xù)， 但結(jié)點(diǎn)編號(hào)之間的關(guān)系是滿足二叉樹(shù)的性質(zhì) 5 的。1A23BCi123571457chABCEDFED14（a）F（b）圖 425 二叉樹(shù)及數(shù)據(jù)表算法實(shí)現(xiàn)時(shí)，需設(shè)置一個(gè)輔助向量 p，用于第四章樹(shù)存放指向結(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)相連，從而建立起了二叉鏈表。 算法見(jiàn)算法4.1 。算法 4.1#define MAXNUM 20BtNode *pMAXNUM+1;BtNode *Creat_Bt (void)printf(n enter i