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

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

2、運(yùn)算。大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)樹(shù)樹(shù)(tree)是由是由n(n0)個(gè)結(jié)點(diǎn)組成的有限集合個(gè)結(jié)點(diǎn)組成的有限集合T。n=0的的樹(shù)稱(chēng)為空樹(shù)；對(duì)樹(shù)稱(chēng)為空樹(shù)；對(duì)n0的樹(shù)，有的樹(shù)，有:(1)僅有僅有一個(gè)特殊的結(jié)點(diǎn)稱(chēng)為根一個(gè)特殊的結(jié)點(diǎn)稱(chēng)為根(root)結(jié)點(diǎn)結(jié)點(diǎn)，根結(jié)點(diǎn)沒(méi)，根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)；有前驅(qū)結(jié)點(diǎn)；(2)當(dāng)當(dāng)n1時(shí)，除根結(jié)點(diǎn)外其余的結(jié)點(diǎn)分為時(shí)，除根結(jié)點(diǎn)外其余的結(jié)點(diǎn)分為m(m0)個(gè)個(gè)互互不相交不相交的有限集合的有限集合T1,T2，Tm，其中每個(gè)集合，其中每個(gè)集合Ti本身又本身又是一棵樹(shù)，稱(chēng)之為根的子樹(shù)（是一棵樹(shù)，稱(chēng)之為根的子樹(shù)（ subtree）。）。注：注：樹(shù)的定義具有樹(shù)的定義具有遞歸性遞歸性，即，即“樹(shù)

3、中還有樹(shù)樹(shù)中還有樹(shù)”。 僅有一個(gè)根結(jié)點(diǎn)的樹(shù)是最小樹(shù)，僅有一個(gè)根結(jié)點(diǎn)的樹(shù)是最小樹(shù)，大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)分支結(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ù)的個(gè)數(shù)的子樹(shù)的個(gè)數(shù)樹(shù)的度：樹(shù)的度：樹(shù)中所有結(jié)點(diǎn)的度的最大值樹(shù)中所有結(jié)點(diǎn)的度的最大值葉結(jié)點(diǎn)：葉結(jié)點(diǎn)：度為度為0 0的結(jié)點(diǎn)，也稱(chēng)作的結(jié)點(diǎn)，也稱(chēng)作終端結(jié)點(diǎn)終端結(jié)點(diǎn)結(jié)點(diǎn)的層次：結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)到樹(shù)中某結(jié)點(diǎn)

4、所經(jīng)路徑上的分支數(shù)從根結(jié)點(diǎn)到樹(shù)中某結(jié)點(diǎn)所經(jīng)路徑上的分支數(shù)樹(shù)的深度：樹(shù)的深度：樹(shù)中所有結(jié)點(diǎn)的層次的最大值樹(shù)中所有結(jié)點(diǎn)的層次的最大值 森林：森林：m m（m m00）棵樹(shù)的集合）棵樹(shù)的集合 大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)孩子孩子(child)(child)結(jié)點(diǎn)結(jié)點(diǎn)：樹(shù)中一個(gè)結(jié)點(diǎn)的子樹(shù)的根結(jié)點(diǎn)樹(shù)中一個(gè)結(jié)點(diǎn)的子樹(shù)的根結(jié)點(diǎn)雙親雙親(parent)(parent)結(jié)點(diǎn)：結(jié)點(diǎn)：若樹(shù)中某結(jié)點(diǎn)有孩子結(jié)點(diǎn)，則這個(gè)若樹(shù)中某結(jié)點(diǎn)有孩子結(jié)點(diǎn)，則這個(gè)結(jié)點(diǎn)就稱(chēng)作它的孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)結(jié)點(diǎn)就稱(chēng)作它的孩子結(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) ABC

5、GEIDHFJMLK大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)無(wú)序樹(shù)：無(wú)序樹(shù)：樹(shù)中任意一個(gè)結(jié)點(diǎn)的各孩子結(jié)點(diǎn)之間的樹(shù)中任意一個(gè)結(jié)點(diǎn)的各孩子結(jié)點(diǎn)之間的次序構(gòu)成次序構(gòu)成 無(wú)關(guān)緊要無(wú)關(guān)緊要的樹(shù)的樹(shù)有序樹(shù)：有序樹(shù)：樹(shù)中任意一個(gè)結(jié)點(diǎn)的各孩子結(jié)點(diǎn)有嚴(yán)格排列次序的樹(shù)樹(shù)中任意一個(gè)結(jié)點(diǎn)的各孩子結(jié)點(diǎn)有嚴(yán)格排列次序的樹(shù)BEFLKBFELK大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)(1)(1)倒懸樹(shù)法倒懸樹(shù)法( (直觀表示直觀表示) ) (2)(2)集合包含關(guān)系圖法集合包含關(guān)系圖法 (3)(3)凹入表示法凹入表示法 ABCGEIDHFJMLK FEKLCGBI IJ JMDHABCDEFGHIJKLM大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)數(shù)據(jù)集合數(shù)據(jù)集合: 樹(shù)的

6、結(jié)點(diǎn)集合，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)元素和構(gòu)造數(shù)樹(shù)的結(jié)點(diǎn)集合，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)元素和構(gòu)造數(shù) 據(jù)元素之間關(guān)系的指針組成。據(jù)元素之間關(guān)系的指針組成。操作集合操作集合: （1 1）創(chuàng)建）創(chuàng)建MakeTree(T) MakeTree(T) （2 2）撤消）撤消DestroyTree(T)DestroyTree(T)（3 3）雙親結(jié)點(diǎn)）雙親結(jié)點(diǎn)Parent(T, curr) Parent(T, curr) （4 4）左孩子結(jié)點(diǎn)）左孩子結(jié)點(diǎn)LeftChild(T, curr) LeftChild(T, curr) （5 5）右兄弟結(jié)點(diǎn)）右兄弟結(jié)點(diǎn)RightSibling(T, curr) RightSibling(T,

7、 curr) （6 6）遍歷樹(shù)）遍歷樹(shù)Traverse(T, Visit()Traverse(T, Visit()大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù) 樹(shù)的結(jié)點(diǎn)之間的邏輯關(guān)系主要有雙親樹(shù)的結(jié)點(diǎn)之間的邏輯關(guān)系主要有雙親- -孩子孩子關(guān)系，兄弟關(guān)系。因此，從結(jié)點(diǎn)之間的邏輯關(guān)系關(guān)系，兄弟關(guān)系。因此，從結(jié)點(diǎn)之間的邏輯關(guān)系分，樹(shù)的存儲(chǔ)結(jié)構(gòu)主要有：分，樹(shù)的存儲(chǔ)結(jié)構(gòu)主要有：雙親表示法、孩子表雙親表示法、孩子表示法、雙親孩子表示法和孩子兄弟表示法示法、雙親孩子表示法和孩子兄弟表示法四種組四種組合。合。 指針有指針有常規(guī)指針常規(guī)指針和和仿真指針?lè)抡嬷羔槾髮W(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)4H2G1F1E1D0C0B-1AI4dat

8、a parentdata parent0 01 12 23 34 45 56 67 78 8(1)(1)雙親表示法雙親表示法(a)一棵樹(shù)一棵樹(shù)（b)仿真指針的雙親表示法存儲(chǔ)結(jié)構(gòu)仿真指針的雙親表示法存儲(chǔ)結(jié)構(gòu)樹(shù)及其使用仿真指針的雙親表示法樹(shù)及其使用仿真指針的雙親表示法ABCFGEIHD大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)(2)(2)孩子表示法孩子表示法常規(guī)指針的孩子表示法常規(guī)指針的孩子表示法BCrootAD EF GIH ABCFGEIHD大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)雙親孩子表示法雙親孩子表示法(3)(3)雙親孩子表示法雙親孩子表示法4H2G1F1E1D0C0B-1AI4data parent headdat

9、a parent head012345678child nextchild next87123456ABCFGEIHD大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)(4)(4)孩子兄弟表示法孩子兄弟表示法常規(guī)指針的孩子兄弟表示法常規(guī)指針的孩子兄弟表示法rootBCDEFGHIAABCFGEIHD大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)二叉樹(shù)二叉樹(shù)(binary tree)：是是n(n0)個(gè)結(jié)點(diǎn)的有限集合。個(gè)結(jié)點(diǎn)的有限集合。n=0的樹(shù)稱(chēng)為空二叉樹(shù)；的樹(shù)稱(chēng)為空二叉樹(shù)；n0的二叉樹(shù)由一個(gè)根結(jié)點(diǎn)以的二叉樹(shù)由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱(chēng)為及兩棵互不相交的、分別稱(chēng)為左子樹(shù)和右子樹(shù)左子樹(shù)和右子樹(shù)的的二叉樹(shù)組成二叉樹(shù)組成 。其。其邏輯

10、結(jié)構(gòu)：邏輯結(jié)構(gòu)： 一對(duì)二（一對(duì)二（1:2）左、右子樹(shù)也是二叉樹(shù)，所以子樹(shù)也可以為空樹(shù)。下圖左、右子樹(shù)也是二叉樹(shù)，所以子樹(shù)也可以為空樹(shù)。下圖展現(xiàn)了五種不同形態(tài)的二叉樹(shù)。展現(xiàn)了五種不同形態(tài)的二叉樹(shù)。n=0n=0n=1n=1n1n1n1n1n1n1大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)基本特征基本特征: 每個(gè)結(jié)點(diǎn)最多只有兩棵子樹(shù)（不存在度大于每個(gè)結(jié)點(diǎn)最多只有兩棵子樹(shù)（不存在度大于2的結(jié)點(diǎn)）；的結(jié)點(diǎn)）； 左子樹(shù)和右子樹(shù)左子樹(shù)和右子樹(shù)次序不能顛倒次序不能顛倒。所以下面是兩棵不同的樹(shù)。所以下面是兩棵不同的樹(shù)BACEDFGBACEDFG大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)滿二叉樹(shù)：滿二叉樹(shù)：在一棵二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在

11、左在一棵二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣子樹(shù)和右子樹(shù)，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣的二叉樹(shù)稱(chēng)為滿二叉樹(shù)。的二叉樹(shù)稱(chēng)為滿二叉樹(shù)。BACEDFGHIJKLMNO大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)完全二叉樹(shù)：完全二叉樹(shù)：如果一棵深度為如果一棵深度為k k，有，有n n個(gè)結(jié)點(diǎn)的二叉樹(shù)中各個(gè)結(jié)點(diǎn)的二叉樹(shù)中各 結(jié)點(diǎn)能夠與深度為結(jié)點(diǎn)能夠與深度為k k的順序編號(hào)的滿二叉樹(shù)從的順序編號(hào)的滿二叉樹(shù)從1 1到到n n標(biāo)號(hào)的標(biāo)號(hào)的 結(jié)點(diǎn)相對(duì)應(yīng)的二叉樹(shù)稱(chēng)為完全二叉樹(shù)。如下圖所示結(jié)點(diǎn)相對(duì)應(yīng)的二叉樹(shù)稱(chēng)為完全二叉樹(shù)。如下圖所示BACEDFGHIJBACEDFGHIJKLMNO(

12、a)滿二叉樹(shù)滿二叉樹(shù) (b)完全二叉樹(shù)完全二叉樹(shù) 大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)數(shù)據(jù)集合：數(shù)據(jù)集合：二叉樹(shù)的結(jié)點(diǎn)集合，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)元素和構(gòu)造數(shù)二叉樹(shù)的結(jié)點(diǎn)集合，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關(guān)系的指針組成。據(jù)元素之間關(guān)系的指針組成。操作集合：操作集合：（1 1）創(chuàng)建）創(chuàng)建MakeTree(T) MakeTree(T) （2 2）撤消）撤消DestroyTree(T)DestroyTree(T)（3 3）左插入結(jié)點(diǎn)）左插入結(jié)點(diǎn)InsertLeftNode(curr, x) InsertLeftNode(curr, x) （4 4）右插入結(jié)點(diǎn)）右插入結(jié)點(diǎn)InsertRightNode(curr

13、, x) InsertRightNode(curr, x) （5 5）左刪除子樹(shù)）左刪除子樹(shù)DeleteLeftTree(curr) DeleteLeftTree(curr) （6 6）右刪除子樹(shù)）右刪除子樹(shù)DeleteRightTree(curr) DeleteRightTree(curr) （7 7）遍歷二叉樹(shù)）遍歷二叉樹(shù)Traverse(T, Visit()Traverse(T, Visit()大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)k=ik=i2 2i -1-1性質(zhì)性質(zhì)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 2

14、3-13-1=2=22 2=4=4BACEDFGHIJKLMNOi=4i=42 24-14-1=2=23 3=8=8k=ik=i大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)性質(zhì)性質(zhì)2:2: k3 2 1k3 2 1 0 00 0 0 00 0 1 1 2 20 0 0 00 0 00 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 11 1 1 2 0 11 1 1 2k k-1-1 =2=21 1=2=22 2=2=23 3=2=2k-1k-1=2=2k k=2=20 01 00 0 01 00 0 0+ +

15、 1 1k kBACEDFGHIJKLM NOk=ik=i2 2i -1-1qqaSnn1)1 (1n=kn=ka a1 1=1=1q=2q=2大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)性質(zhì)性質(zhì)3 3 對(duì)于一棵非空的二叉樹(shù)，如果葉結(jié)點(diǎn)個(gè)數(shù)為對(duì)于一棵非空的二叉樹(shù)，如果葉結(jié)點(diǎn)個(gè)數(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為二叉樹(shù)的結(jié)點(diǎn)總數(shù)，為二叉樹(shù)的結(jié)點(diǎn)總數(shù)，n n1 1為二叉樹(shù)為二叉樹(shù)中度為中度為1 1的結(jié)點(diǎn)個(gè)數(shù)，則有：的結(jié)點(diǎn)個(gè)數(shù)，則有：n = nn = n0 0 + n + n

16、1 1 + n + n2 2 (1)(1)由于二叉樹(shù)中除根結(jié)點(diǎn)外，由于二叉樹(shù)中除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有一條與其父每個(gè)結(jié)點(diǎn)都有一條與其父結(jié)點(diǎn)相連的邊。所以，有結(jié)點(diǎn)相連的邊。所以，有n n個(gè)結(jié)點(diǎn)的二叉樹(shù)總共有個(gè)結(jié)點(diǎn)的二叉樹(shù)總共有 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 + 2n n2 2則可以得到則可以得到: :大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)+1 k-1-

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

18、編號(hào)。開(kāi)始順序編號(hào)。BACEDFGHIJ1 12 23 34 45 56 67 78 89 91010n=10n=10當(dāng)當(dāng)i=1i=1時(shí)，該結(jié)點(diǎn)為根結(jié)點(diǎn)，時(shí)，該結(jié)點(diǎn)為根結(jié)點(diǎn)，它無(wú)雙親結(jié)點(diǎn)；它無(wú)雙親結(jié)點(diǎn)；則對(duì)于序號(hào)為則對(duì)于序號(hào)為 i i 的結(jié)點(diǎn)的結(jié)點(diǎn)(1in),(1in),有：有：當(dāng)當(dāng)i1i1時(shí)，其雙親是結(jié)點(diǎn)時(shí)，其雙親是結(jié)點(diǎn)i/2 i/2 (“/”(“/”表示整除）；表示整除）；若若2in2in，則第，則第i i個(gè)結(jié)點(diǎn)有編號(hào)為個(gè)結(jié)點(diǎn)有編號(hào)為2i2i的左孩子；的左孩子；若若2i+1n2i+1n，則第，則第i i 個(gè)結(jié)點(diǎn)有編號(hào)為個(gè)結(jié)點(diǎn)有編號(hào)為2i+12i+1的右孩子的右孩子大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)

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

20、 14 15DA BCONMLKJIHGFE1 12 23 34 45 56 67 78 89 9 1010n=15n=1511111212131314141515滿二叉樹(shù)：滿二叉樹(shù)：結(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大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)完全二叉樹(shù)：完全二叉樹(shù)：BACEDFGHIJ1 12 23 34 45 56 67 78 89 9 1010n=10n=10120435768910A BCDJIHGFE大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和

21、二叉樹(shù)對(duì)于一般的非完全二叉樹(shù)對(duì)于一般的非完全二叉樹(shù)BACEGDFA BCGFED1204357611810912數(shù)組數(shù)組下標(biāo)下標(biāo)13 必須首先在非完全二叉樹(shù)中增添一些并不存在的空結(jié)點(diǎn)使之必須首先在非完全二叉樹(shù)中增添一些并不存在的空結(jié)點(diǎn)使之變成完全二叉樹(shù)的形態(tài)。變成完全二叉樹(shù)的形態(tài)。 然后再用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)在一維數(shù)組中。然后再用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)在一維數(shù)組中。 顯然不能直接使用二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)。顯然不能直接使用二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)。所以，順序存儲(chǔ)結(jié)構(gòu)僅適于滿二叉樹(shù)或完全二叉樹(shù)，一般二叉樹(shù)所以，順序存儲(chǔ)結(jié)構(gòu)僅適于滿二叉樹(shù)或完全二叉樹(shù)，一般二叉樹(shù)更適宜用鏈表存儲(chǔ)結(jié)構(gòu)更適宜用鏈表存儲(chǔ)結(jié)構(gòu)大學(xué)數(shù)據(jù)結(jié)

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

23、雙親的指針域。了一個(gè)指向雙親的指針域。2. 2. 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(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;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)描為：大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)A BCD F J K ABCDFJK BACDJFK二叉鏈表二叉鏈表三叉鏈表三叉鏈表二叉樹(shù)二

24、叉樹(shù)大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)二叉樹(shù)的仿真指針存儲(chǔ)二叉樹(shù)的仿真指針存儲(chǔ)結(jié)構(gòu)結(jié)構(gòu)是用數(shù)組存儲(chǔ)二叉樹(shù)中的結(jié)點(diǎn)，是用數(shù)組存儲(chǔ)二叉樹(shù)中的結(jié)點(diǎn)，數(shù)組中每個(gè)結(jié)點(diǎn)除數(shù)據(jù)元素域外，再增加仿真指針域用于仿數(shù)組中每個(gè)結(jié)點(diǎn)除數(shù)據(jù)元素域外，再增加仿真指針域用于仿真常規(guī)指針建立二叉樹(shù)中結(jié)點(diǎn)之間的關(guān)系。真常規(guī)指針建立二叉樹(shù)中結(jié)點(diǎn)之間的關(guān)系。二叉樹(shù)的仿真二叉鏈存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的仿真二叉鏈存儲(chǔ)結(jié)構(gòu)BACDGEF二叉樹(shù)的仿真指針二叉樹(shù)的仿真指針大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)6.2.5 二叉樹(shù)二叉鏈表的一個(gè)生成算法二叉樹(shù)二叉鏈表的一個(gè)生成算法 創(chuàng)建二叉樹(shù)的方法有多種，并且算法都比較復(fù)雜，這里我們創(chuàng)建二叉樹(shù)的方法有多種，并且算法都比較復(fù)

25、雜，這里我們運(yùn)用二叉樹(shù)的性質(zhì)運(yùn)用二叉樹(shù)的性質(zhì)5 5，學(xué)習(xí)一種較簡(jiǎn)單的生成算法。，學(xué)習(xí)一種較簡(jiǎn)單的生成算法。 對(duì)任意二叉樹(shù)，首先按滿二叉樹(shù)的結(jié)構(gòu)對(duì)其結(jié)點(diǎn)進(jìn)行編號(hào)。對(duì)任意二叉樹(shù)，首先按滿二叉樹(shù)的結(jié)構(gòu)對(duì)其結(jié)點(diǎn)進(jìn)行編號(hào)。1211131416151 12 23 34 45 56 67 78 89 9i123469x111213141516 此樹(shù)并非完全二叉樹(shù)，此樹(shù)并非完全二叉樹(shù)，因此結(jié)點(diǎn)編號(hào)不連續(xù)。算因此結(jié)點(diǎn)編號(hào)不連續(xù)。算法中用一個(gè)輔助向量法中用一個(gè)輔助向量s s存存放樹(shù)結(jié)點(diǎn)的指針。該向量放樹(shù)結(jié)點(diǎn)的指針。該向量的類(lèi)型為：的類(lèi)型為：Bnode *sMAXSIZE大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)Bnode *cr

26、eat() Bnode *t=NULL; printf(“n i,x=”);scanf(“%d%d”,&i,&x); while(i!=0&x!=0) q=(Bnode *)malloc(sizeof(Bnode); q-data=x;q-lch=NULL;q-rch=NULL; si=q; /* Bnode *s20 */ if(i=1)t=q; /* t為樹(shù)根結(jié)點(diǎn)為樹(shù)根結(jié)點(diǎn) */ else j=i/2; /* j為雙親結(jié)點(diǎn)編號(hào)為雙親結(jié)點(diǎn)編號(hào) */ if(i%2)=0)sj-lch=q;else sj-rch=q; printf(“n i,x=”); scanf(“%

27、d%d”,&i,&x); return t; /* creat end */typedef struct node ElemType data; struct node *lch,*rch; Bnode;012345678910 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+1大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)6.3 6.3 二叉樹(shù)遍歷二叉樹(shù)遍歷 遍歷二叉樹(shù)是指以一定的次序訪問(wèn)二叉樹(shù)中的每個(gè)遍歷二叉樹(shù)是指以一定的次序訪問(wèn)二叉樹(shù)中

28、的每個(gè)結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)僅訪問(wèn)一次。所謂訪問(wèn)結(jié)點(diǎn)是指對(duì)結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)僅訪問(wèn)一次。所謂訪問(wèn)結(jié)點(diǎn)是指對(duì)結(jié)點(diǎn)進(jìn)行各種操作的簡(jiǎn)稱(chēng)。結(jié)點(diǎn)進(jìn)行各種操作的簡(jiǎn)稱(chēng)。 遍歷二叉樹(shù)的過(guò)程實(shí)質(zhì)上是把二叉樹(shù)的結(jié)點(diǎn)進(jìn)行線遍歷二叉樹(shù)的過(guò)程實(shí)質(zhì)上是把二叉樹(shù)的結(jié)點(diǎn)進(jìn)行線性排列的過(guò)程。假如訪問(wèn)結(jié)點(diǎn)的操作是輸出結(jié)點(diǎn)數(shù)據(jù)域性排列的過(guò)程。假如訪問(wèn)結(jié)點(diǎn)的操作是輸出結(jié)點(diǎn)數(shù)據(jù)域的值，那么遍歷的結(jié)果就會(huì)得到一個(gè)線性序列。的值，那么遍歷的結(jié)果就會(huì)得到一個(gè)線性序列。 由于二叉樹(shù)有左、右子樹(shù)，因此遍歷的次序不同，由于二叉樹(shù)有左、右子樹(shù)，因此遍歷的次序不同，得到的結(jié)果也就不同。得到的結(jié)果也就不同。大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù) 從二叉樹(shù)的定義知，一棵

29、二叉樹(shù)由三部分組成：根從二叉樹(shù)的定義知，一棵二叉樹(shù)由三部分組成：根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)。結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)。則有三種不同的遍歷次序：則有三種不同的遍歷次序： TLR-前序遍歷（先根遍歷）前序遍歷（先根遍歷） LTR-中序遍歷（中根遍歷）中序遍歷（中根遍歷） LRT-后序遍歷后序遍歷（后根遍歷）（后根遍歷）若規(guī)定：若規(guī)定： T-代表訪問(wèn)根結(jié)點(diǎn)代表訪問(wèn)根結(jié)點(diǎn) L-代表遍歷根結(jié)點(diǎn)的左子樹(shù)代表遍歷根結(jié)點(diǎn)的左子樹(shù) R-代表遍歷根結(jié)點(diǎn)的右子樹(shù)代表遍歷根結(jié)點(diǎn)的右子樹(shù)T TL LR RT TL LR大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)ABCDDD遍歷搜索示意圖遍歷搜索示意圖圖中二叉樹(shù)有四個(gè)結(jié)點(diǎn)圖中二叉樹(shù)有四個(gè)結(jié)點(diǎn)AB

30、CDABCD，為了便于理解遍歷的思想，為每個(gè)沒(méi)有子樹(shù)的，為了便于理解遍歷的思想，為每個(gè)沒(méi)有子樹(shù)的結(jié)點(diǎn)補(bǔ)上相應(yīng)的空子樹(shù)。結(jié)點(diǎn)補(bǔ)上相應(yīng)的空子樹(shù)。設(shè)想有一條搜索路線設(shè)想有一條搜索路線.，它從根結(jié)點(diǎn)的左側(cè)開(kāi)始，自上而下，自左至右搜索，它從根結(jié)點(diǎn)的左側(cè)開(kāi)始，自上而下，自左至右搜索，最后從根結(jié)點(diǎn)的右側(cè)向上出去。恰好搜索線途經(jīng)每個(gè)有效樹(shù)結(jié)點(diǎn)都是三次最后從根結(jié)點(diǎn)的右側(cè)向上出去。恰好搜索線途經(jīng)每個(gè)有效樹(shù)結(jié)點(diǎn)都是三次搜索線第一次經(jīng)過(guò)就訪問(wèn)的結(jié)點(diǎn)序列搜索線第一次經(jīng)過(guò)就訪問(wèn)的結(jié)點(diǎn)序列ABCDABCD，稱(chēng)先根遍歷；搜索線第二次經(jīng)過(guò)才，稱(chēng)先根遍歷；搜索線第二次經(jīng)過(guò)才訪問(wèn)的結(jié)點(diǎn)序列訪問(wèn)的結(jié)點(diǎn)序列BADCBADC，稱(chēng)中根遍歷

31、；搜索線第三次經(jīng)過(guò)才訪問(wèn)的序列，稱(chēng)中根遍歷；搜索線第三次經(jīng)過(guò)才訪問(wèn)的序列BDCA,BDCA,稱(chēng)稱(chēng)后根遍歷后根遍歷A,B,C,D A,B,C,D 先根（前序）遍歷先根（前序）遍歷B,A,D,C B,A,D,C 中根（序）遍歷中根（序）遍歷B,D,C,A B,D,C,A 后根（序）遍歷后根（序）遍歷大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)二叉樹(shù)選擇不同的存儲(chǔ)結(jié)構(gòu)，遍歷算法的程序代碼會(huì)二叉樹(shù)選擇不同的存儲(chǔ)結(jié)構(gòu)，遍歷算法的程序代碼會(huì)有所不同。這里確定用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，樹(shù)中有所不同。這里確定用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，樹(shù)中結(jié)點(diǎn)的結(jié)構(gòu)定義為：結(jié)點(diǎn)的結(jié)構(gòu)定義為：typedef struct node ElemType

32、data; struct node *lch,*rch; Bnode;大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)若根為空則結(jié)束；否則：若根為空則結(jié)束；否則：（1 1）訪問(wèn)根結(jié)點(diǎn)；）訪問(wèn)根結(jié)點(diǎn)；（2 2）按先根次序遍歷左子樹(shù)；）按先根次序遍歷左子樹(shù)；（3 3）按先根次序遍歷右子樹(shù)。）按先根次序遍歷右子樹(shù)。6.3.1 先根遍歷先根遍歷（先根遍歷（TLRTLR）遞歸算法為：）遞歸算法為：Void preorder(Bnode *p) if(p!=NULL) printf(“%6c”,p-data); preorder(p-lch); preorder(p-rch); /* preorder */此處假設(shè)此處假設(shè)El

33、emTypeElemType為為charchar型型大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)ABCDA B C D p p訪問(wèn)訪問(wèn)A遍歷左子樹(shù)遍歷左子樹(shù)遍歷右子樹(shù)遍歷右子樹(shù)返回返回訪問(wèn)訪問(wèn)B遍歷左子樹(shù)遍歷左子樹(shù)遍歷右子樹(shù)遍歷右子樹(shù)返回返回訪問(wèn)訪問(wèn)C遍歷左子樹(shù)遍歷左子樹(shù)遍歷右子樹(shù)遍歷右子樹(shù)返回返回訪問(wèn)訪問(wèn)D遍歷左子樹(shù)遍歷左子樹(shù)遍歷右子樹(shù)遍歷右子樹(shù)返回返回根為根為NULLNULL返回返回根為根為NULLNULL返回返回根為根為NULLNULL返回返回根為根為NULLNULL返回返回根為根為NULLNULL返回返回大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)若根為空則結(jié)束；否則：若根為空則結(jié)束；否則：（1 1）按中根次序遍歷左子樹(shù)

34、；）按中根次序遍歷左子樹(shù)；（2 2）訪問(wèn)根結(jié)點(diǎn)；）訪問(wèn)根結(jié)點(diǎn)；（3 3）按中根次序遍歷右子樹(shù)。）按中根次序遍歷右子樹(shù)。6.3.2 中根遍歷中根遍歷（中根遍歷（LTRLTR）與先根遍歷相似，只是在根不空時(shí)將算法的第一）與先根遍歷相似，只是在根不空時(shí)將算法的第一步與第二步次序?qū)Q而已，即：步與第二步次序?qū)Q而已，即：Void inorder(Bnode *p) if(p!=NULL) inorder(p-lch); printf(“%6c”,p-data); inorder(p-rch); /* inorder */此處假設(shè)此處假設(shè)ElemTypeElemType為為charchar型型實(shí)現(xiàn)算法的

35、代碼也是在先根實(shí)現(xiàn)算法的代碼也是在先根算法基礎(chǔ)上稍做改動(dòng)，即：算法基礎(chǔ)上稍做改動(dòng)，即：遞歸算法簡(jiǎn)練但執(zhí)行效率較低，遞歸算法簡(jiǎn)練但執(zhí)行效率較低，而且有些高級(jí)也不支持遞歸調(diào)而且有些高級(jí)也不支持遞歸調(diào)用，作為程序設(shè)計(jì)能力的訓(xùn)練，用，作為程序設(shè)計(jì)能力的訓(xùn)練，有必要學(xué)習(xí)非遞歸算法。有必要學(xué)習(xí)非遞歸算法。大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)s s01234中根遍歷的非遞歸算法如下：中根遍歷的非遞歸算法如下：voide inorderz(Bnode *p) /* 棧棧s是是Bnode *s10 */ q=p; top =0; /*棧頂指針棧頂指針*/ bool =1; /* bool=1表示棧不空表示棧不空*/ pr

36、intf(“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); /*訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn)*/ q=q-rch; while(bool); printf(“n”); /* inorderz */ABCDA B C D p ptopC AB Dtoptop大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)6.3.3 后根遍歷若根為空則結(jié)束；否則：若根為空則結(jié)束；否則：（1 1）按后根次序遍歷左子樹(shù)；）按后根次序遍歷左子樹(shù)；（2 2）按后根

37、次序遍歷右子樹(shù)；）按后根次序遍歷右子樹(shù)；（3 3）訪問(wèn)根結(jié)點(diǎn)。）訪問(wèn)根結(jié)點(diǎn)。Void postorder(Bnode *p) if(p!=NULL) postorder(p-lch); postorder(p-rch); printf(“%6c”,p-data); /* postorder */ 后根遍歷的非遞歸算法較為復(fù)雜，它需要兩個(gè)棧，第一個(gè)棧后根遍歷的非遞歸算法較為復(fù)雜，它需要兩個(gè)棧，第一個(gè)棧的用途與中根遍歷相同，第二個(gè)棧用來(lái)經(jīng)過(guò)某根結(jié)點(diǎn)的次數(shù)。兩的用途與中根遍歷相同，第二個(gè)棧用來(lái)經(jīng)過(guò)某根結(jié)點(diǎn)的次數(shù)。兩個(gè)棧的數(shù)據(jù)類(lèi)型為：個(gè)棧的數(shù)據(jù)類(lèi)型為：Bnode Bnode * *s10;int s2

38、20;s10;int s220; 具體算法程序留給同學(xué)們課外閱讀。（具體算法程序留給同學(xué)們課外閱讀。（P111P111）大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)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ì)并訪問(wèn)出隊(duì)并訪問(wèn)*/ if(p-lch!=NULL) rear+; qrear=p-lch; /*若左孩子不空，進(jìn)隊(duì)若左

39、孩子不空，進(jìn)隊(duì)*/ if(p-rch!=NULL) rear+; qrear=p-rch;/*若左孩子不空，進(jìn)隊(duì)若左孩子不空，進(jìn)隊(duì)*/ /* levelorder */6.3.4 按層遍歷二叉樹(shù)AB C D FJ K BACDJFKpFR109876543210qRRRRRRRFFFFFFFabcdfjkpppppp大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)（1 1）初始化設(shè)置一個(gè)隊(duì)列；）初始化設(shè)置一個(gè)隊(duì)列；（2 2）把根結(jié)點(diǎn)指針入隊(duì)列；）把根結(jié)點(diǎn)指針入隊(duì)列；（3 3）當(dāng)隊(duì)列非空時(shí)，循環(huán)執(zhí)行步驟）當(dāng)隊(duì)列非空時(shí)，循環(huán)執(zhí)行步驟（3.a）到步驟到步驟（3.c）（3.a3.a）出隊(duì)列取得一個(gè)結(jié)點(diǎn)指針，訪問(wèn)該結(jié)點(diǎn)；）出

40、隊(duì)列取得一個(gè)結(jié)點(diǎn)指針，訪問(wèn)該結(jié)點(diǎn)；（3.b3.b）若該結(jié)點(diǎn)的左子樹(shù)非空，則將該結(jié)點(diǎn)的左子樹(shù)指）若該結(jié)點(diǎn)的左子樹(shù)非空，則將該結(jié)點(diǎn)的左子樹(shù)指針入隊(duì)列；針入隊(duì)列；（3.c3.c）若該結(jié)點(diǎn)的右子樹(shù)非空，則將該結(jié)點(diǎn)的右子樹(shù)指）若該結(jié)點(diǎn)的右子樹(shù)非空，則將該結(jié)點(diǎn)的右子樹(shù)指針入隊(duì)列；針入隊(duì)列；（4 4）結(jié)束。）結(jié)束。按層遍歷二叉樹(shù)的算法可以用語(yǔ)言描述如下：大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù) 按層遍歷二叉樹(shù)被稱(chēng)為按層遍歷二叉樹(shù)被稱(chēng)為層序遍歷層序遍歷。層序遍歷的要求是：。層序遍歷的要求是：按二叉樹(shù)的層序次序（即按二叉樹(shù)的層序次序（即從根結(jié)點(diǎn)層至葉結(jié)點(diǎn)層從根結(jié)點(diǎn)層至葉結(jié)點(diǎn)層），同一），同一層中按層中按先左子樹(shù)再右子樹(shù)先左子

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

42、學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)把二叉樹(shù)逆時(shí)針旋轉(zhuǎn)把二叉樹(shù)逆時(shí)針旋轉(zhuǎn)900C，按照二叉樹(shù)的凹入表示法打印按照二叉樹(shù)的凹入表示法打印二叉樹(shù)?？砂汛撕瘮?shù)設(shè)計(jì)成遞二叉樹(shù)?？砂汛撕瘮?shù)設(shè)計(jì)成遞歸函數(shù)。由于把二叉樹(shù)逆時(shí)針歸函數(shù)。由于把二叉樹(shù)逆時(shí)針旋轉(zhuǎn)旋轉(zhuǎn)900C后，在屏幕上方的首后，在屏幕上方的首先是右子樹(shù)，然后是根結(jié)點(diǎn)，先是右子樹(shù)，然后是根結(jié)點(diǎn)，最后是左子樹(shù)，所以最后是左子樹(shù)，所以打印二叉打印二叉樹(shù)算法是一種特殊的中序遍歷樹(shù)算法是一種特殊的中序遍歷算法。算法。6.3.5 二叉樹(shù)遍歷的應(yīng)用1 1 打印二叉樹(shù)打印二叉樹(shù)void PrintBiTree(Bnode *bt, int n) int i; if(bt =

43、 NULL) return; PrintBiTree(bt-rightChild, n+1); for(i = 0; i 0) printf(-); printf(%cn, bt-data); PrintBiTree(bt-leftChild, n+1);大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)在二叉樹(shù)中查找數(shù)據(jù)元素操作在二叉樹(shù)中查找數(shù)據(jù)元素操作的要求是：在的要求是：在bt為根結(jié)點(diǎn)指針的二為根結(jié)點(diǎn)指針的二叉樹(shù)中查找數(shù)據(jù)元素叉樹(shù)中查找數(shù)據(jù)元素x，若查找到，若查找到數(shù)據(jù)元素?cái)?shù)據(jù)元素x時(shí)返回該結(jié)點(diǎn)的指針；時(shí)返回該結(jié)點(diǎn)的指針；若查找不到數(shù)據(jù)元素若查找不到數(shù)據(jù)元素x時(shí)返回空指時(shí)返回空指針。針。在二叉樹(shù)在二叉樹(shù)bt中查

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

45、de *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;大學(xué)數(shù)據(jù)結(jié)構(gòu)6.樹(shù)和二叉樹(shù)6.4 線索二叉樹(shù) 線索二叉樹(shù)是另一種分步遍歷二叉樹(shù)的方法。它線索二叉樹(shù)是另一種分步遍歷二叉樹(shù)的方法。它既可以從前向后既可以從前向后分步遍歷二叉樹(shù)，分步遍歷二叉樹(shù)，又可以從后向前又可以從后向前分步遍歷二叉樹(shù)。分步遍歷二叉樹(shù)。 當(dāng)按某種規(guī)則遍歷二叉樹(shù)時(shí)，保存遍歷時(shí)得到的結(jié)點(diǎn)的后繼結(jié)點(diǎn)當(dāng)按某種規(guī)則遍歷二叉樹(shù)時(shí)，保存遍歷時(shí)得到的結(jié)點(diǎn)的后繼結(jié)點(diǎn)信息和前驅(qū)結(jié)點(diǎn)信息的最常用的方法是建立線索二叉樹(shù)。信息和前驅(qū)結(jié)點(diǎn)信息的最常用的方法是建立線索二叉樹(shù)。 對(duì)二叉鏈表存儲(chǔ)結(jié)構(gòu)的二叉樹(shù)分析可知，在有對(duì)二叉鏈表存儲(chǔ)結(jié)構(gòu)的二叉樹(shù)分析可知