大學(xué)數(shù)據(jù)結(jié)構(gòu)課件6.樹和二叉樹

1、前面講的線性表主要表現(xiàn)的是數(shù)據(jù)元素之間的前前面講的線性表主要表現(xiàn)的是數(shù)據(jù)元素之間的前后次序關(guān)系，是一種線性結(jié)構(gòu)。后次序關(guān)系，是一種線性結(jié)構(gòu)。樹型結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)構(gòu)。樹形結(jié)樹型結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)構(gòu)。樹形結(jié)構(gòu)在客觀世界中廣泛存在，如人類的家庭族譜及各種構(gòu)在客觀世界中廣泛存在，如人類的家庭族譜及各種社會組織機(jī)構(gòu)。又如計算機(jī)文件管理和信息組織也用社會組織機(jī)構(gòu)。又如計算機(jī)文件管理和信息組織也用到樹形結(jié)構(gòu)。本章討論樹的基本概念，重點(diǎn)討論二叉到樹形結(jié)構(gòu)。本章討論樹的基本概念，重點(diǎn)討論二叉樹的有關(guān)概念、性質(zhì)、存儲結(jié)構(gòu)和各種運(yùn)算。樹的有關(guān)概念、性質(zhì)、存儲結(jié)構(gòu)和各種運(yùn)算。樹樹(tree)是由

2、是由n(n0)個結(jié)點(diǎn)組成的有限集合個結(jié)點(diǎn)組成的有限集合t。n=0的的樹稱為空樹；對樹稱為空樹；對n0的樹，有的樹，有:(1)僅有僅有一個特殊的結(jié)點(diǎn)稱為根一個特殊的結(jié)點(diǎn)稱為根(root)結(jié)點(diǎn)結(jié)點(diǎn)，根結(jié)點(diǎn)沒，根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)；有前驅(qū)結(jié)點(diǎn)；(2)當(dāng)當(dāng)n1時，除根結(jié)點(diǎn)外其余的結(jié)點(diǎn)分為時，除根結(jié)點(diǎn)外其余的結(jié)點(diǎn)分為m(m0)個個互互不相交不相交的有限集合的有限集合t1,t2，tm，其中每個集合，其中每個集合ti本身又本身又是一棵樹，稱之為根的子樹（是一棵樹，稱之為根的子樹（ subtree）。）。注：注：樹的定義具有樹的定義具有遞歸性遞歸性，即，即“樹中還有樹樹中還有樹”。 僅有一個根結(jié)點(diǎn)的樹是最小樹，

3、僅有一個根結(jié)點(diǎn)的樹是最小樹，分支結(jié)點(diǎn)：分支結(jié)點(diǎn)：度不為度不為0 0的結(jié)點(diǎn)，除葉結(jié)點(diǎn)之外的其余結(jié)點(diǎn)。的結(jié)點(diǎn)，除葉結(jié)點(diǎn)之外的其余結(jié)點(diǎn)。abcgeidhfjmlk結(jié)點(diǎn)（結(jié)點(diǎn)（nodenode）：）：由數(shù)據(jù)元素由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關(guān)系的和構(gòu)造數(shù)據(jù)元素之間關(guān)系的指針組成指針組成結(jié)點(diǎn)的度：結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有結(jié)點(diǎn)所擁有的子樹的個數(shù)的子樹的個數(shù)樹的度：樹的度：樹中所有結(jié)點(diǎn)的度的最大值樹中所有結(jié)點(diǎn)的度的最大值葉結(jié)點(diǎn)：葉結(jié)點(diǎn)：度為度為0 0的結(jié)點(diǎn)，也稱作的結(jié)點(diǎn)，也稱作終端結(jié)點(diǎn)終端結(jié)點(diǎn)結(jié)點(diǎn)的層次：結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)到樹中某結(jié)點(diǎn)所經(jīng)路徑上的分支數(shù)從根結(jié)點(diǎn)到樹中某結(jié)點(diǎn)所經(jīng)路徑上的分支數(shù)樹的深度：樹的深度：樹

4、中所有結(jié)點(diǎn)的層次的最大值樹中所有結(jié)點(diǎn)的層次的最大值 森林：森林：m m（m m00）棵樹的集合）棵樹的集合 孩子孩子(child)(child)結(jié)點(diǎn)結(jié)點(diǎn)：樹中一個結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)樹中一個結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)雙親雙親(parent)(parent)結(jié)點(diǎn)：結(jié)點(diǎn)：若樹中某結(jié)點(diǎn)有孩子結(jié)點(diǎn)，則這個若樹中某結(jié)點(diǎn)有孩子結(jié)點(diǎn)，則這個結(jié)點(diǎn)就稱作它的孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)結(jié)點(diǎn)就稱作它的孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn) 兄弟兄弟(sibling)(sibling)結(jié)點(diǎn)：結(jié)點(diǎn)：具有相同的雙親結(jié)點(diǎn)的結(jié)點(diǎn)具有相同的雙親結(jié)點(diǎn)的結(jié)點(diǎn) abcgeidhfjmlk無序樹：無序樹：樹中任意一個結(jié)點(diǎn)的各孩子結(jié)點(diǎn)之間的樹中任意一個結(jié)點(diǎn)的各孩子結(jié)點(diǎn)之間的

5、次序構(gòu)成次序構(gòu)成 無關(guān)緊要無關(guān)緊要的樹的樹有序樹：有序樹：樹中任意一個結(jié)點(diǎn)的各孩子結(jié)點(diǎn)有嚴(yán)格排列次序的樹樹中任意一個結(jié)點(diǎn)的各孩子結(jié)點(diǎn)有嚴(yán)格排列次序的樹beflkbfelk(1)(1)倒懸樹法倒懸樹法( (直觀表示直觀表示) ) (2)(2)集合包含關(guān)系圖法集合包含關(guān)系圖法 (3)(3)凹入表示法凹入表示法 abcgeidhfjmlk feklcgbi ij jmdhabcdefghijklm數(shù)據(jù)集合數(shù)據(jù)集合: 樹的結(jié)點(diǎn)集合，每個結(jié)點(diǎn)由數(shù)據(jù)元素和構(gòu)造數(shù)樹的結(jié)點(diǎn)集合，每個結(jié)點(diǎn)由數(shù)據(jù)元素和構(gòu)造數(shù) 據(jù)元素之間關(guān)系的指針組成。據(jù)元素之間關(guān)系的指針組成。操作集合操作集合: （1 1）創(chuàng)建）創(chuàng)建maketr

6、eemaketree(t) (t) （2 2）撤消）撤消destroytreedestroytree(t)(t)（3 3）雙親結(jié)點(diǎn)）雙親結(jié)點(diǎn)parent(t, currparent(t, curr) ) （4 4）左孩子結(jié)點(diǎn)）左孩子結(jié)點(diǎn)leftchild(t, currleftchild(t, curr) ) （5 5）右兄弟結(jié)點(diǎn)）右兄弟結(jié)點(diǎn)rightsibling(t, currrightsibling(t, curr) ) （6 6）遍歷樹）遍歷樹traverse(t, visit()traverse(t, visit() 樹的結(jié)點(diǎn)之間的邏輯關(guān)系主要有雙親樹的結(jié)點(diǎn)之間的邏輯關(guān)系主要有雙親-

7、 -孩子孩子關(guān)系，兄弟關(guān)系。因此，從結(jié)點(diǎn)之間的邏輯關(guān)系關(guān)系，兄弟關(guān)系。因此，從結(jié)點(diǎn)之間的邏輯關(guān)系分，樹的存儲結(jié)構(gòu)主要有：分，樹的存儲結(jié)構(gòu)主要有：雙親表示法、孩子表雙親表示法、孩子表示法、雙親孩子表示法和孩子兄弟表示法示法、雙親孩子表示法和孩子兄弟表示法四種組四種組合。合。 指針有指針有常規(guī)指針常規(guī)指針和和仿真指針仿真指針4h2g1f1e1d0c0b-1ai4data parentdata parent0 01 12 23 34 45 56 67 78 8(1)(1)雙親表示法雙親表示法(a)一棵樹一棵樹（b)仿真指針的雙親表示法存儲結(jié)構(gòu)仿真指針的雙親表示法存儲結(jié)構(gòu)樹及其使用仿真指針的雙親表示法

8、樹及其使用仿真指針的雙親表示法abcfgeihd(2)(2)孩子表示法孩子表示法常規(guī)指針的孩子表示法常規(guī)指針的孩子表示法bcrootad ef gih abcfgeihd雙親孩子表示法雙親孩子表示法(3)(3)雙親孩子表示法雙親孩子表示法4h2g1f1e1d0c0b-1ai4data parent headdata parent head012345678child nextchild next87123456abcfgeihd(4)(4)孩子兄弟表示法孩子兄弟表示法常規(guī)指針的孩子兄弟表示法常規(guī)指針的孩子兄弟表示法rootbcdefghiaabcfgeihd二叉樹二叉樹(binary tree

9、)：是是n(n0)個結(jié)點(diǎn)的有限集合。個結(jié)點(diǎn)的有限集合。n=0的樹稱為空二叉樹；的樹稱為空二叉樹；n0的二叉樹由一個根結(jié)點(diǎn)以的二叉樹由一個根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為及兩棵互不相交的、分別稱為左子樹和右子樹左子樹和右子樹的的二叉樹組成二叉樹組成 。其。其邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)： 一對二（一對二（1:2）左、右子樹也是二叉樹，所以子樹也可以為空樹。下圖左、右子樹也是二叉樹，所以子樹也可以為空樹。下圖展現(xiàn)了五種不同形態(tài)的二叉樹。展現(xiàn)了五種不同形態(tài)的二叉樹。n=0n=0n=1n=1n1n1n1n1n1n1基本特征基本特征: 每個結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于每個結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于

10、2的結(jié)點(diǎn)）；的結(jié)點(diǎn)）； 左子樹和右子樹左子樹和右子樹次序不能顛倒次序不能顛倒。所以下面是兩棵不同的樹。所以下面是兩棵不同的樹bacedfgbacedfg滿二叉樹：滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣子樹和右子樹，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣的二叉樹稱為滿二叉樹。的二叉樹稱為滿二叉樹。bacedfghijklmno完全二叉樹：完全二叉樹：如果一棵深度為如果一棵深度為k k，有，有n n個結(jié)點(diǎn)的二叉樹中各個結(jié)點(diǎn)的二叉樹中各 結(jié)點(diǎn)能夠與深度為結(jié)點(diǎn)能夠與深度為k k的順序編號的滿二叉樹從的順序編

11、號的滿二叉樹從1 1到到n n標(biāo)號的標(biāo)號的 結(jié)點(diǎn)相對應(yīng)的二叉樹稱為完全二叉樹。如下圖所示結(jié)點(diǎn)相對應(yīng)的二叉樹稱為完全二叉樹。如下圖所示bacedfghijbacedfghijklmno(a)滿二叉樹滿二叉樹 (b)完全二叉樹完全二叉樹 數(shù)據(jù)集合：數(shù)據(jù)集合：二叉樹的結(jié)點(diǎn)集合，每個結(jié)點(diǎn)由數(shù)據(jù)元素和構(gòu)造數(shù)二叉樹的結(jié)點(diǎn)集合，每個結(jié)點(diǎn)由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關(guān)系的指針組成。據(jù)元素之間關(guān)系的指針組成。操作集合：操作集合：（1 1）創(chuàng)建）創(chuàng)建maketreemaketree(t) (t) （2 2）撤消）撤消destroytreedestroytree(t)(t)（3 3）左插入結(jié)點(diǎn)）左插入結(jié)點(diǎn)inser

12、tleftnode(currinsertleftnode(curr, x) , x) （4 4）右插入結(jié)點(diǎn)）右插入結(jié)點(diǎn)insertrightnode(currinsertrightnode(curr, x) , x) （5 5）左刪除子樹）左刪除子樹deletelefttree(currdeletelefttree(curr) ) （6 6）右刪除子樹）右刪除子樹deleterighttree(currdeleterighttree(curr) ) （7 7）遍歷二叉樹）遍歷二叉樹traverse(t, visit()traverse(t, visit()k=ik=i2 2i -1-1性質(zhì)性質(zhì)

13、1 1:i=1i=1 2 21-11-1=2=20 0=1=1i=2i=22 22-12-1=2=21 1=2=2i=3i=32 23-13-1=2=22 2=4=4bacedfghijklmnoi=4i=42 24-14-1=2=23 3=8=8k=ik=i性質(zhì)性質(zhì)2:2: k k3 2 13 2 1 0 0 0 00 0 0 0 1 1 2 20 0 0 0 0 00 0 1 1 0 2 0 21 1 0 0 0 01 1 0 0 2 0 0 22 2 + + 0 0 1 10 0 0 20 0 0 2k-1k-1 0 1 0 11 1 1 21 1 1 2k k-1-1 =2=21 1=

14、2=22 2=2=23 3=2=2k-1k-1=2=2k k=2=20 01 01 00 0 00 0 0+ + 1 1k kbacedfghijklm nok=ik=i2 2i -1-1qqasnn1)1 (1n=kn=ka a1 1=1=1q=2q=2性質(zhì)性質(zhì)3 3 對于一棵非空的二叉樹，如果葉結(jié)點(diǎn)個數(shù)為對于一棵非空的二叉樹，如果葉結(jié)點(diǎn)個數(shù)為n n0 0，度為度為2 2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n n2 2，則有，則有n n0 0= n= n2 2+1+1。bacedfghijn0 = n2+1。證明：設(shè)證明：設(shè)n n為二叉樹的結(jié)點(diǎn)總數(shù)，為二叉樹的結(jié)點(diǎn)總數(shù)，n n1 1為二叉樹為二叉樹中度為中度

15、為1 1的結(jié)點(diǎn)個數(shù)，則有：的結(jié)點(diǎn)個數(shù)，則有：n = nn = n0 0 + n + n1 1 + n + n2 2 (1)(1)由于二叉樹中除根結(jié)點(diǎn)外，由于二叉樹中除根結(jié)點(diǎn)外，每個結(jié)點(diǎn)都有一條與其父每個結(jié)點(diǎn)都有一條與其父結(jié)點(diǎn)相連的邊。所以，有結(jié)點(diǎn)相連的邊。所以，有n n個結(jié)點(diǎn)的二叉樹總共有個結(jié)點(diǎn)的二叉樹總共有 n-1n-1條邊。于是有：條邊。于是有：n-1=0n-1=0n n0 0 + 1 + 1n n1 1 + 2 + 2n n2 2 (2)(2)再把再把(1)(1)代入代入(2)(2)，得：，得：n n0 0 + + n n1 1 + n + n2 2 -1= n -1= n1 1 + 2

16、 + 2n n2 2則可以得到則可以得到: :+1 k-1-1 = bacedfghij證明：根據(jù)性質(zhì)證明：根據(jù)性質(zhì)2 2，對于有對于有n n個結(jié)個結(jié)點(diǎn)的深度為點(diǎn)的深度為k k的完全二叉樹有的完全二叉樹有: : 因?yàn)樵摬坏仁礁黜?xiàng)均為整數(shù)，當(dāng)對兩端各加因?yàn)樵摬坏仁礁黜?xiàng)均為整數(shù)，當(dāng)對兩端各加1 1時不時不等式發(fā)生變化得：等式發(fā)生變化得：對不等式求對數(shù)，有對不等式求對數(shù)，有因?yàn)橐驗(yàn)閗必須是整數(shù)，所以對必須是整數(shù)，所以對log2(n) 取整，即取整，即顯顯然得到：然得到：即即: k= 對于一棵有對于一棵有n個結(jié)點(diǎn)的完全二叉樹，按照從上至下個結(jié)點(diǎn)的完全二叉樹，按照從上至下和從左至右的順序?qū)λ薪Y(jié)點(diǎn)從和從

17、左至右的順序?qū)λ薪Y(jié)點(diǎn)從1開始順序編號。開始順序編號。bacedfghij1 12 23 34 45 56 67 78 89 91010n=10n=10當(dāng)當(dāng)i=1i=1時，該結(jié)點(diǎn)為根結(jié)點(diǎn)，時，該結(jié)點(diǎn)為根結(jié)點(diǎn)，它無雙親結(jié)點(diǎn)；它無雙親結(jié)點(diǎn)；則對于序號為則對于序號為 i i 的結(jié)點(diǎn)的結(jié)點(diǎn)(1in),(1in),有：有：當(dāng)當(dāng)i1i1時，其雙親是結(jié)點(diǎn)時，其雙親是結(jié)點(diǎn)i/2 i/2 (“/”(“/”表示整除）；表示整除）；若若2in2in，則第，則第i i個結(jié)點(diǎn)有編號為個結(jié)點(diǎn)有編號為2i2i的左孩子；的左孩子；若若2i+1n2i+1n，則第，則第i i 個結(jié)點(diǎn)有編號為個結(jié)點(diǎn)有編號為2i+12i+1的右孩子

18、的右孩子 完全二叉樹的結(jié)點(diǎn)可按從上到下和從左至右的次完全二叉樹的結(jié)點(diǎn)可按從上到下和從左至右的次序存儲在一維數(shù)組中，其結(jié)點(diǎn)之間的關(guān)系可由公式計序存儲在一維數(shù)組中，其結(jié)點(diǎn)之間的關(guān)系可由公式計算得到，這就是二叉樹的順序存儲結(jié)構(gòu)。下面兩棵樹算得到，這就是二叉樹的順序存儲結(jié)構(gòu)。下面兩棵樹在數(shù)組中的存儲結(jié)構(gòu)分別為：在數(shù)組中的存儲結(jié)構(gòu)分別為：二叉樹的存儲結(jié)構(gòu)有多種，最常用的有兩種：二叉樹的存儲結(jié)構(gòu)有多種，最常用的有兩種：順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)1. 1. 二叉樹的順序存儲結(jié)構(gòu)二叉樹的順序存儲結(jié)構(gòu)bacedfghijklmno1204357611810912 13 14 15da

19、bconmlkjihgfe1 12 23 34 45 56 67 78 89 9 1010n=15n=1511111212131314141515滿二叉樹：滿二叉樹：結(jié)點(diǎn)：結(jié)點(diǎn)：i=5i=5父結(jié)點(diǎn)：父結(jié)點(diǎn)：i/2=5/2=2i/2=5/2=2左孩子：左孩子：2i=22i=2* *5=105=10右孩子：右孩子：2i+1=22i+1=2* *5+1=115+1=11完全二叉樹：完全二叉樹：bacedfghij1 12 23 34 45 56 67 78 89 9 1010n=10n=10120435768910a bcdjihgfe對于一般的非完全二叉樹對于一般的非完全二叉樹bacegdfa b

20、cgfed1204357611810912數(shù)組數(shù)組下標(biāo)下標(biāo)13 必須首先在非完全二叉樹中增添一些并不存在的空結(jié)點(diǎn)使之必須首先在非完全二叉樹中增添一些并不存在的空結(jié)點(diǎn)使之變成完全二叉樹的形態(tài)。變成完全二叉樹的形態(tài)。 然后再用順序存儲結(jié)構(gòu)存儲在一維數(shù)組中。然后再用順序存儲結(jié)構(gòu)存儲在一維數(shù)組中。 顯然不能直接使用二叉樹的順序存儲結(jié)構(gòu)。顯然不能直接使用二叉樹的順序存儲結(jié)構(gòu)。所以，順序存儲結(jié)構(gòu)僅適于滿二叉樹或完全二叉樹，一般二叉樹所以，順序存儲結(jié)構(gòu)僅適于滿二叉樹或完全二叉樹，一般二叉樹更適宜用鏈表存儲結(jié)構(gòu)更適宜用鏈表存儲結(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是用指針建立二叉樹中結(jié)點(diǎn)之間的關(guān)系。二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是用

21、指針建立二叉樹中結(jié)點(diǎn)之間的關(guān)系。二叉二叉樹最常用的的鏈?zhǔn)奖韮Y(jié)構(gòu)是二叉鏈和三叉鏈。樹最常用的的鏈?zhǔn)奖韮Y(jié)構(gòu)是二叉鏈和三叉鏈。二叉鏈存儲結(jié)構(gòu)的每二叉鏈存儲結(jié)構(gòu)的每個結(jié)點(diǎn)包含三個域，分別是數(shù)據(jù)域個結(jié)點(diǎn)包含三個域，分別是數(shù)據(jù)域data、左孩子指針域、左孩子指針域leftchild和右和右孩子指針域孩子指針域rightchild。二叉鏈存儲結(jié)構(gòu)中每個結(jié)點(diǎn)的圖示結(jié)構(gòu)為：。二叉鏈存儲結(jié)構(gòu)中每個結(jié)點(diǎn)的圖示結(jié)構(gòu)為：rightchilddataleftchild 三叉鏈表的結(jié)點(diǎn)比前者多三叉鏈表的結(jié)點(diǎn)比前者多了一個指向雙親的指針域。了一個指向雙親的指針域。2. 2. 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)結(jié)點(diǎn)結(jié)

22、構(gòu)描為：結(jié)點(diǎn)結(jié)構(gòu)描為：typedef struct node elemtype data; struct node *lch,*rch; bnode;typedef struct node elemtype data; struct node *lch,*par,*rch; /*par是雙親指針域是雙親指針域*/ bnode3;parrchdatalch結(jié)點(diǎn)結(jié)構(gòu)描為：結(jié)點(diǎn)結(jié)構(gòu)描為：a bcd f j k abcdfjk bacdjfk二叉鏈表二叉鏈表三叉鏈表三叉鏈表二叉樹二叉樹二叉樹的仿真指針存儲二叉樹的仿真指針存儲結(jié)構(gòu)結(jié)構(gòu)是用數(shù)組存儲二叉樹中的結(jié)點(diǎn)，是用數(shù)組存儲二叉樹中的結(jié)點(diǎn)，數(shù)組中每個結(jié)點(diǎn)

23、除數(shù)據(jù)元素域外，再增加仿真指針域用于仿數(shù)組中每個結(jié)點(diǎn)除數(shù)據(jù)元素域外，再增加仿真指針域用于仿真常規(guī)指針建立二叉樹中結(jié)點(diǎn)之間的關(guān)系。真常規(guī)指針建立二叉樹中結(jié)點(diǎn)之間的關(guān)系。二叉樹的仿真二叉鏈存儲結(jié)構(gòu)二叉樹的仿真二叉鏈存儲結(jié)構(gòu)bacdgef二叉樹的仿真指針二叉樹的仿真指針6.2.5 二叉樹二叉鏈表的一個生成算法二叉樹二叉鏈表的一個生成算法 創(chuàng)建二叉樹的方法有多種，并且算法都比較復(fù)雜，這里我們創(chuàng)建二叉樹的方法有多種，并且算法都比較復(fù)雜，這里我們運(yùn)用二叉樹的性質(zhì)運(yùn)用二叉樹的性質(zhì)5 5，學(xué)習(xí)一種較簡單的生成算法。，學(xué)習(xí)一種較簡單的生成算法。 對任意二叉樹，首先按滿二叉樹的結(jié)構(gòu)對其結(jié)點(diǎn)進(jìn)行編號。對任意二叉樹，

24、首先按滿二叉樹的結(jié)構(gòu)對其結(jié)點(diǎn)進(jìn)行編號。1211131416151 12 23 34 45 56 67 78 89 9i123469x111213141516 此樹并非完全二叉樹，此樹并非完全二叉樹，因此結(jié)點(diǎn)編號不連續(xù)。算因此結(jié)點(diǎn)編號不連續(xù)。算法中用一個輔助向量法中用一個輔助向量s s存存放樹結(jié)點(diǎn)的指針。該向量放樹結(jié)點(diǎn)的指針。該向量的類型為：的類型為：bnode *smaxsizebnode *creat() bnode *t=null; printf(“n i,x=”);scanf(“%d%d”,&i,&x); while(i!=0&x!=0) q=(bnode *)malloc(sizeof

25、(bnode); q-data=x;q-lch=null;q-rch=null; si=q; /* bnode *s20 */ if(i=1)t=q; /* t為樹根結(jié)點(diǎn)為樹根結(jié)點(diǎn) */ else j=i/2; /* j為雙親結(jié)點(diǎn)編號為雙親結(jié)點(diǎn)編號 */ if(i%2)=0)sj-lch=q;else sj-rch=q; printf(“n i,x=”); scanf(“%d%d”,&i,&x); return t; /* creat end */typedef struct node elemtype data; struct node *lch,*rch; bnode;0123456789

26、10 11 12 13 14 15 16 17 18 19* *s s1211131416151 12 23 34 46 69 9ti的父結(jié)點(diǎn)：的父結(jié)點(diǎn)：ti/2 左孩子：左孩子：t2i 右孩子：右孩子：t2i+16.3 6.3 二叉樹遍歷二叉樹遍歷 遍歷二叉樹是指以一定的次序訪問二叉樹中的每個遍歷二叉樹是指以一定的次序訪問二叉樹中的每個結(jié)點(diǎn)，并且每個結(jié)點(diǎn)僅訪問一次。所謂訪問結(jié)點(diǎn)是指對結(jié)點(diǎn)，并且每個結(jié)點(diǎn)僅訪問一次。所謂訪問結(jié)點(diǎn)是指對結(jié)點(diǎn)進(jìn)行各種操作的簡稱。結(jié)點(diǎn)進(jìn)行各種操作的簡稱。 遍歷二叉樹的過程實(shí)質(zhì)上是把二叉樹的結(jié)點(diǎn)進(jìn)行線遍歷二叉樹的過程實(shí)質(zhì)上是把二叉樹的結(jié)點(diǎn)進(jìn)行線性排列的過程。假如訪問結(jié)點(diǎn)

27、的操作是輸出結(jié)點(diǎn)數(shù)據(jù)域性排列的過程。假如訪問結(jié)點(diǎn)的操作是輸出結(jié)點(diǎn)數(shù)據(jù)域的值，那么遍歷的結(jié)果就會得到一個線性序列。的值，那么遍歷的結(jié)果就會得到一個線性序列。 由于二叉樹有左、右子樹，因此遍歷的次序不同，由于二叉樹有左、右子樹，因此遍歷的次序不同，得到的結(jié)果也就不同。得到的結(jié)果也就不同。 從二叉樹的定義知，一棵二叉樹由三部分組成：根從二叉樹的定義知，一棵二叉樹由三部分組成：根結(jié)點(diǎn)、左子樹和右子樹。結(jié)點(diǎn)、左子樹和右子樹。則有三種不同的遍歷次序：則有三種不同的遍歷次序： tlr-前序遍歷（先根遍歷）前序遍歷（先根遍歷） ltr-中序遍歷（中根遍歷）中序遍歷（中根遍歷） lrt-后序遍歷后序遍歷（后根遍

28、歷）（后根遍歷）若規(guī)定：若規(guī)定： t-代表訪問根結(jié)點(diǎn)代表訪問根結(jié)點(diǎn) l-代表遍歷根結(jié)點(diǎn)的左子樹代表遍歷根結(jié)點(diǎn)的左子樹 r-代表遍歷根結(jié)點(diǎn)的右子樹代表遍歷根結(jié)點(diǎn)的右子樹t tl lr rt tl lrabcddd遍歷搜索示意圖遍歷搜索示意圖圖中二叉樹有四個結(jié)點(diǎn)圖中二叉樹有四個結(jié)點(diǎn)abcdabcd，為了便于理解遍歷的思想，為每個沒有子樹的，為了便于理解遍歷的思想，為每個沒有子樹的結(jié)點(diǎn)補(bǔ)上相應(yīng)的空子樹。結(jié)點(diǎn)補(bǔ)上相應(yīng)的空子樹。設(shè)想有一條搜索路線設(shè)想有一條搜索路線.，它從根結(jié)點(diǎn)的左側(cè)開始，自上而下，自左至右搜索，它從根結(jié)點(diǎn)的左側(cè)開始，自上而下，自左至右搜索，最后從根結(jié)點(diǎn)的右側(cè)向上出去。恰好搜索線途經(jīng)每個

29、有效樹結(jié)點(diǎn)都是三次最后從根結(jié)點(diǎn)的右側(cè)向上出去。恰好搜索線途經(jīng)每個有效樹結(jié)點(diǎn)都是三次搜索線第一次經(jīng)過就訪問的結(jié)點(diǎn)序列搜索線第一次經(jīng)過就訪問的結(jié)點(diǎn)序列abcdabcd，稱先根遍歷；搜索線第二次經(jīng)過才，稱先根遍歷；搜索線第二次經(jīng)過才訪問的結(jié)點(diǎn)序列訪問的結(jié)點(diǎn)序列badcbadc，稱中根遍歷；搜索線第三次經(jīng)過才訪問的序列，稱中根遍歷；搜索線第三次經(jīng)過才訪問的序列bdca,bdca,稱稱后根遍歷后根遍歷a,b,c,d a,b,c,d 先根（前序）遍歷先根（前序）遍歷b,a,d,c b,a,d,c 中根（序）遍歷中根（序）遍歷b,d,c,a b,d,c,a 后根（序）遍歷后根（序）遍歷二叉樹選擇不同的存儲結(jié)

30、構(gòu)，遍歷算法的程序代碼會二叉樹選擇不同的存儲結(jié)構(gòu)，遍歷算法的程序代碼會有所不同。這里確定用二叉鏈表作為存儲結(jié)構(gòu)，樹中有所不同。這里確定用二叉鏈表作為存儲結(jié)構(gòu)，樹中結(jié)點(diǎn)的結(jié)構(gòu)定義為：結(jié)點(diǎn)的結(jié)構(gòu)定義為：typedef struct node elemtype data; struct node *lch,*rch; bnode;若根為空則結(jié)束；否則：若根為空則結(jié)束；否則：（1 1）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)；（2 2）按先根次序遍歷左子樹；）按先根次序遍歷左子樹；（3 3）按先根次序遍歷右子樹。）按先根次序遍歷右子樹。6.3.1 先根遍歷先根遍歷（先根遍歷（tlrtlr）遞歸算法為：）遞歸算法為：v

31、oid preorder(bnode *p) if(p!=null) printf(“%6c”,p-data); preorder(p-lch); preorder(p-rch); /* preorder */此處假設(shè)此處假設(shè)elemtypeelemtype為為charchar型型abcda b c d p p訪問訪問a遍歷左子樹遍歷左子樹遍歷右子樹遍歷右子樹返回返回訪問訪問b遍歷左子樹遍歷左子樹遍歷右子樹遍歷右子樹返回返回訪問訪問c遍歷左子樹遍歷左子樹遍歷右子樹遍歷右子樹返回返回訪問訪問d遍歷左子樹遍歷左子樹遍歷右子樹遍歷右子樹返回返回根為根為nullnull返回返回根為根為nullnull

32、返回返回根為根為nullnull返回返回根為根為nullnull返回返回根為根為nullnull返回返回若根為空則結(jié)束；否則：若根為空則結(jié)束；否則：（1 1）按中根次序遍歷左子樹；）按中根次序遍歷左子樹；（2 2）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)；（3 3）按中根次序遍歷右子樹。）按中根次序遍歷右子樹。6.3.2 中根遍歷中根遍歷（中根遍歷（ltrltr）與先根遍歷相似，只是在根不空時將算法的第一）與先根遍歷相似，只是在根不空時將算法的第一步與第二步次序?qū)Q而已，即：步與第二步次序?qū)Q而已，即：void inorder(bnode *p) if(p!=null) inorder(p-lch); pri

33、ntf(“%6c”,p-data); inorder(p-rch); /* inorder */此處假設(shè)此處假設(shè)elemtypeelemtype為為charchar型型實(shí)現(xiàn)算法的代碼也是在先根實(shí)現(xiàn)算法的代碼也是在先根算法基礎(chǔ)上稍做改動，即：算法基礎(chǔ)上稍做改動，即：遞歸算法簡練但執(zhí)行效率較低，遞歸算法簡練但執(zhí)行效率較低，而且有些高級也不支持遞歸調(diào)而且有些高級也不支持遞歸調(diào)用，作為程序設(shè)計能力的訓(xùn)練，用，作為程序設(shè)計能力的訓(xùn)練，有必要學(xué)習(xí)非遞歸算法。有必要學(xué)習(xí)非遞歸算法。s s01234中根遍歷的非遞歸算法如下：中根遍歷的非遞歸算法如下：voide inorderz(bnode *p) /* 棧棧

34、s是是bnode *s10 */ q=p; top =0; /*棧頂指針棧頂指針*/ bool =1; /* bool=1表示棧不空表示棧不空*/ printf(“n 中根遍歷：中根遍歷：n”); do while(q!=null) top+; stop=q; q=q-lch; if(top=0) bool = 0; else q=stop; top-; printf(“%6c”,q-data); /*訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn)*/ q=q-rch; while(bool); printf(“n”); /* inorderz */abcda b c d p ptopc ab dtoptop6.3.3

35、 后根遍歷若根為空則結(jié)束；否則：若根為空則結(jié)束；否則：（1 1）按后根次序遍歷左子樹；）按后根次序遍歷左子樹；（2 2）按后根次序遍歷右子樹；）按后根次序遍歷右子樹；（3 3）訪問根結(jié)點(diǎn)。）訪問根結(jié)點(diǎn)。void postorder(bnode *p) if(p!=null) postorder(p-lch); postorder(p-rch); printf(“%6c”,p-data); /* postorder */ 后根遍歷的非遞歸算法較為復(fù)雜，它需要兩個棧，第一個棧后根遍歷的非遞歸算法較為復(fù)雜，它需要兩個棧，第一個棧的用途與中根遍歷相同，第二個棧用來經(jīng)過某根結(jié)點(diǎn)的次數(shù)。兩的用途與中根遍歷

36、相同，第二個棧用來經(jīng)過某根結(jié)點(diǎn)的次數(shù)。兩個棧的數(shù)據(jù)類型為：個棧的數(shù)據(jù)類型為：bnode bnode * *s10;int s220;s10;int s220; 具體算法程序留給同學(xué)們課外閱讀。（具體算法程序留給同學(xué)們課外閱讀。（p111p111）void levelorder(bnode *p) bnode *q20; front =0; rear=0; if(p!=null)rear+;qrear=p; /*根結(jié)點(diǎn)不空，進(jìn)隊(duì)根結(jié)點(diǎn)不空，進(jìn)隊(duì)*/ while(front!=rear) front+; p=qfront; printf(“%6c”,p-data); /* 出隊(duì)并訪問出隊(duì)并訪問*/

37、 if(p-lch!=null) rear+; qrear=p-lch; /*若左孩子不空，進(jìn)隊(duì)若左孩子不空，進(jìn)隊(duì)*/ if(p-rch!=null) rear+; qrear=p-rch;/*若左孩子不空，進(jìn)隊(duì)若左孩子不空，進(jìn)隊(duì)*/ /* levelorder */6.3.4 按層遍歷二叉樹ab c d fj k bacdjfkpfr109876543210qrrrrrrrfffffffabcdfjkpppppp（1 1）初始化設(shè)置一個隊(duì)列；）初始化設(shè)置一個隊(duì)列；（2 2）把根結(jié)點(diǎn)指針入隊(duì)列；）把根結(jié)點(diǎn)指針入隊(duì)列；（3 3）當(dāng)隊(duì)列非空時，循環(huán)執(zhí)行步驟）當(dāng)隊(duì)列非空時，循環(huán)執(zhí)行步驟（3.a）到步

38、驟到步驟（3.c）（3.a3.a）出隊(duì)列取得一個結(jié)點(diǎn)指針，訪問該結(jié)點(diǎn)；）出隊(duì)列取得一個結(jié)點(diǎn)指針，訪問該結(jié)點(diǎn)；（3.b3.b）若該結(jié)點(diǎn)的左子樹非空，則將該結(jié)點(diǎn)的左子樹指）若該結(jié)點(diǎn)的左子樹非空，則將該結(jié)點(diǎn)的左子樹指針入隊(duì)列；針入隊(duì)列；（3.c3.c）若該結(jié)點(diǎn)的右子樹非空，則將該結(jié)點(diǎn)的右子樹指）若該結(jié)點(diǎn)的右子樹非空，則將該結(jié)點(diǎn)的右子樹指針入隊(duì)列；針入隊(duì)列；（4 4）結(jié)束。）結(jié)束。按層遍歷二叉樹的算法可以用語言描述如下： 按層遍歷二叉樹被稱為按層遍歷二叉樹被稱為層序遍歷層序遍歷。層序遍歷的要求是：。層序遍歷的要求是：按二叉樹的層序次序（即按二叉樹的層序次序（即從根結(jié)點(diǎn)層至葉結(jié)點(diǎn)層從根結(jié)點(diǎn)層至葉結(jié)點(diǎn)層）

39、，同一），同一層中按層中按先左子樹再右子樹先左子樹再右子樹的次序遍歷二叉樹。的次序遍歷二叉樹?？梢越柚?duì)列實(shí)現(xiàn)二叉樹的層序遍歷可以借助隊(duì)列實(shí)現(xiàn)二叉樹的層序遍歷。 它的特點(diǎn)是，在所有未被訪問結(jié)點(diǎn)的集合中，排列它的特點(diǎn)是，在所有未被訪問結(jié)點(diǎn)的集合中，排列在已訪問結(jié)點(diǎn)集合中最前面結(jié)點(diǎn)的左孩子將最先被訪問，在已訪問結(jié)點(diǎn)集合中最前面結(jié)點(diǎn)的左孩子將最先被訪問，然后是該結(jié)點(diǎn)的右孩子。這樣，如果把已訪問的結(jié)點(diǎn)放然后是該結(jié)點(diǎn)的右孩子。這樣，如果把已訪問的結(jié)點(diǎn)放在一個隊(duì)列中，那么，所有未被訪問結(jié)點(diǎn)的訪問次序就在一個隊(duì)列中，那么，所有未被訪問結(jié)點(diǎn)的訪問次序就可以由存放在隊(duì)列中的已訪問結(jié)點(diǎn)的出隊(duì)列次序決定。可以由存放

40、在隊(duì)列中的已訪問結(jié)點(diǎn)的出隊(duì)列次序決定。因此因此把二叉樹逆時針旋轉(zhuǎn)把二叉樹逆時針旋轉(zhuǎn)900c，按照二叉樹的凹入表示法打印按照二叉樹的凹入表示法打印二叉樹。可把此函數(shù)設(shè)計成遞二叉樹?？砂汛撕瘮?shù)設(shè)計成遞歸函數(shù)。由于把二叉樹逆時針歸函數(shù)。由于把二叉樹逆時針旋轉(zhuǎn)旋轉(zhuǎn)900c后，在屏幕上方的首后，在屏幕上方的首先是右子樹，然后是根結(jié)點(diǎn)，先是右子樹，然后是根結(jié)點(diǎn)，最后是左子樹，所以最后是左子樹，所以打印二叉打印二叉樹算法是一種特殊的中序遍歷樹算法是一種特殊的中序遍歷算法。算法。6.3.5 二叉樹遍歷的應(yīng)用1 1 打印二叉樹打印二叉樹void printbitree(bnode *bt, int n) int

41、 i; if(bt = null) return; printbitree(bt-rightchild, n+1); for(i = 0; i 0) printf(-); printf(%cn, bt-data); printbitree(bt-leftchild, n+1);在二叉樹中查找數(shù)據(jù)元素操作在二叉樹中查找數(shù)據(jù)元素操作的要求是：在的要求是：在bt為根結(jié)點(diǎn)指針的二為根結(jié)點(diǎn)指針的二叉樹中查找數(shù)據(jù)元素叉樹中查找數(shù)據(jù)元素x，若查找到，若查找到數(shù)據(jù)元素數(shù)據(jù)元素x時返回該結(jié)點(diǎn)的指針；時返回該結(jié)點(diǎn)的指針；若查找不到數(shù)據(jù)元素若查找不到數(shù)據(jù)元素x時返回空指時返回空指針。針。在二叉樹在二叉樹bt中查找數(shù)

42、據(jù)元素中查找數(shù)據(jù)元素x算法可設(shè)計成先序遍歷算法，此時算法可設(shè)計成先序遍歷算法，此時查找結(jié)點(diǎn)的次序是：首先在根結(jié)點(diǎn)查找結(jié)點(diǎn)的次序是：首先在根結(jié)點(diǎn)查找，然后在左子樹查找，最后在查找，然后在左子樹查找，最后在右子樹查找。但是，和常規(guī)遞歸算右子樹查找。但是，和常規(guī)遞歸算法不同的是，此算法當(dāng)一個分支上法不同的是，此算法當(dāng)一個分支上的結(jié)點(diǎn)比較完仍未查找到數(shù)據(jù)元素的結(jié)點(diǎn)比較完仍未查找到數(shù)據(jù)元素x時，要返回到該結(jié)點(diǎn)的雙親結(jié)點(diǎn)時，要返回到該結(jié)點(diǎn)的雙親結(jié)點(diǎn)處繼續(xù)查找。因此，此算法是一個處繼續(xù)查找。因此，此算法是一個回溯算法回溯算法 。2 2 查找數(shù)據(jù)元素查找數(shù)據(jù)元素bitreenode *search(bnode

43、 *bt, elemtype x) bitreenode *p; if(bt = null) return null; if(bt-data = x) return bt; if(bt-leftchild != null) p = search(bt-leftchild, x); if(p != null) return p; if(bt-rightchild != null) p = search(bt-rightchild, x); if(p != null) return p; return null;6.4 線索二叉樹 線索二叉樹是另一種分步遍歷二叉樹的方法。它線索二叉樹是另一種分步遍歷二叉樹的方法。它既可以從前向后既可以從前向后分步遍歷二叉樹，分步遍歷二叉樹，又可以從后向前又可以從后向前分步遍歷二叉樹。分步遍歷二叉樹。 當(dāng)按某種規(guī)則遍歷二叉樹時，保存遍歷時得到的結(jié)點(diǎn)的后繼結(jié)點(diǎn)當(dāng)按某種規(guī)則遍歷二叉樹時，保存遍歷時得到的結(jié)點(diǎn)的后繼結(jié)點(diǎn)信息和前驅(qū)結(jié)點(diǎn)信息的最常用的方法是建立線索二叉樹。信息和前驅(qū)結(jié)點(diǎn)信息的最常用的方法是建立線索二叉樹。 對二叉鏈表存儲結(jié)構(gòu)的二叉樹分析可知，在有對二叉鏈表存儲結(jié)構(gòu)的二叉樹分析可知，在有