1、第6章 樹 數據結構（C描述） 目錄目錄 在許多領域許多問題不能或難用線性結構表示（哈夫曼編碼、判定問題），故研究非線性的數據結構。樹是一種應用十分廣泛的非線性數據結構。6.1 樹的基本概念樹的基本概念6.1.1 樹的定義樹的定義樹的定義 樹是由n（n0）個結點組成的有限集合。若n=0，稱為空樹；若n0，則稱為非空樹，在任一棵非空樹中：（1）有一個特定的稱為根（root）的結點。它只有直接后繼，但沒有直接前驅；（2）除根結點以外的其它結點可以劃分為m（m0）個互不相交的有限集合T0，T1，Tm-1，且每個集合Ti（i=0,1,m-1）本身又是一棵樹，稱為根的子樹根的子樹。由此可知，樹的定義是一

2、個遞歸的定義遞歸的定義，即樹的定義中又用到了樹的概念。 從定義中看出樹結構具有以下特點：（1）有且僅有一個結點沒有直接前驅，即根結點。（2）除根結點之外，其余所有結點有且僅有一個直接前趨結點。（3）包括根結點在內，每個結點可以有多個直接后繼結點。從此可見，樹型結構的特點是，數據元素之間存在著一對多的關系。樹的結構參見圖6-1。 A A B C D I H G F E J K L M （a）空樹 （b）僅含有根結點的樹 （c） 含有多個結點的樹 圖 6-1 樹的示意圖 在圖6-1(c)中，樹的根結點為A，該樹還可以分為三個互不相交子集T0，T1，T2，具體請參見圖6-2，其中T0=B，E，F，J

3、，K，L，T1=C，G，T2=D，H，I，M而T0，T1，T2又可以分解成若干棵不相交子樹。如：T0可以分解成T00，T01兩個不相交子集，T00=E，J，K，L，T01=F，而T00又可以分為三個不相交子集T000，T001，T002，其中，T000=J，T001=K，T002=L。 C G B E F J K L D H I M (a) T0子樹 (b)T1子樹 (c)T2子樹 圖 6-2 樹的三個子樹 6.1.2 基本術語基本術語1.樹的結點指樹中的一個數據元素，一般用一個字母表示。 2.結點的度 一個結點包含子樹的數目，稱為該結點的度。 3.樹葉（葉子） 度為0的結點，稱為葉子結點或樹

4、葉，也叫終端結點。 4.分支結點（非終端結點）除葉子結點外的所有結點，為分支結點。通常又將除根結點之外的分支結點稱為內部結點內部結點。6.雙親結點若結點X有子女Y，則X為Y的雙親結點。 7.祖先結點8.子孫結點某一結點的子女的子女為該結點子孫。 5.孩子結點若結點X有子樹，則子樹的根結點為X的孩子結點，也稱為孩子。如圖6-1（c）中A的孩子為B，C，D。 10結點的層次從根結點開始定義，根為第一層，根的孩子為第二層，依次類推。 11. 樹的高度樹的高度（深度深度） 樹中結點所處的最大層數稱為樹的高度，如空樹的高度為0，只有一個根結點的樹高度為1。12.樹的度樹的度樹中結點度的最大值稱為樹的度。

5、9.兄弟結點具有同一個雙親的結點，稱為兄弟結點。 13. 有序樹有序樹 若一棵樹中所有子樹從左到右的排序是有順序的，不能顛倒次序。稱該樹為有序樹。 14. 無序樹無序樹 若一棵樹中所有子樹的次序無關緊要，則稱為無序樹。 15森林（樹林）森林（樹林） 若干棵互不相交的樹組成的集合為森林。一棵樹可以看成是一個特殊的森林。樹與森林的關系 6.1.3 樹的表示樹的表示1樹形結構表示法樹形結構表示法 （掌握）（掌握）具體參 見圖6-1 。 A A B C D I H G F E J K L M （a）空樹 （b）僅含有根結點的樹 （c） 含有多個結點的樹 圖 6-1 樹的示意圖 2. 凹入法表示法凹入法

6、表示法具體參見圖6-3 A B E J K L F C G D H M I 圖 6-3 圖 6-1(c)的樹的凹入法表示 3. 嵌套集合表示法嵌套集合表示法具體參 見圖6-4 。 A B E J K L F C G D H M I 圖 6-4 圖 6-1(c)的樹的集合表示 4.廣義表表示法廣義表表示法 對圖7-1（c）的樹結構，廣義表表示法可表示為：A（B（E（J，K，L），F），C（G），D（H（M），I）6.2 樹的存儲結構樹的存儲結構 僅考慮鏈式存儲結構鏈式存儲結構，有兩種：多重鏈表表示法、二重鏈表表示法6.2.1 多重鏈表表示法多重鏈表表示法 每個結點由一個數據域和若干個指針域若干個

7、指針域組成，其中，每個指針域指向該結點的一個孩子。一棵樹中不同結點的度數可能不同，每個結點設置的指針域的數目可能就有所不同。通常有下面的兩種方案：1、定長結點的多重鏈表表示法、定長結點的多重鏈表表示法取樹的度數樹的度數作為每個結點的指針域的個數每個結點的指針域的個數。缺點：由于樹中多數結點的度可能小于樹的度，因而這種方法將會導致許多結點的部分指針域為空，造成空間的浪費。2、不定長結點的多重鏈表示法、不定長結點的多重鏈表示法 樹中每個結點都取自己的度數作為指針域的個數，顯然，對于葉結點就不必設指針域。另外，每個結點除了數據域、指針域外，還應設一個度數域用來指出該結點的度數，即指出該結點中指針域的

8、個數。6.2.2 二重鏈表表示法二重鏈表表示法 這種方法是對樹中的每個結點設三個域：數據域和2個指針域，第一個指針域給出該結點的第一個孩子（即最左邊子樹的根結點，長子長子）的地址，第二個指針域給出該結點的右邊第一個兄弟結點（次弟次弟）的地址。 樹的三重鏈表表示，增加了一個指針域即給出該結點的雙親結點的地址。6.3 二叉樹二叉樹 在樹型結構中，有一類簡單而又重要的樹，它的每個結點最多只有2棵子樹，這種樹被稱為二叉樹。6.3.1 二叉樹的定義二叉樹的定義1二叉樹的定義二叉樹的定義 和樹結構定義類似，二叉樹的定義也可以遞歸形式給出：二叉樹是n（n0）個結點的有限集，它或者是空集（n=0），或者由一個

9、根結點及兩棵不相交的左子樹和右子樹組成。 二叉樹的特點：二叉樹的特點： 每個結點最多有兩個孩子，或者說，在二叉樹中，不存在度大于2的結點 二叉樹是有序樹（樹為無序樹），其子樹的順序不能顛倒。因此，二叉樹有五種不同的形態，參見下圖。 L R L R (a) (b) (c) (d) (e) 圖 6-5 二叉樹的五種不同的形態 6.3.2 二叉樹的性質二叉樹的性質性質性質1 若二叉樹的層數從1開始，則二叉樹的第k層結點數，最多為個 （k0）。可以用數學歸納法證明之。性質性質2 深度（高度）為k的二叉樹最大結點數為 （k0）證明： 深度為k的二叉樹，若要求結點數最多，則必須每一層的結點數都為最多，由性

10、質1可知，最大結點數應為每一層最大結點數之和。即為： 20+21+2k-1=2k-1。2k-12k-1性質性質3 對任意一棵二叉樹，如果葉子結點個數為n0，度為2的結點個數為n2，則有n0=n2+1。證明：設二叉樹中度為1的結點個數為n1，根據二叉樹的定義（二叉樹中所有結點的度均小于或等于2)可知，該二叉樹的結點總數 n=n0+n1+n2 (1)。 再看二叉樹中的分支數。除了根結點外，其余結點都有一個分支進入。設B為分支總數，則 n=B+1由于這些分支是由度為1或2的結點射出的，所以又有B=n1+2*n2 于是得：n=n1+2n2+1 (2)由（1）和（2）得：n0=n2+1下面討論兩種特殊的

11、二叉樹：滿二叉樹和完全二叉樹。 滿二叉樹滿二叉樹 深度為k具有2k-1個結點的二叉樹，稱為滿二叉樹。或或者說：者說：如果一棵二叉樹中任何結點，或者是葉結點，或者是有兩棵非空子樹，且葉子結點都集中在二叉樹的最下一層，這樣的二叉樹稱為滿二叉樹。 從定義可知：必須是二叉樹的每一層上的結點數都達到最大，否則就不是滿二叉樹。例：深（高）度為4的滿二叉樹如圖（15個結點） 可以對滿二叉樹的結點進行編號，約定編號從根結點起，自上而下，自左而右，由此引出完全二叉樹的定義。完全二叉樹完全二叉樹 如果一棵具有n個結點的深度為k的二叉樹，它的每一個結點都與深度為k的滿二叉樹中編號為1 n的結點一一對一一對應應，則稱

12、這棵二叉樹為完全二叉樹。（例：k=3,n=4,5,6） 從滿二叉樹及完全二叉樹定義可以得出如下結論： 滿二叉樹一定是一棵完全二叉樹 反之完全二叉樹不一定是一棵滿二叉樹。 滿二叉樹的葉子結點全部在最底層，而完全二叉樹的葉子結點可以分布在最下面兩層。深度為4的滿二叉樹和完全二叉樹（8個結點）如圖6-6所示。 A B C D E F G H I J K L M N O A B C D E G H F （a）滿二叉樹 (b)完全二叉樹 圖 6-6 滿二叉樹和完全二叉樹示意圖 性質性質4 具有n個結點的完全二叉樹高度為log2(n)+1 或 log2（n+1） 。（注意x表示取不大于x（即）的最大整數，

13、也叫做對x下取整，x表示取不小于x（即）的最小整數，也叫做對x上取整。)1、二叉樹中度為0的結點數為50，度為1的結點數為30，總結點數為_。湖南大學考研題湖南大學考研題性質3：n0=n2+12、樹最合適用來表示_。A 有序數據元素 B 無序數據元素 C 元素之間無聯系的數據 D元素之間分支層次關系的數據3、對于有n 個結點的二叉樹, 其高度為（ ）【武漢交通科技大學 一、5 (4分)】 Anlog2n Blog2n Clog2n+1 D不確定4、深度為h的滿m叉樹的第k層有（ ）個結點。(1 k h)【北京航空航天大學 一、4（2分）】 Amk-1 Bmk-1 Cmh-1 Dmh-15、在一

14、棵高度為k的滿二叉樹中，結點總數為（ ）【北京工商大學 一、3 (3分)】 A2k-1 B2k C2k-1 Dlog2k+16、高度為 K的二叉樹最大的結點數為（ ）。 【山東大學 二、3 (1分)】A2k B2k-1 C2k -1 D2k-1-17、若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數是（ ）A9 B11 C15 D不確定 【北京工商大學一.7(3分)】性質性質3 對任意一棵二叉樹，如果葉子結點個數為n0，度為2的結點個數為n2，則有n0=n2+1。6.3.3 二叉樹的存貯結構二叉樹的存貯結構1順序存貯結構順序存貯結構 即用一維數組TM來存儲二叉樹的數據元

15、素，按照二叉樹的結點層次編號結點層次編號依次來存放。如：見圖這種結構適合于存儲完全二叉樹和滿二叉樹適合于存儲完全二叉樹和滿二叉樹，若是一般二叉樹應如何處理？必須按完全二叉樹完全二叉樹的形式來存貯樹中的結點，這就要虛設很多空結點才能使它成為一棵完全二叉樹。如圖可見這將造成空間的浪費。例：k=3的一般二叉樹 A B C D E F G A B C D . A B C D E F G A B C D 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 (a)滿二叉樹的存儲形式 (b)非完全二叉樹的存儲形式 圖 6-7 二叉樹的順序存儲形式 對于一棵二叉樹,若采用順序存貯時,當它為完全

16、二叉樹（或滿二叉樹）時,比較方便,若為非完全二叉樹,將會浪費大量存貯存貯單元。 最壞情況的非完全二叉樹是全部只有右分支,設高度為K,則需占用個 存貯單元,而實際只有k個元素,實際只需k個存儲單元。因此，對于非完全二叉樹非完全二叉樹，宜采用下面的鏈式存儲結構鏈式存儲結構。2K-12二叉鏈表存貯結構二叉鏈表存貯結構 （1）二叉鏈表表示）二叉鏈表表示將一個結點分成三部分,一部分存放結點本身信息,另外兩部分為指針,分別存放左、右孩子的地址。二叉鏈表中一個結點可描述為: 1child data rchild 對于圖6-7所示二叉樹,用二叉鏈表形式描述見圖6-8。 A B C D E F G root A

17、 root B C D (a)完全二叉樹的鏈表 (b)非完全二叉樹的二叉鏈表 圖 6-8 二叉樹的二叉鏈表表示法 （2）二叉鏈表的類型說明）二叉鏈表的類型說明二叉鏈表的數據類型描述如下:typedef struct btnode int data ; /結點數據類型struct btnode *lchild, *rchild; /定義左、右孩子為指 針型 bitree;有時，為了便于找到結點中的雙親，還可在結點結構中增加一個指向雙親的指針域，這種存貯結構稱為三叉鏈表。6.4 遍歷二叉樹遍歷二叉樹 （二叉樹的運算）二叉樹的運算） 所謂遍歷二叉樹，就是遵從某種次序，訪問二叉樹中的所有結點，使得每個

18、結點僅被訪問訪問一次。 這里提到的“訪問”是指對結點施行某種操作，操作可以是輸出結點信息，修改結點的數據值等，但要求這種訪問不破壞它原來的數據結構。在本書中，我們規定訪問是輸出結點信息data，且以二叉鏈表作為二叉樹的存貯結構。 遍歷對線性結構而言非常簡單，只需順序掃描每個數據元素即可。但對非線性結構，要找到一種規律，以便二叉樹上各結點能排列成一個線性序列。 二叉樹由三部分組成：根結點（D），左子樹（L），右子樹（R）。要遍歷這三個基本部分，可有六種可能的順序：DLR（先序或前序） DRL（逆先序遍歷） LDR(中序） RDL（逆中序） LRD （后序） RLD（逆后序）規定：二叉樹中必須先左

19、后右(左右順序不能顛倒)，則只有DLR、LDR、LRD三種遍歷規則。DLR稱為前根遍歷(或前序遍歷、先序遍歷、先根遍歷)，LDR稱為中根遍歷(或中序遍歷)，LRD稱為后根遍歷(或后序遍歷)。6.4.1先序遍歷先序遍歷所謂先序遍歷，就是根結點最先遍歷，其次左子樹，最后右子樹。遞歸遍歷遞歸遍歷先序遍歷二叉樹的遞歸遍歷算法描述為：若二叉樹為空，則算法結束;否則（1）輸出（訪問）根結點；）輸出（訪問）根結點；（2）再按先序遍歷方式遍歷根結點的左子樹）再按先序遍歷方式遍歷根結點的左子樹;（3）最后按先序遍歷方式遍歷根結點的右子樹）最后按先序遍歷方式遍歷根結點的右子樹;遞歸算法如下:void preord

20、er(bitree *root)if(root!=NULL) printf(“%d”,root-data); preorder(root-lchild); preorder (root-rchild); 6.4.2中序遍歷中序遍歷所謂中序遍歷，就是根在中間，先左子樹，然后根結點，最后右子樹。遞歸遍歷遞歸遍歷中序遍歷二叉樹的遞歸遍歷算法描述為：若二叉樹為空，則算法結束；否則中序遍歷左子樹中序遍歷左子樹;輸出根結點輸出根結點;中序遍歷右子樹。中序遍歷右子樹。算法如下:void inorder(biteee *root) if (root!=NULL) inorder(root-lchild); p

21、rintf(“%d”,root-data); inorder(root-rchild);6.4.3 后序遍歷后序遍歷所謂后序遍歷，就是根在最后，即先左子樹，然后右子樹，最后根結點。遞歸遍歷遞歸遍歷后序遍歷二叉樹的遞歸遍歷算法描述為：若二叉樹為空，則算法結束;否則（1）后序遍歷左子樹）后序遍歷左子樹:（2）后序遍歷右子樹）后序遍歷右子樹;（3）訪問根結點。）訪問根結點。算法如下:void postorder( bitree *root)if (root!=NULL) postorder (root-lchild); postorder (root-rchild); printf(“%d”,roo

22、t-data);例如，可以利用上面介紹的遍歷算法，寫出如下圖所示二叉樹的三種遍歷序列為： A B C D E F G H 圖 6-11 一棵二叉樹 先 序 遍 歷 序 列 ：ABDGCEFH中 序 遍 歷 序 列 ： BGDAECFH后 序 遍 歷 序 列 ： GDBEHFCA例題例題另外，在編譯原理中，有用二叉樹來表示一個算術表達式的情形。在一棵二叉樹中，若用操作數代表樹葉，用操作數代表樹葉，運算符代表非葉子結點運算符代表非葉子結點，則這樣的樹可以代表一個算術表達式。 若按前序、中序、后序對該二叉樹進行遍歷，則得到的遍歷序列分別稱為前綴表達式(或稱波蘭式)、中綴表達式、后綴表達式(逆波蘭式)

23、。具體參見圖6-12。右圖所對應的前綴表達式：-*abc。右圖所對應的中綴表達式：a*b-c。右圖所對應的后綴表達式：ab*c-。 a c b * - 圖 6-12 表達式 a*b-c 代表的二叉樹 6.4.4 遍歷二叉樹的非遞歸算法遍歷二叉樹的非遞歸算法遞歸算法遞歸算法：簡明，但效率較低，且有的程序設計語言不允許函數遞歸調用。故要討論遍歷二叉樹的非遞歸算法非遞歸算法。均用棧保存遍歷過程中經歷的結點的左右孩子（指向孩子的指針），用一維數組SM作為棧存放元素，top為棧頂指針。1、先序遍歷二叉樹的非遞歸算法利用一個一維數組作為棧，來存儲二叉鏈表中結點，算法思想為：算法思想為： 從二叉樹根結點開始

24、，先輸出輸出結點信息，沿左左子樹子樹一直走到末端(左孩子為空)為止，在走的過程中，遇到結點有右孩子的，則把指向結點右孩子的指針進棧，當左子樹為空時，從棧頂退出一個指針信息（即退出某結點的右孩子）。如此重復，直到棧為空。void preorder(bitree *root) bitree *p,*s100; int top=0; /top為棧頂指針 p=root;do while(p!=NULL) printf(“%d”,p-data); if(p-rchild!=NULL) stop+=p-rchild; p=p-lchild; if(top=0) p=s-top; while(top=0);

25、2中序遍歷二叉樹的非遞歸算法同樣利用一個一維數組作棧，來存貯二叉鏈表中結點，算法思想為：從二叉樹根結點開始，沿左子樹一直走到末端(左孩子為空)為止，在走的過程中，把依次遇到的結點進棧,待左子樹為空時,從棧中退出結點并訪問,然后再轉向它的右子樹。如此重復，直到棧空或指針為空止。算法如下:void inorder ( bitree *root) bitree *p,*s100; /s為一個棧，top為棧頂指針 int top=0; p=root;do while(p!=NULL) stop +=p;p=p-lchild; if(top=0) p=s-top; printf(“%d”,p-data)

26、; p=p-rchild; while(top=0);6.4.5 遍歷算法應用舉例遍歷算法應用舉例 例1 由二叉樹的前序序列和中序序列建立該二叉樹分析：分析： 若二叉樹的任意兩個結點的值都不相同，則二叉樹的前序序列和中序序列能唯一確定一棵二叉樹。另外，由前序序列和中序序列的定義可知，前序序列中第一個結點必為根結點，而在中序序列中，根結點剛好是左、右子樹的分界點，因此，可按如下方法建立二叉樹：1.用前序序列的第一個結點作為根結點;2.在中序序列中查找根結點的位置，并以此為界將中序序列劃分為左、右兩個序列(左、右子樹);3.根據左、右子樹的中序序列中的結點個數，將前序序列去掉根結點后的序列劃分為左

27、、右兩個序列，它們分別是左、右子樹的前序序列;4.對左、右子樹的前序序列和中序序列遞歸地實施同樣方法，直到所得左、右子樹為空。假設前序序列為ABDGHCEFI， 中序序列為GDHBAECIF， 則得到的二叉樹如下頁所示1。A為根結點A BDGH CEFI GDHB A ECIF BDGHCEFIA2. B為左子樹的根結點B DGHGDH BCEFIDHGBA3. D為左子樹的左子樹的根結點 A B G H D C E F I A B G H D C FI E 4。C為右子樹的根結點 A B G H D C F I E 5。F為右子樹的右子樹的根結點C E FIE C IF思考：能否根據中序、后

28、序求前序？能否根據前序、后序求中序？例2 按層次遍歷一棵二叉樹對于一棵二叉樹，若規定遍歷順序為從上到下(上層遍歷完才進入下層)，從左到右(同一層從左到右進行，這樣的遍歷稱為按層次遍歷：例1的樹的層次遍歷序列為：ABCDEFGHI。下面用一個一維數組來模擬隊列，實現二叉樹的層次遍歷。Void lorder (bitree * t) bitree *qmaxsize,*p; / maxsize為最大容量 int f,r; / f,r類似于頭尾指針q0=t; f=r=0; while (fdata); if(p -lchild!=NULL) r+; qr=p-1child; /入隊 if (p-rc

29、hild!=NULL) r+; qr=p-rchild; /入隊 作業：作業：1、一棵度為2的樹與一棵二叉樹有何區別？2、用一維數組存放的一棵完全二叉樹：ABCDEFGHIJKL，寫出該二叉樹的前序、中序、后序遍歷序列。3、假設一棵二叉樹的前序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK，請寫出二叉樹的后序遍歷序列。4、假設一棵二叉樹的中序序列為DCBGEAHFIJK和后序序列為DCEGBFHKJIA。請寫出二叉樹前序遍歷序列。12311458912136710141512345671231145891267101234566.5 二叉排序樹二叉排序樹(二叉搜索樹，二叉查找樹

30、）二叉搜索樹，二叉查找樹）1什么是二叉排序樹什么是二叉排序樹二叉排序樹（Binary Sorting Tree），它或者是一棵空樹，或者是一棵具有如下特征的非空二叉樹：(1)若它的左子樹非空，則左子樹上所有結點的關鍵字均小于根結點的關鍵字；(2)若它的右子樹非空，則右子樹上所有結點的關鍵字均大于等于根結點的關鍵字； (3)左、右子樹本身又都是一棵二叉排序樹。下圖各例是否為二叉排序樹？（為了討論問題的方便，假設樹中每個結點的值是一個十進制整數）2、下面給出構造二叉排序樹的算法、下面給出構造二叉排序樹的算法：將一個給定的數據元素構造為相應的二叉排序樹，通常采用逐步插入結點逐步插入結點的方法來構造二

31、叉排序樹。設k=k1,k2,.,kn為數據元素序列，從k1開始依次取序列中的元素，每取出一個元素ki,按下列原則建立二叉排序樹的一個新結點：（1）若二叉排序樹為空，則新的數據元素就是二叉排序樹的根結點。（2）若二叉排序樹非空，則將新的數據元素與該二叉樹的根結點的值進行比較，若小于根結點的值，則將新的數據元素插入到根結點的左子樹中；否則，插入到右子樹中。這個過程是一個遞歸的過程遞歸的過程，因為數據元素插入到左子樹或右子樹也同樣是按這個原則遞歸進行的。（例）例如，結定關鍵字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序樹過程如下圖所示。 79 62 79 68 62

32、 79 68 62 79 90 88 68 62 79 90 (a) (b) (c) (d) (e) 88 68 62 79 90 89 89 17 88 68 62 79 90 17 5 88 68 62 79 90 89 (f) (g) (h) 89 17 5 88 68 62 79 90 100 89 17 5 88 68 62 79 90 100 120 圖 7-6 二叉排序樹的生成過程 (i) (j) （注：排列順序不一樣，得到的二叉排序樹也不一樣）二叉排序樹與關鍵字排列順序有關嗎?a、遞歸算法bitree *Inserttree(bitree *t, int x) if(t=NUL

33、L) t=( bitree *)malloc(sizeof(bitree); t-data=x; t-lchild=NULL; t-rchild=NULL; else若二叉排序樹為空，則新的數據元素就是二叉排序樹的根結點。 if(xdata) t-lchild=Inserttree(t-lchild,x); else t-rchild=Inserttree(t-rchild,x); return(t);b、生成二叉排序樹的非遞歸算法： bitree *creat(bitree *t) bitree *s,*p,*q; int x;若二叉排序樹非空，則將新的數據元素與該二叉樹的根結點的值進行比較

34、，若小于根結點的值，則將新的數據元素插入到根結點的左子樹中；否則，插入到右子樹中。scanf(“%d”,&x);while(x!=0)s= ( bitree *)malloc(sizeof(bitree);s-data=x;s-lchild=s-rchild=NULL;if(t=NULL) t=s;else p=t; while(p) q=p; if(s-datadata) p=p-lchild; else p=p-rchild; if(s-datadata) q-lchild=s;else q-rchild=s; /插入結點算法scanf(“%d”,&x); /while循環結束return

35、(t);3、二叉排序、二叉排序 樹上的查找樹上的查找(檢索算法）檢索算法） （1）二叉排序）二叉排序 樹的查找思想樹的查找思想若二叉排樹為空，則查找 失敗，否則，先拿根結點值與待查值進行比較，若相等，則查找成功，若根結點值大于待查值，則進入左子樹重復此步驟，否則，進入右子樹重復此步驟，若在查找過程中遇到二叉排序樹的葉子結點時，還沒有找到待找結點，則查找不成功。（2）二叉排序樹查找的算法實現）二叉排序樹查找的算法實現a、遞歸算法： bitree *bstsrch(bitree *t,int k) if(t=NULL)|(t-data=k) return(t); else if(t-data rc

36、hild,k); else return(bstsrch(t-lchild,k); b、非遞歸算法bitree *search(bitree *t,int k) while(t!=NULL) if(t-data=k) return(t); else if(t-datarchild; else t=t-lchild; return(NULL);4、刪除運算、刪除運算在二叉排序樹上刪除一個結點需注意：要保證刪除后所得的二叉樹仍是一棵二叉檢索樹。考慮下面三種情況：1）若要刪除的是葉子結點若要刪除的是葉子結點 最簡單的一種，只要將其雙親結點與它之間的鏈接的指針置空即可。如圖 2）若要刪除的結點只有左子

37、樹或只有右子樹，即單支若要刪除的結點只有左子樹或只有右子樹，即單支結點。結點。a、若被刪除的結點沒有左子樹，則可用其右子樹的根結點取代被刪除結點的位置。b、若被刪除結點沒有右子樹，則可用其左子樹的根結點取代被刪除結點的位置。3）若刪除的結點具有左、右子樹。若刪除的結點具有左、右子樹。方法：首先將該結點的中序前趨結點的值賦給該結點的值，然后再刪除它的中序前趨結點。由于此時，它的中序前趨結點的右指針為空，只要將中序前趨結點的左指針鏈接到中序前趨結點所在的鏈接位置即可。5二叉排序樹查找的性能分析二叉排序樹查找的性能分析 在二叉排序樹查找中，成功的查找次數不會超過二叉樹的深度，而具有n個結點的二叉排序

38、樹的深度，最好為log2（n+1） ，最壞為n。因此，二叉排序樹查找的最好時間復雜度為O(log2n)，最壞的時間復雜度為O(n)，一般情形下，其時間復雜度大致可看成O(log2n)，比順序查找效率要好，但比二分查找要差。 即使關鍵字相同的一組數據，若先后插入的次序不同插入的次序不同，所生成的二叉排序樹也不同生成的二叉排序樹也不同，則查找的時間性能也不同，當要求查找的性能較高時，要對構成二叉排序樹的過程進行“平衡化”處理，形成二叉平衡樹。 6.6 平衡二叉樹平衡二叉樹1平衡二叉樹的概念平衡二叉樹的概念平衡二叉樹(balanced binary tree)是由阿德爾森一維爾斯和蘭迪斯(Adels

39、on-Velskii and Landis)于1962年首先提出的，所以又稱為AVL樹。平衡二叉樹平衡二叉樹: 若一棵二叉樹中每個結點的左、右子樹的深度之差的絕對值不超過1，則稱這樣的二叉樹為平衡二叉樹。平衡因子：平衡因子：將該結點的左子樹深度減去右子樹深度的值，稱為該結點的平衡因子(balance factor)。也就是說，一棵二叉排序樹中，所有結點的平衡因子只能為0、1、-1時，則該二叉排序樹就是一棵平衡二叉樹， 5 2 3 4 16 7 圖 7-8 一棵平衡二叉樹 6 1 2 3 4 8 5 7 圖 7-9 一棵非平衡二叉樹 2. 非平衡二叉樹的平衡處理非平衡二叉樹的平衡處理 若一棵二叉

40、排序樹是平衡二叉樹，扦入某個結點后，可能會變成非平衡二叉樹，這時，就可以對該二叉樹進行平衡處理，使其變成一棵平衡二叉樹。處理的原則處理的原則應該是處理與扦入點最近的最近的、而平衡因子又比1大或比-1小的結點。下面將分四種情況討論平衡處理。 （1）LL型型 的處理的處理(左左型左左型)如圖7-10所示，在C的左孩子B上扦入一個左孩子結點A，使C的平衡因子由1變成了2，成為不平衡的二叉樹序樹。這時的平衡處理為：將C順時針旋轉，成為B的右子樹，而原來B的右子樹則變成C的左子樹，待扦入結點A作為B的左子樹。(注：圖中結點旁邊的數字表示該 結點的平衡因子) 平衡外理 a 1 A B C 0 2 C B

41、A 0 0 0 圖 7-10 LL 型平衡外理 （2）LR型的處理型的處理(左右型左右型)如圖7-11所示，在C的左孩子A上扦入一個右孩子B，使的C的平衡因子由1變成了2，成為不平衡的二叉排序樹。這是的平衡處理為：將B變到A與C 之間，使之成為LL型，然后按第(1)種情形LL型處理。 0 -1 C A B 2 0 1 C A B 2 B 0 0 C A 0 平衡處理 旋轉 圖 7-11 LR 型平衡處理 （3）RR型的處理型的處理(右右型右右型)如圖7-12所示，在A的右孩子B上扦入一個右孩子C，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹。這時的平衡處理為：將A逆時針旋轉，成為B的左

42、子樹，而原來B的左子樹則變成A的右子樹，待扦入結點C成為B的右子樹。 平衡處理 a -1 C B A 0 -2 C B A 0 0 0 圖 7-12 RR 型平衡處理 （4）RL型的處理型的處理(右左型右左型)如圖7-13所示，在A的右孩子C上扦入一個左孩子B，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹。這時的平衡處理為：將B變到A與C之間，使之成為RR型，然后按第(3) 種情形RR型處理。 平衡處理 a C B A 0 0 0 圖 7-13 RL 型平衡處理 -1 -2 C B A B 0 1 -2 A 旋轉 C 例1，給定一個關鍵字序列4,5,7,2,1,3,6，試生成一棵平衡二

43、叉樹。分析：平衡二叉樹實際上也是一棵二叉排序樹，故可以按建立二叉排序樹的思想建立，在建立的過程中，若遇到不平衡，則進行相應平衡處理，最后就可以建成一棵平衡二叉樹。具體生成過程見圖7-14。 (a)插入 4 (b)插入 5 (c)插入 7 RR 型 4 0 4 5 0 -1 7 4 5 -2 -1 0 0 0 4 5 7 0 LL 型 (d)插入 2 (e)插入 1 4 2 5 7 1 0 0 0 0 0 4 2 5 7 1 0 0 1 2 2 4 2 5 7 0 0 1 1 -1 5 2 1 4 3 7 2 0 1 0 0 5 2 1 4 3 7 -1 0 0 0 0 0 LR 型 (f)插入

44、 3 5 2 1 4 3 7 -2 -1 0 1 0 0 6 0 RL 型 0 6 2 1 4 3 7 0 0 0 0 0 5 0 (g) 插入 6 圖 7-14 平衡二叉樹的生成過程 例2：給定一個關鍵字序列13，24，37，90，53，試生成一棵平衡二叉樹。作業作業：將一組關鍵字（47,16,21,36,29,59,19,54)生成一二叉平衡樹。 3平衡二叉樹的查找及性能分析平衡二叉樹的查找及性能分析平衡二叉樹本身就是一棵二叉排序樹，故它的查找與二叉排序樹完全相同。但它的查找 性能優于二叉排序樹，不像二叉排序樹一樣，會出現最壞的時間復雜度O(n)，它的時間復雜度與二叉排序樹的最好時間復雜相

45、同，都為O(log2n)。一般二叉平衡樹主要應用于查找。例3，對例1給定的關鍵字序列4,5,7,2,1,3,6，試用二叉排序樹和平衡二叉樹兩種方法查找，給出查找6的次數及成功的平均查找長度。分析：由于關鍵字序列的順序己經確定，故得到的二叉排序樹和平衡二叉樹都是唯一的。得到的平衡二叉樹見圖7-14，得到的二叉排序樹見圖7-15。 4 2 3 1 5 7 6 圖 7-15 由 關 鍵 字 序 列 4,5,7,2,1 ,3,6 生 成 的二 叉 排 序 樹 從圖7-15的二叉排序樹可知，查找6需4次，假設7個記錄的查找概率相等，為1/7，則該二叉排序樹的平均查找長度為 ASL=(1+2+2+3+3+

46、3+4)/7=18/72.57。從圖7-16的平衡二叉樹可知，查找6需2次，平均查找長度ASL=(1+2+2+3+3+3+3)/7=17/72.43。從結果可知，平衡二叉樹的查找性能優于二叉排序樹。 0 6 2 1 4 3 7 0 0 0 0 0 5 0 圖 7-16 平衡二叉樹 #includeh1.h#include#includebitree *creat(bitree *t) bitree *s,*p,*q; int x; printf(input the nodes value:0-ENDn); scanf(%d,&x); while(x!=0) s=(bitree *)malloc

47、(sizeof(bitree); s-data=x; s-lchild=s-rchild=NULL; if(t=NULL) t=s; else p=t; while(p) q=p; if(s-datadata) p=p-lchild; else p=p-rchild; if(s-datadata) q-lchild=s; else q-rchild=s; printf(input the nodes value:n); scanf(%d,&x); return(t); void preorder(bitree *root) if(root!=NULL) printf(%dn,root-data

48、); preorder(root-lchild); preorder (root-rchild);void main() bitree *p=NULL,*q; q=creat(p); printf(now output the trees preorder value:n); preorder(q);湖南大學01-03 1、樹最合適用來表示_。A 有序數據元素 B 無序數據元素 C 元素之間無聯系的數據 D元素之間分支層次關系的數據2、中序遍歷二叉排序樹就可以得到排好序的結點序列。（ ）（判斷正誤） 一維數組存放一棵完全二叉樹:ABCDEFGHIJK，請給出該二叉樹的后序遍歷序列。算法設計題略

49、1、在二叉排序樹上成功地找到一個結點，在平均情況下的時間復雜性是 , 在最壞情況下的時間復雜性是 。設結點個數為 n，以大O形式給出時間復雜性。2、已知一棵二叉樹是以二叉鏈表的形式存儲的，其結點結構說明如下：（本題10 分。） struct node int data; / 結點的數據場。 struct node *left; / 給出結點的左兒子的地址。 struct node * right; / 給出結點的右兒子的地址。 ； 請在1、2二題的 處進行填空，完成題目要求的功能。注意，每空只能填一個語句，多填為 0 分。(1) 求出以T 為根的二叉樹或子樹的結點個數。 int size (s

50、truct node * T ) if ( ) return 0; else ; ( 2) 求出以T為根的二叉樹或子樹的高度。注：高度定義為樹的總的層次數。 int height(struct node * T ) if ( T = NULL ) ; else ; 上海交通大學上海交通大學2004年數據結構考研試題年數據結構考研試題 提示：用遞歸形式O(log2n) O(n) T = NULLreturn ( 1 +size(T-left) + size(T-right) )return 0return 1 +( ( height(T-left) height(T-right)? height

51、(T-left): height(T-right) )6.7線索二叉樹線索二叉樹6.7.1 線索的概念 遍歷二叉樹：遍歷二叉樹：就是將樹中所有結點排成一個線性序列。好處：好處：在這樣的線性序列中，很容易求得某個結點在某種遍歷下的直接前驅和后繼。 帶來麻煩，希望不進行遍歷就能快速找到快速找到某個結點在某種遍歷下的直接前驅和后繼，這樣，就應該把每個結點的直接前驅和直接后繼記錄下來。 為了做到這一點，可以在原來的二叉鏈表結點中，再增加兩個指針域，一個指向前驅，一個指向后繼，但這樣做將會浪費大量存貯單元，存貯空間的利用率相當低(一個結點中有4個指針，1個指左孩子，1個指右孩子，1個指前驅，1個指后繼)

52、，而原來的左、右孩子域有許多空指針又沒有利用起來。為了不浪費存貯空間，我們利用原有的孩子指針為空時來存放直接前驅和后繼，這樣的指針稱為“線索”（thread)，加線索的過程稱為線索化線索化，加了線索的二叉樹，稱為線索二叉樹線索二叉樹，對應的二叉鏈表稱為線索二叉鏈表線索二叉鏈表（簡稱為線索鏈表）。 在線索二叉樹中，由于有了線索，無需遍歷二叉樹就可以得到任一結點在某種遍歷下的直接前驅和后繼。 但是，我們怎樣來區分孩子指針域中存放的是左、右孩子信息還是直接前驅或直接后繼信息呢?為此，在二叉鏈表結點中，還必須增加兩個標志域ltag、rtag。 ltag和rtag定義如下： 0 lchild域指向結點的

53、左孩子 ltag= 1 lchild域指向結點在某種遍歷下的直 接前驅 0 rchild域指向結點的右孩子 rtag= 1 rchild域指向結點在某種遍歷下的直接后繼 這樣，二叉鏈表中每個結點還是有5個域，但其中只有2個指針，較原來的4個指針要方便。增加線索后的二叉鏈表結點結構可描述如下： lchild ltag data rtag rchild 2線索的分類線索的分類另外，根據遍歷的不同要求，線索二叉樹可以分為：（1）前序前驅線索二叉樹）前序前驅線索二叉樹(只需畫出前驅只需畫出前驅)（2）前序后繼線索二叉樹）前序后繼線索二叉樹(只需畫出后繼只需畫出后繼)（3）前序線索二叉樹）前序線索二叉樹

54、(前驅和后繼都要標出前驅和后繼都要標出)（4）中序前驅線索二叉樹）中序前驅線索二叉樹(只需畫出前驅只需畫出前驅)（5）中序后繼線索二叉樹）中序后繼線索二叉樹(只需畫出中序后繼只需畫出中序后繼)（6）中序線索二叉樹）中序線索二叉樹(中序前驅和后繼都要標出中序前驅和后繼都要標出)（8）后序前驅線索二叉樹）后序前驅線索二叉樹(只需畫出后序前驅只需畫出后序前驅)（8）后序后繼線索二叉樹）后序后繼線索二叉樹(中需畫出后序后驅中需畫出后序后驅)（9）后序線索二叉樹）后序線索二叉樹(前驅和后繼都要標出前驅和后繼都要標出) 6.7.2線索的描述線索的描述1結點數據類型描述結點數據類型描述typedef str

55、uct bithrnode int data; int ltag ,rtag; /左、右標志域 struct bithrnode *lchild, *rchild; binode ; 2線索的畫法線索的畫法在二叉樹或二叉鏈表中，若左孩子為空，則畫出它的直接前驅，右孩子為空時，則畫出它的直接后繼，左右孩子不為空時，不需畫前驅和后繼。這樣就得到了線索二叉樹或線索二叉鏈表。前序序列為：ABCD A D C B 0 A 0 1 B 1 0 C 1 root 1 D 1 A D C B NULL (a) 二叉樹 (b)前序線索二叉樹 (c)前序線索二叉鏈表 圖 7-17 前序線索示意圖 A D C B

56、NULL NULL （a）中序線索二叉樹 （b） 中序線索二叉鏈表 圖 7-18 中序線索示意圖 0 A 0 root 1 D 1 0 C 1 1 B 1 中序序列為：BADC C 0 A 0 1 B 1 0 C 1 1 D 1 root D B A NULL (a)后序線索二叉樹 (b)后序線索二叉鏈表 圖 7-19 后序線索示意圖 后序序列為：BDCA仿線性表的存儲結構，在二叉樹的線索鏈表上添加一個頭結點，其中lchild指向根結點，rchild指向自己，并且原先指向空的線索均指向該頭結點。如此處理，使得在線索二叉樹中查找某結點的前趨、后繼結點的算法中不必再判斷線索是否為空的情況。6.8

57、樹和森林樹和森林 6.8.1 樹、森林和二叉樹的轉換樹、森林和二叉樹的轉換1樹轉換成二叉樹樹轉換成二叉樹可以分為三步：（1） 連線指相鄰兄弟之間連線，加一虛線。 （2） 抹線指抹掉雙親與除最左孩子外其它孩子之間的連線。 （3） 旋轉只需將樹作適當的旋轉，具體：將圖形上原有的實線均向左斜，加上的虛線均向右斜，且變成實線，調整成二叉樹的樹型結構。 具體實現過程見圖7-20。 G F E D C B A A B E C D G F F G D C E B A 圖 7-20 樹轉換成二叉樹示意圖 連線抹線 旋轉 由轉換可知：在二叉樹中，左分支上的各結點在原來的樹中是父子關系，而右分支上的各結點在原來的

58、樹中是兄弟關系。由于根結點沒有兄弟，所以變換后的二叉樹的根結點的右孩子必為空2森林轉換成二叉樹森林轉換成二叉樹（1） 將森林中每一棵樹分別轉換成二叉樹將森林中每一棵樹分別轉換成二叉樹這在剛才的樹轉換成二叉樹中已經介紹過。這在剛才的樹轉換成二叉樹中已經介紹過。 （2）合并）合并使第n棵樹接入到第n-1棵的右邊并成為它的右子樹，第 n-1 棵二叉樹接入到第n-2 棵的右邊并成為它的右子樹，第2棵二叉樹接入到第1棵的右邊并成為它的右子樹，直到最后剩下一棵二叉樹為止。 C D B A F E I A A A H G E F I H G G F E D C B A I H A D B C 圖 7-21

59、森 林 轉 換 成 二 叉 樹 示 意 圖 合 并 3二叉樹還原成樹二叉樹還原成樹與樹轉換成二叉樹的步驟剛好相反：a. 加線：若某節點I是雙親節點的左孩子，則將該節點的右孩子及沿著此右孩子的右鏈不斷搜索到的所有右孩子，都分別與節點I的雙親節點用虛線連接起來。b. 抹線：抹掉原二叉樹中所有雙親節點與右孩子的連線。c. 旋轉：將樹中虛線均變為實線，并按層次排好。ABECDFABCDEF調整后ABCDEF4. 二叉樹還原成森林二叉樹還原成森林(1) 右鏈斷開（即抹線）將二叉樹的根結點的右鏈及右鏈的右鏈等全部斷開，得到若干棵無右子樹的二叉樹。具體操作見圖7-21(b)。（2） 二叉樹還原成樹 具體操作

60、步驟見圖7-21(c)。 G D A B C E F H I J K (a)一個森林得到的二叉樹 D A B C E G F H I J K (b)斷開根的右鏈得到 4 棵無右子樹的二叉樹 C G F H I J K D A B E (c) 四棵二叉樹還原成四棵樹 H I J K G F C D A B E (d) 二叉樹還原成森林 圖 7-21 二叉樹還原成森林過程 6.8.2 樹和森林的遍歷樹和森林的遍歷 在樹和森林中，一個結點可能有兩棵以上的子樹，因而不便討論它們的中序遍歷。故樹和森林的遍歷通常有兩種方式，先序遍歷和后序遍歷。下面分別討論：（1）樹的先序遍歷）樹的先序遍歷若樹非空，則先訪