1、數(shù)據(jù)構(gòu)造數(shù)據(jù)構(gòu)造A 第第5章章 樹第第5章章 樹樹7、并查集和等價(jià)關(guān)系、并查集和等價(jià)關(guān)系5.1 樹的根本概念樹的根本概念5.1.1 樹的定義層次構(gòu)造的數(shù)據(jù)在現(xiàn)實(shí)自然界中大量存在。層次構(gòu)造的數(shù)據(jù)在現(xiàn)實(shí)自然界中大量存在。國家、省、市、縣和區(qū)。國家、省、市、縣和區(qū)。書的章節(jié)、回目。書的章節(jié)、回目。上級(jí)和下級(jí)。上級(jí)和下級(jí)。整體和部分。整體和部分。祖先和后裔。祖先和后裔。5.1 樹的根本概念樹的根本概念5.1.1 樹的定義層次構(gòu)造的數(shù)據(jù)在現(xiàn)實(shí)自然界中大量存在。層次構(gòu)造的數(shù)據(jù)在現(xiàn)實(shí)自然界中大量存在。圖圖5-1 5-1 西歐言語譜系圖西歐言語譜系圖原始印歐語原始印歐語古意大利語古意大利語日耳曼語日耳曼語西日

2、耳曼語西日耳曼語拉丁語拉丁語西西班班牙牙語語法法語語意意大大利利語語希臘語希臘語北日耳曼語北日耳曼語冰冰島島語語瑞瑞典典語語挪挪威威語語英英語語荷荷蘭蘭語語德德語語古希臘語古希臘語5.1 樹的根本概念樹的根本概念5.1.1 樹的定義層次構(gòu)造的數(shù)據(jù)在現(xiàn)實(shí)自然界中大量存在。層次構(gòu)造的數(shù)據(jù)在現(xiàn)實(shí)自然界中大量存在。圖圖5-2 5-2 操作系統(tǒng)的目錄構(gòu)造操作系統(tǒng)的目錄構(gòu)造樹樹形形構(gòu)構(gòu)造造5.1 樹的根本概念樹的根本概念5.1.1 樹的定義2、樹的遞歸定義、樹的遞歸定義定義定義5.2 樹是包括樹是包括n個(gè)結(jié)點(diǎn)的有限非空集合個(gè)結(jié)點(diǎn)的有限非空集合T，其中一個(gè)，其中一個(gè)特定的結(jié)點(diǎn)特定的結(jié)點(diǎn)r稱為根，其他結(jié)點(diǎn)稱為

3、根，其他結(jié)點(diǎn)T-r劃分成劃分成mm0個(gè)互不相交的子集個(gè)互不相交的子集T1，T2，.Tm，其中，每個(gè)子集都是，其中，每個(gè)子集都是樹，被稱為樹根樹，被稱為樹根r的子樹。的子樹。定義定義5.2是遞歸的，用子樹來定義樹，也就是說，在樹的是遞歸的，用子樹來定義樹，也就是說，在樹的定義中援用了樹概念本身，所以，樹被稱為遞歸數(shù)據(jù)構(gòu)造。定義中援用了樹概念本身，所以，樹被稱為遞歸數(shù)據(jù)構(gòu)造。5.1 樹的根本概念樹的根本概念5.1.2 根本術(shù)語結(jié)點(diǎn)結(jié)點(diǎn)(node)(node)：樹中的元素。：樹中的元素。根結(jié)點(diǎn)和它的子樹根假設(shè)存在根結(jié)點(diǎn)和它的子樹根假設(shè)存在之間構(gòu)成一條邊。之間構(gòu)成一條邊。E E、A A、F F、B B

4、、G G、C C、D D、L L、J J、M M、N N均為結(jié)點(diǎn)。均為結(jié)點(diǎn)。EAFGBCDLJMN途徑途徑(path)(path)：從某個(gè)結(jié)點(diǎn)沿樹中的：從某個(gè)結(jié)點(diǎn)沿樹中的邊可到達(dá)另一個(gè)結(jié)點(diǎn)，那么稱這兩邊可到達(dá)另一個(gè)結(jié)點(diǎn)，那么稱這兩個(gè)結(jié)點(diǎn)之間存在一條途徑。個(gè)結(jié)點(diǎn)之間存在一條途徑。E E和和N N之間存在一條途徑。之間存在一條途徑。5.1 樹的根本概念樹的根本概念5.1.2 根本術(shù)語EAFGBCDLJMN結(jié)點(diǎn)結(jié)點(diǎn)G和和C互為兄弟否？互為兄弟否？雙親雙親(parent)(parent)：假設(shè)一個(gè)結(jié)點(diǎn)有子：假設(shè)一個(gè)結(jié)點(diǎn)有子樹，那么該結(jié)點(diǎn)稱為子樹根的雙親。樹，那么該結(jié)點(diǎn)稱為子樹根的雙親。A A、F F、

5、B B的雙親是的雙親是E E。C C、D D的雙親是的雙親是F F。孩子孩子(child)(child)：某結(jié)點(diǎn)子樹的根是：某結(jié)點(diǎn)子樹的根是該結(jié)點(diǎn)的孩子。該結(jié)點(diǎn)的孩子。E E有三個(gè)孩子：有三個(gè)孩子：A A、F F、B B。D D有一個(gè)孩子：有一個(gè)孩子：J J。兄弟兄弟(sibling)(sibling)：有一樣雙親的結(jié)：有一樣雙親的結(jié)點(diǎn)互為兄弟。點(diǎn)互為兄弟。A A、F F、B B互為兄弟，互為兄弟，C C和和D D互為兄弟。互為兄弟。5.1 樹的根本概念樹的根本概念5.1.2 根本術(shù)語EAFGBCDLJMN后裔后裔(decendent)(decendent)：一個(gè)結(jié)點(diǎn)的：一個(gè)結(jié)點(diǎn)的一切子樹上的

6、任何結(jié)點(diǎn)都是該結(jié)一切子樹上的任何結(jié)點(diǎn)都是該結(jié)點(diǎn)的后裔。點(diǎn)的后裔。結(jié)點(diǎn)結(jié)點(diǎn)C C的后裔為：的后裔為：L L、M M、N N。祖先祖先(ancestor)(ancestor)：從根結(jié)點(diǎn)到：從根結(jié)點(diǎn)到某個(gè)結(jié)點(diǎn)的途徑上的一切結(jié)點(diǎn)某個(gè)結(jié)點(diǎn)的途徑上的一切結(jié)點(diǎn)都是該結(jié)點(diǎn)的祖先。都是該結(jié)點(diǎn)的祖先。結(jié)點(diǎn)結(jié)點(diǎn)L L的祖先為：的祖先為：E E、F F、C C。5.1 樹的根本概念樹的根本概念5.1.2 根本術(shù)語EAFGBCDLJMN結(jié)點(diǎn)的度結(jié)點(diǎn)的度(degree)(degree)：結(jié)點(diǎn)擁有的子樹數(shù)。：結(jié)點(diǎn)擁有的子樹數(shù)。結(jié)點(diǎn)結(jié)點(diǎn)E E的度為的度為3 3，結(jié)點(diǎn)，結(jié)點(diǎn)F F的度為的度為2 2，結(jié)點(diǎn)結(jié)點(diǎn)A A的度為的度為1

7、 1，結(jié)點(diǎn)，結(jié)點(diǎn)G G的度為的度為0 0。葉子葉子(leaf)(leaf)：度為零的結(jié)點(diǎn)。：度為零的結(jié)點(diǎn)。B B、G G、J J、M M、N N均為葉子結(jié)點(diǎn)。均為葉子結(jié)點(diǎn)。分支結(jié)點(diǎn)分支結(jié)點(diǎn)(branch)(branch)：度不為零的結(jié)點(diǎn)。：度不為零的結(jié)點(diǎn)。E E、A A、F F、C C等為分支結(jié)點(diǎn)。等為分支結(jié)點(diǎn)。樹的度：樹中結(jié)點(diǎn)的最大的度。樹的度：樹中結(jié)點(diǎn)的最大的度。該樹的度為該樹的度為3 3。5.1 樹的根本概念樹的根本概念5.1.2 根本術(shù)語結(jié)點(diǎn)的層次：根結(jié)點(diǎn)的層次為結(jié)點(diǎn)的層次：根結(jié)點(diǎn)的層次為1 1，其他結(jié)點(diǎn)的層次等于其，其他結(jié)點(diǎn)的層次等于其雙親結(jié)點(diǎn)的層次加雙親結(jié)點(diǎn)的層次加1 1。結(jié)點(diǎn)結(jié)點(diǎn)

8、E E的層次為的層次為1 1。結(jié)點(diǎn)結(jié)點(diǎn)M M的層次為的層次為5 5。樹的高度：樹中結(jié)點(diǎn)的樹的高度：樹中結(jié)點(diǎn)的最大層次。最大層次。樹中結(jié)點(diǎn)的最大樹中結(jié)點(diǎn)的最大層次為層次為5 5。樹的高度為樹的高度為5 5。12345EAFGBCDLJMN5.1 樹的根本概念樹的根本概念5.1.2 根本術(shù)語AG無序樹：假設(shè)樹中結(jié)點(diǎn)的各子樹之間的次序是不重要的，無序樹：假設(shè)樹中結(jié)點(diǎn)的各子樹之間的次序是不重要的，可以交換位置。可以交換位置。以下是同一棵無序樹：以下是同一棵無序樹：將左邊樹中一切結(jié)點(diǎn)的子樹互換次序就是右邊的樹。將左邊樹中一切結(jié)點(diǎn)的子樹互換次序就是右邊的樹。EAFGBCDLJMNEFBCDLJNM5.1

9、樹的根本概念樹的根本概念5.1.2 根本術(shù)語有序樹：假設(shè)樹中結(jié)點(diǎn)的各棵子樹看成是從左到右有次序有序樹：假設(shè)樹中結(jié)點(diǎn)的各棵子樹看成是從左到右有次序的，那么稱該樹為有序樹。的，那么稱該樹為有序樹。有序樹的各子樹從左到右為第一棵子樹、第二棵，有序樹的各子樹從左到右為第一棵子樹、第二棵，以下是二棵有序樹：以下是二棵有序樹：AGEAFGBCDLJMNEFBCDLJNM5.1 樹的根本概念樹的根本概念5.1.2 根本術(shù)語森林：是樹的集合。森林：是樹的集合。0 0個(gè)或多個(gè)不相交的樹組成森林。個(gè)或多個(gè)不相交的樹組成森林。果園或有序森林：有序樹的有序集合。果園或有序森林：有序樹的有序集合。假設(shè)將樹中的根去掉，那

10、么得到根的子樹組成的森假設(shè)將樹中的根去掉，那么得到根的子樹組成的森林。林。 BEAGFCDLJMNE 假設(shè)添加一個(gè)結(jié)點(diǎn)，將森林中各樹的根作為新增結(jié)點(diǎn)假設(shè)添加一個(gè)結(jié)點(diǎn)，將森林中各樹的根作為新增結(jié)點(diǎn)的孩子，那么森林即成為樹。的孩子，那么森林即成為樹。 5.2 二叉樹二叉樹二叉樹是非常重要的樹形數(shù)二叉樹是非常重要的樹形數(shù)據(jù)構(gòu)造。據(jù)構(gòu)造。很多從實(shí)踐問題中籠統(tǒng)出來很多從實(shí)踐問題中籠統(tǒng)出來的數(shù)據(jù)是二叉樹形的；以后的數(shù)據(jù)是二叉樹形的；以后我們將看到恣意樹或森林可我們將看到恣意樹或森林可方便地轉(zhuǎn)換成二叉樹，從而方便地轉(zhuǎn)換成二叉樹，從而為普通樹和森林的存儲(chǔ)和處為普通樹和森林的存儲(chǔ)和處置提供了有效方法。置提供了有

11、效方法。5.2 二叉樹二叉樹5.1.2 根本術(shù)語 方法二：改良構(gòu)造，組織成樹形構(gòu)造。比較次數(shù)不會(huì)超方法二：改良構(gòu)造，組織成樹形構(gòu)造。比較次數(shù)不會(huì)超越樹高，提高了效率。越樹高，提高了效率。二叉樹運(yùn)用實(shí)例二叉樹運(yùn)用實(shí)例 設(shè)有序表為設(shè)有序表為21，25，28，33，36，45，如今，如今要在表中查找元素要在表中查找元素33。282136253345方法一：順序搜索。效率低，平均比較一半的元素。方法一：順序搜索。效率低，平均比較一半的元素。21，25，28，33，36，45比較了比較了4 4次！次！比較了比較了3 3次！次！33335.2 二叉樹二叉樹5.2.1 二叉樹的定義定義定義5.35.3 二叉

12、樹二叉樹(binary tree)(binary tree)是結(jié)點(diǎn)的有限集合，是結(jié)點(diǎn)的有限集合，該集合或者為空集，或者是由一個(gè)根和兩個(gè)互不該集合或者為空集，或者是由一個(gè)根和兩個(gè)互不相交的、稱為該根的左子樹和右子樹的二叉樹組相交的、稱為該根的左子樹和右子樹的二叉樹組成。成。 上述定義闡明二叉樹可以為空集，因此，二上述定義闡明二叉樹可以為空集，因此，二叉樹有叉樹有5 5種根本形狀。種根本形狀。(a) (b) (c) (d) (e)(a) (b) (c) (d) (e)圖圖5-4 5-4 二叉樹的五種根本形狀二叉樹的五種根本形狀5.2 二叉樹二叉樹5.2.1 二叉樹的定義樹與二叉樹的區(qū)別：樹與二叉樹

13、的區(qū)別： 樹不能是空樹，即至少有一個(gè)根結(jié)點(diǎn)。而二樹不能是空樹，即至少有一個(gè)根結(jié)點(diǎn)。而二叉樹可以是空樹。叉樹可以是空樹。 普通樹的子樹之間是無序的。而二叉樹中結(jié)普通樹的子樹之間是無序的。而二叉樹中結(jié)點(diǎn)的子樹要區(qū)分左、右子樹，即使只需一棵子點(diǎn)的子樹要區(qū)分左、右子樹，即使只需一棵子樹。樹。 樹中每個(gè)節(jié)點(diǎn)可有樹中每個(gè)節(jié)點(diǎn)可有0 0棵或假設(shè)干子樹。而二棵或假設(shè)干子樹。而二叉樹的每個(gè)節(jié)點(diǎn)最多只能有叉樹的每個(gè)節(jié)點(diǎn)最多只能有2 2棵子樹。棵子樹。EFEF5.2 二叉樹二叉樹5.2.2 二叉樹的性質(zhì)性質(zhì)性質(zhì)5.1 5.1 二叉樹的第二叉樹的第i(i1)i(i1)層上至多有層上至多有2i-1 2i-1 個(gè)結(jié)點(diǎn)。個(gè)

14、結(jié)點(diǎn)。 可用歸納法證明之。當(dāng)可用歸納法證明之。當(dāng)i=1i=1時(shí)，二叉樹至多只需一個(gè)結(jié)時(shí)，二叉樹至多只需一個(gè)結(jié)點(diǎn)，結(jié)論成立。點(diǎn)，結(jié)論成立。 設(shè)當(dāng)設(shè)當(dāng)i=ki=k時(shí)結(jié)論成立，即二叉樹上至多有時(shí)結(jié)論成立，即二叉樹上至多有2k-1 2k-1 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) 當(dāng)當(dāng)i=k+1i=k+1時(shí)，時(shí)， 每個(gè)結(jié)點(diǎn)最多只需兩個(gè)孩子，每個(gè)結(jié)點(diǎn)最多只需兩個(gè)孩子， 第第k+1k+1層上至多有層上至多有2 2* *2k1 =2k2k1 =2k個(gè)結(jié)點(diǎn)，性質(zhì)成立。個(gè)結(jié)點(diǎn)，性質(zhì)成立。5.2 二叉樹二叉樹5.2.2 二叉樹的性質(zhì)性質(zhì)性質(zhì)5.2 5.2 高度為高度為h h的二叉樹上至多有的二叉樹上至多有2h12h1個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。當(dāng)當(dāng)h

15、=0h=0時(shí)，二叉樹為空二叉樹。時(shí)，二叉樹為空二叉樹。當(dāng)當(dāng)h0h0時(shí)，利用性質(zhì)時(shí)，利用性質(zhì)1 1，高度為，高度為h h的二叉樹中結(jié)點(diǎn)的總數(shù)最多為：的二叉樹中結(jié)點(diǎn)的總數(shù)最多為：1012112(222.2)21hihhi12311.1nnaaaaaa補(bǔ)充：等比數(shù)列的求和公式是11 (1)2ii i性質(zhì) 二叉樹的第層上至多有個(gè)結(jié)點(diǎn)。5.2 二叉樹二叉樹5.2.2 二叉樹的性質(zhì)5.2 二叉樹二叉樹5.2.2 二叉樹的性質(zhì)性質(zhì)性質(zhì)5.3 5.3 包含包含n n個(gè)元素的二叉樹的高度至少為個(gè)元素的二叉樹的高度至少為 log2 log2 (n+1)(n+1) 根據(jù)性質(zhì)根據(jù)性質(zhì)2 2，高度為，高度為h h的二叉

16、樹最多有的二叉樹最多有2h 12h 1個(gè)結(jié)點(diǎn)性質(zhì)個(gè)結(jié)點(diǎn)性質(zhì)2 2，因此，因此n n2h 1, 2h 1, 那么有那么有h h log2(n+1) log2(n+1)。由于由于h h是整數(shù)，所以是整數(shù)，所以h h log2 (n+1)log2 (n+1)。5.2 二叉樹二叉樹5.2.2 二叉樹的性質(zhì)性質(zhì)性質(zhì)5.4 5.4 恣意一棵二叉樹中，假設(shè)葉結(jié)點(diǎn)的個(gè)數(shù)為恣意一棵二叉樹中，假設(shè)葉結(jié)點(diǎn)的個(gè)數(shù)為n0n0，度，度為為2 2的結(jié)點(diǎn)的個(gè)數(shù)為的結(jié)點(diǎn)的個(gè)數(shù)為n2n2，那么必有，那么必有n0=n2+1n0=n2+1。設(shè)二叉樹的度為設(shè)二叉樹的度為1 1的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n1n1，樹中結(jié)點(diǎn)總數(shù)為，樹中結(jié)點(diǎn)總數(shù)為

17、n n，那么那么n=n0+n1+n2 n=n0+n1+n2 二叉樹中只需度為二叉樹中只需度為0 0、1 1、2 2三種類型的結(jié)點(diǎn)三種類型的結(jié)點(diǎn)設(shè)分支數(shù)為設(shè)分支數(shù)為B B，n n個(gè)結(jié)點(diǎn)的二叉樹，除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)的二叉樹，除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有一個(gè)分支進(jìn)入，那么都有一個(gè)分支進(jìn)入，那么B=n-1B=n-1；分支是由度為；分支是由度為1 1或者度為或者度為2 2的射出的，又有的射出的，又有B=2n2+n1B=2n2+n1；那么有：那么有：n-1=2n2+n1 n-1=2n2+n1 n=2n2+n1+1n=2n2+n1+1由由 可得到：可得到：n0+n1+n2=2n2+n1+1 n0+n

18、1+n2=2n2+n1+1 n0+n2=2n2 +1 n0+n2=2n2 +1即即n2=n0-1n2=n0-1。5.2 二叉樹二叉樹5.2.2 二叉樹的性質(zhì)定義定義5.4 5.4 高度為高度為h h的二叉樹恰好有的二叉樹恰好有2h 12h 1個(gè)結(jié)點(diǎn)時(shí)稱為滿個(gè)結(jié)點(diǎn)時(shí)稱為滿二叉樹。二叉樹。0123456789101112 1314(a)滿二叉樹滿二叉樹0123456789(b)完全二叉樹完全二叉樹圖圖5.6 幾種特殊的二叉樹幾種特殊的二叉樹9定義定義5.5 一棵二叉樹中，只需最下面兩層結(jié)點(diǎn)的度可以小一棵二叉樹中，只需最下面兩層結(jié)點(diǎn)的度可以小于于2，并且最下一層的葉結(jié)點(diǎn)集中在靠左的假設(shè)干位置上。，并

19、且最下一層的葉結(jié)點(diǎn)集中在靠左的假設(shè)干位置上。這樣的二叉樹稱為完全二叉樹。這樣的二叉樹稱為完全二叉樹。5.2 二叉樹二叉樹5.2.2 二叉樹的性質(zhì)定義定義5.6 5.6 擴(kuò)展二叉樹也稱擴(kuò)展二叉樹也稱2-2-樹，其中除葉子結(jié)點(diǎn)外，其樹，其中除葉子結(jié)點(diǎn)外，其他結(jié)點(diǎn)都必需有兩個(gè)孩子。他結(jié)點(diǎn)都必需有兩個(gè)孩子。5323301112131735895.2 二叉樹二叉樹5.2.2 二叉樹的性質(zhì)：完全二叉樹的性質(zhì)性質(zhì)性質(zhì)5.5 5.5 具有具有n n個(gè)結(jié)點(diǎn)的完全二叉樹的高度為個(gè)結(jié)點(diǎn)的完全二叉樹的高度為log2 (n+1)log2 (n+1)。證明：根據(jù)性質(zhì)證明：根據(jù)性質(zhì)2 2高度為高度為h-1h-1的完全二叉樹

20、結(jié)點(diǎn)個(gè)數(shù)最多為的完全二叉樹結(jié)點(diǎn)個(gè)數(shù)最多為2h-1-12h-1-1高度為高度為h h的完全二叉樹結(jié)點(diǎn)個(gè)數(shù)最多為的完全二叉樹結(jié)點(diǎn)個(gè)數(shù)最多為2h-12h-1高度為高度為h h的完全二叉樹結(jié)點(diǎn)個(gè)數(shù)取值范圍的完全二叉樹結(jié)點(diǎn)個(gè)數(shù)取值范圍2h-1 , 2h)2h-1 , 2h)結(jié)論：結(jié)論： n n個(gè)結(jié)點(diǎn)的二叉樹中完全二叉樹最矮，高度為個(gè)結(jié)點(diǎn)的二叉樹中完全二叉樹最矮，高度為log2 (n+1)log2 (n+1)。 n n個(gè)結(jié)點(diǎn)的完全二叉樹和二叉斷定樹的高度是一樣的個(gè)結(jié)點(diǎn)的完全二叉樹和二叉斷定樹的高度是一樣的2log1n 2h-1n2h-1n2h2hlog2nlog2nh log2n+1h log2n+1hh

21、是整數(shù)是整數(shù) h= h=2log1n 性質(zhì)性質(zhì)2 2 高度為高度為h h的二叉樹上至多有的二叉樹上至多有2h 12h 1個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。2h-1 - 12h-1 - 1 n 2h 1 n 2h 1l o g 2 ( n + 1 ) hl o g 2 ( n + 1 ) h log2(n+1)+1log2(n+1)+1h = h = log2 (n+1)log2 (n+1)5.2 二叉樹二叉樹5.2.2 二叉樹的性質(zhì)：完全二叉樹的性質(zhì)性質(zhì)性質(zhì)5.6 5.6 假定對(duì)一棵有假定對(duì)一棵有n n個(gè)結(jié)點(diǎn)的完全二叉樹中的結(jié)點(diǎn)，按從上個(gè)結(jié)點(diǎn)的完全二叉樹中的結(jié)點(diǎn)，按從上到下、從左到右的順序，從到下、從左到右的順

22、序，從0 0到到n-1n-1編號(hào)見圖編號(hào)見圖5.6(c)5.6(c)，設(shè)樹中，設(shè)樹中一個(gè)結(jié)點(diǎn)的序號(hào)為一個(gè)結(jié)點(diǎn)的序號(hào)為i i，0 0i in n ，那么有以下關(guān)系成立：，那么有以下關(guān)系成立：1 1當(dāng)當(dāng)i=0i=0時(shí)，該結(jié)點(diǎn)為二叉樹的根。時(shí)，該結(jié)點(diǎn)為二叉樹的根。2 2假設(shè)假設(shè)i0i0，那么該結(jié)點(diǎn)的雙親的序號(hào)為，那么該結(jié)點(diǎn)的雙親的序號(hào)為(i-1)/2(i-1)/23 3假設(shè)假設(shè)2i+12i+1n n，那么該結(jié)點(diǎn)的左孩子的序號(hào)為，那么該結(jié)點(diǎn)的左孩子的序號(hào)為2i+12i+1，否那么，否那么該結(jié)點(diǎn)無左孩子。該結(jié)點(diǎn)無左孩子。4 4假設(shè)假設(shè)2i+22i+2n n，那么該結(jié)點(diǎn)的右孩子的序號(hào)為，那么該結(jié)點(diǎn)的右孩子

23、的序號(hào)為2i+22i+2，否那么，否那么該結(jié)點(diǎn)無右孩子。該結(jié)點(diǎn)無右孩子。(a)(a)滿二叉樹滿二叉樹0123456789 10 11 12 13 140123456789(b)(b)完全二叉樹完全二叉樹5.2 二叉樹二叉樹5.2.3 二叉樹ADTADT BinaryTree Data: 二叉樹是結(jié)點(diǎn)的有限集合，該集合或者為空集，或者是由一個(gè)根二叉樹是結(jié)點(diǎn)的有限集合，該集合或者為空集，或者是由一個(gè)根和兩個(gè)互不相交的稱為該根的左子樹和右子樹的二叉樹組成。和兩個(gè)互不相交的稱為該根的左子樹和右子樹的二叉樹組成。 Operations: Create()： 創(chuàng)建一棵空二叉樹。創(chuàng)建一棵空二叉樹。 Dest

24、roy(): 撤銷一棵二叉樹。撤銷一棵二叉樹。 IsEmpty()：假設(shè)二叉樹空，那么前往：假設(shè)二叉樹空，那么前往true，否那么前往，否那么前往false。 Clear(): 移去一切結(jié)點(diǎn)，成為空二叉樹。移去一切結(jié)點(diǎn)，成為空二叉樹。 Root(x)：取：取x為根結(jié)點(diǎn)；假設(shè)操作勝利，那么前往為根結(jié)點(diǎn)；假設(shè)操作勝利，那么前往true，否那么前往，否那么前往false MakeTree(x,left，right)：創(chuàng)建一棵二叉樹，：創(chuàng)建一棵二叉樹，x為根結(jié)點(diǎn)，為根結(jié)點(diǎn)，left為為 左子樹，左子樹，right為右子樹。為右子樹。 BreakTree(x ,left, right)：拆分二叉樹為三部

25、分，：拆分二叉樹為三部分，x為根的值，為根的值， left和和right分別為原樹的左右子樹分別為原樹的左右子樹 PreOrder： 運(yùn)用函數(shù)運(yùn)用函數(shù)Visit訪問結(jié)點(diǎn)，先序遍歷二叉樹。訪問結(jié)點(diǎn)，先序遍歷二叉樹。 InOrder： 運(yùn)用函數(shù)運(yùn)用函數(shù)Visit訪問結(jié)點(diǎn)，中序遍歷二叉樹。訪問結(jié)點(diǎn)，中序遍歷二叉樹。 PostOrder：運(yùn)用函數(shù)：運(yùn)用函數(shù)Visit訪問結(jié)點(diǎn)，后序遍歷二叉樹。訪問結(jié)點(diǎn)，后序遍歷二叉樹。 5.2 二叉樹二叉樹5.2.4 二叉樹的存儲(chǔ)表示1. 1. 完全二叉樹的順序表示完全二叉樹的順序表示 完全二叉樹中的結(jié)點(diǎn)可以按層次順序存儲(chǔ)在一片延完全二叉樹中的結(jié)點(diǎn)可以按層次順序存儲(chǔ)在一

26、片延續(xù)的存儲(chǔ)單元中。根結(jié)點(diǎn)保管在編號(hào)為續(xù)的存儲(chǔ)單元中。根結(jié)點(diǎn)保管在編號(hào)為0 0的位置上。的位置上。留意：普通的二叉樹不適宜用這種存儲(chǔ)構(gòu)造。留意：普通的二叉樹不適宜用這種存儲(chǔ)構(gòu)造。0 01 12 23 34 45 56 67 78 89 90 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 9圖圖6.5 6.5 圖圖6.4(b)6.4(b)完全二叉樹的順序表示完全二叉樹的順序表示0123456789圖圖6.4(b) 6.4(b) 完全二叉樹完全二叉樹5.2 二叉樹二叉樹5.2.4 二叉樹的存儲(chǔ)表示lChild element rChildlChild element rCh

27、ild一棵有一棵有n n個(gè)結(jié)點(diǎn)的二叉樹中，每個(gè)結(jié)點(diǎn)有個(gè)結(jié)點(diǎn)的二叉樹中，每個(gè)結(jié)點(diǎn)有2 2個(gè)指針域。個(gè)指針域。指針域有指針域有2n2n個(gè)。除了根結(jié)點(diǎn)外，其它結(jié)點(diǎn)均有一個(gè)指向它個(gè)。除了根結(jié)點(diǎn)外，其它結(jié)點(diǎn)均有一個(gè)指向它的指針，此項(xiàng)開支用掉的指針，此項(xiàng)開支用掉n-1n-1個(gè)指針域。個(gè)指針域。空指針域的數(shù)目為空指針域的數(shù)目為2n-(n-1)=n+12n-(n-1)=n+1。2. 2. 二叉樹的鏈接表示二叉樹的鏈接表示ABCDEFA AB B C C D D E E F F (a)(a)二叉樹二叉樹(b)(b)二叉樹的鏈接表示二叉樹的鏈接表示圖圖6-6 6-6 二叉樹的鏈接表示二叉樹的鏈接表示5.2 二叉樹

28、二叉樹5.2.4 二叉樹的存儲(chǔ)表示二叉樹的二叉鏈表構(gòu)造有利于從雙親到孩子方向的訪問，二叉樹的二叉鏈表構(gòu)造有利于從雙親到孩子方向的訪問，但從孩子無法反向訪問其父節(jié)點(diǎn)。但從孩子無法反向訪問其父節(jié)點(diǎn)。假設(shè)在二叉鏈表結(jié)點(diǎn)中添加一個(gè)假設(shè)在二叉鏈表結(jié)點(diǎn)中添加一個(gè)parent域，令它指向該結(jié)域，令它指向該結(jié)點(diǎn)的雙親結(jié)點(diǎn)，就可以實(shí)現(xiàn)從孩子到雙親，以及從雙親到點(diǎn)的雙親結(jié)點(diǎn)，就可以實(shí)現(xiàn)從孩子到雙親，以及從雙親到孩子的雙向鏈接構(gòu)造。孩子的雙向鏈接構(gòu)造。A AB B C C D D E E F F 5.2 二叉樹二叉樹5.2.5 二叉樹類templatestruct BTNode BTNode() lChild =

29、rChild = NULL; BTNode(const T& x) element =x; lChild = rChild = NULL; BTNode(const T& x, BTNode* l, BTNode* r) element = x; lChild = l; rChild = r; T element; BTNode *lChild, *rChild;程序程序5.1 二叉樹結(jié)點(diǎn)類二叉樹結(jié)點(diǎn)類5.2 二叉樹二叉樹5.2.5 二叉樹類templateclass BinaryTree public: BinaryTree()root = NULL; BinaryTree()Clear()

30、; bool IsEmpty()const; void Clear(); bool Root(T& x)const; void MakeTree(const T& e,BinaryTree& left,BinaryTree& right); void BreakTree(T& e,BinaryTree& left,BinaryTree& right); void PreOrder(void(*Visit)(T& x); void InOrder(void(*Visit)(T& x); void PostOrder(void(*Visit)(T& x); protected: BTNode* r

31、oot; private: int Size(BTNode* t); void Clear(BTNode* t); void PreOrder(void(*Visit)(T& x),BTNode* t); void InOrder(void(*Visit)(T& x), BTNode* t); void PostOrder(void(*Visit)(T& x), BTNode* t);程序程序5.2 二叉樹類二叉樹類5.2 二叉樹二叉樹5.2.6 實(shí)現(xiàn)二叉樹根本運(yùn)算本小節(jié)中，我們主要實(shí)現(xiàn)本小節(jié)中，我們主要實(shí)現(xiàn)MakeTree、BreakTree和和Root運(yùn)運(yùn)算，而將二叉樹遍歷算法留待下一小節(jié)

32、專門討論。算，而將二叉樹遍歷算法留待下一小節(jié)專門討論。Clear()函數(shù)釋放二叉鏈表中的一切結(jié)點(diǎn)，它需求經(jīng)過遍函數(shù)釋放二叉鏈表中的一切結(jié)點(diǎn)，它需求經(jīng)過遍歷二叉樹來實(shí)現(xiàn)。歷二叉樹來實(shí)現(xiàn)。5.2 二叉樹二叉樹5.2.6 實(shí)現(xiàn)二叉樹根本運(yùn)算程序程序5.3 部分二叉樹運(yùn)算部分二叉樹運(yùn)算templatebool BinaryTree:Root(T& x)const if(root) x = root-element; return true; else return false;ABCDEF5.2 二叉樹二叉樹5.2.6 實(shí)現(xiàn)二叉樹根本運(yùn)算程序程序5.3 部分二叉樹運(yùn)算部分二叉樹運(yùn)算templatevo

33、id BinaryTree:MakeTree(const T& x, BinaryTree& left,BinaryTree& right) if(root|&left=&right) return; root = new BTNode(x, left.root, right.root); left.root = right.root = NULL; DCEFBTNode(const T& x, BTNode* l,BTNode* r) element = x; lChild = l; rChild = r; A Aleft.rootright.root=NULL=NULL5.2 二叉樹二叉樹

34、5.2.6 實(shí)現(xiàn)二叉樹根本運(yùn)算程序程序5.3 部分二叉樹運(yùn)算部分二叉樹運(yùn)算 if(root|&left=&right) return; root = new BTNode(x, left.root, right.root); left.root = right.root = NULL;D C E F t3t2(1) t1.root != NULL;(2) &t2 = &t3t1.MakeTree(A, t2, t3);N P t1(1) t1的結(jié)點(diǎn)全部喪失的結(jié)點(diǎn)全部喪失?(2) t1左右子樹的結(jié)點(diǎn)是同左右子樹的結(jié)點(diǎn)是同一空間一空間?5.2 二叉樹二叉樹5.2.6 實(shí)現(xiàn)二叉樹根本運(yùn)算程序程序5.

35、3 部分二叉樹運(yùn)算部分二叉樹運(yùn)算templatetemplatevoid BinaryTree:BreakTree(T& x, void BinaryTree:BreakTree(T& x, BinaryTree&left,BinaryTree&right) BinaryTree&left,BinaryTree&right) if(!root|&left=&right|left.root|right.root) if(!root|&left=&right|left.root|right.root) return; return; x = root-element; x = root-eleme

36、nt; left.root = root-lChild; left.root = root-lChild; right.root = root-rChild; right.root = root-rChild; delete root; delete root; root = NULL; root = NULL; D DC CE EF FA Aleft.rootleft.rootright.rootright.rootroot=root=root5.2 二叉樹二叉樹5.2.6 實(shí)現(xiàn)二叉樹根本運(yùn)算int main(void) BinaryTreea, b, x, y, z; y.MakeTree

37、(E, a, b); z.MakeTree(F, a, b); x.MakeTree(C, y, z); y.MakeTree(D, a, b); z.MakeTree(B, y, x); z.BreakTree(e, y, x); return 0;程序程序5.4 main5.4 main函數(shù)函數(shù)一個(gè)測(cè)試程序一個(gè)測(cè)試程序a b x y zEyCxFzDyBz5.3 二叉樹的遍歷二叉樹的遍歷5.1.2 根本術(shù)語遍歷遍歷traversetraverse一個(gè)有限一個(gè)有限結(jié)點(diǎn)的集合，意味著對(duì)該集結(jié)點(diǎn)的集合，意味著對(duì)該集合中的每個(gè)結(jié)點(diǎn)訪問且僅訪合中的每個(gè)結(jié)點(diǎn)訪問且僅訪問一次。問一次。A AB BD D

38、C CE EF F二叉樹遍歷算法二叉樹遍歷算法: : (I) (I) 先左后右：先左后右：VLRVLR，LVRLVR，LRVLRV(II)(II)先右后左：先右后左：VRLVRL，RVLRVL，RLV-RLV-逆逆5.3 二叉樹的遍歷二叉樹的遍歷5.3.1 二叉樹遍歷算法 先序遍歷先序遍歷VLRVLR假設(shè)二叉樹為空，那么空操作；假設(shè)二叉樹為空，那么空操作；否那么否那么 訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； 先序遍歷左子樹；先序遍歷左子樹； 先序遍歷右子樹。先序遍歷右子樹。A AB BD DC CE EF F先序遍歷序列：先序遍歷序列： A B D C E F A B D C E F 先序遍歷序列：先序遍歷

39、序列： A B D G H E C F A B D G H E C F ttttttt= t= t=t=ttt=t=t=A AB BC CD DE EF FG GH H5.3 二叉樹的遍歷二叉樹的遍歷5.3.1 二叉樹遍歷算法(2) (2) 中序遍歷中序遍歷LVRLVR假設(shè)二叉樹為空，那么空操作；假設(shè)二叉樹為空，那么空操作；否那么否那么 中序遍歷左子樹；中序遍歷左子樹； 訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； 中序遍歷右子樹。中序遍歷右子樹。 中序遍歷序列：中序遍歷序列：B D A E C F B D A E C F A AB BD DC CE EF F中序遍歷中序遍歷A AB BC CD DE EF FG

40、 GH HI IJ JK K5.3 二叉樹的遍歷二叉樹的遍歷5.3.1 二叉樹遍歷算法(3)(3)后序遍歷后序遍歷 LRVLRV 假設(shè)二叉樹為空，那么空操作假設(shè)二叉樹為空，那么空操作； 否那么否那么 后序遍歷左子樹；后序遍歷左子樹； 后序遍歷右子樹；后序遍歷右子樹； 訪問根結(jié)點(diǎn)。訪問根結(jié)點(diǎn)。后序遍歷序列：后序遍歷序列：D B E F C A D B E F C A A AB BD DC CE EF F后序遍歷后序遍歷A AB BC CD DE EF FG GH HI IJ JK K層次遍歷層次遍歷A AB BC CD DE EF FG GH HI IJ JK K5.3 二叉樹的遍歷二叉樹的遍歷

41、5.3.2 二叉樹遍歷的遞歸算法 對(duì)于遍歷運(yùn)算，設(shè)計(jì)了一個(gè)面向用戶的公有成員函數(shù)對(duì)于遍歷運(yùn)算，設(shè)計(jì)了一個(gè)面向用戶的公有成員函數(shù)和一個(gè)詳細(xì)實(shí)現(xiàn)遍歷操作的遞歸私有成員函數(shù)，兩者共同和一個(gè)詳細(xì)實(shí)現(xiàn)遍歷操作的遞歸私有成員函數(shù)，兩者共同完成遍歷運(yùn)算的功能。完成遍歷運(yùn)算的功能。 公有成員函數(shù)：非遞歸函數(shù)，作為與用戶的接口。它調(diào)用公有成員函數(shù)：非遞歸函數(shù)，作為與用戶的接口。它調(diào)用私有的遞歸函數(shù)。私有的遞歸函數(shù)。 私有成員函數(shù)：遞歸函數(shù)，詳細(xì)實(shí)現(xiàn)遍歷操作。被公有成私有成員函數(shù)：遞歸函數(shù)，詳細(xì)實(shí)現(xiàn)遍歷操作。被公有成員函數(shù)調(diào)用。員函數(shù)調(diào)用。5.3 二叉樹的遍歷二叉樹的遍歷5.3.2 二叉樹遍歷的遞歸算法程序程序5

42、.5 訪問元素函數(shù)訪問元素函數(shù)templatevoid Visit(T& x) cout x t;程序程序5.6 先序遍歷先序遍歷templatevoid BinaryTree:PreOrder(void(*Visit)(T& x) PreOrder(Visit,root);templatevoid BinaryTree:PreOrder(void(*Visit)(T& x), BTNode* t) if(t) Visit(t-element); PreOrder(Visit, t-lChild); PreOrder(Visit, t-rChild); 5.3 二叉樹的遍歷二叉樹的遍歷5.3.

43、2 二叉樹遍歷的遞歸算法補(bǔ)充：中序遍歷補(bǔ)充：中序遍歷templatevoid BinaryTree:InOrder(void(*Visit)(T& x) InOrder(Visit,root);templatevoid BinaryTree:InOrder(void(*Visit)(T& x), BTNode* t) if(t) InOrder(Visit, t-lChild); Visit(t-element); InOrder(Visit, t-rChild); 5.3 二叉樹的遍歷二叉樹的遍歷5.3.2 二叉樹遍歷的遞歸算法補(bǔ)充：后序遍歷補(bǔ)充：后序遍歷templatevoid Binar

44、yTree:PostOrder(void(*Visit)(T& x) PostOrder(Visit,root);templatevoid BinaryTree:PostOrder(void(*Visit)(T& x), BTNode* t) if(t) PostOrder(Visit, t-lChild); PostOrder(Visit, t-rChild); Visit(t-element); 5.3 二叉樹的遍歷二叉樹的遍歷 顯然，二叉樹遍歷算法根本操作是訪問結(jié)點(diǎn)，不論按顯然，二叉樹遍歷算法根本操作是訪問結(jié)點(diǎn)，不論按何種次序遍歷，對(duì)含有何種次序遍歷，對(duì)含有n n個(gè)結(jié)點(diǎn)的二叉樹，其時(shí)間復(fù)

45、雜度均個(gè)結(jié)點(diǎn)的二叉樹，其時(shí)間復(fù)雜度均為為O(n)O(n)。5.3 二叉樹的遍歷二叉樹的遍歷關(guān)于三種遍歷算法：關(guān)于三種遍歷算法：1.1.給定一棵二叉樹，能寫出它的三種遍歷序列。給定一棵二叉樹，能寫出它的三種遍歷序列。2.2.給出二叉樹的先序遍歷序列和中序遍歷序列可以獨(dú)一確給出二叉樹的先序遍歷序列和中序遍歷序列可以獨(dú)一確 定一棵二叉樹。定一棵二叉樹。3.3.給出二叉樹的后序遍歷序列和中序遍歷序列可以獨(dú)一確給出二叉樹的后序遍歷序列和中序遍歷序列可以獨(dú)一確 定一棵二叉樹。定一棵二叉樹。4.4.當(dāng)當(dāng)n1n1時(shí)，給出二叉樹的先序遍歷序列和后序遍歷序列不時(shí)，給出二叉樹的先序遍歷序列和后序遍歷序列不 可以獨(dú)一

46、確定一棵二叉樹。可以獨(dú)一確定一棵二叉樹。例如：先序序列：例如：先序序列：ABAB，后序序列：，后序序列：BABAA AB BA AB B5.3 二叉樹的遍歷二叉樹的遍歷例例 知結(jié)點(diǎn)的先序序列和中序序列分別為：知結(jié)點(diǎn)的先序序列和中序序列分別為：先序序列先序序列 A B C D E F G中序序列中序序列 C B E D A F G那么可按上述分解求得整棵二叉樹那么可按上述分解求得整棵二叉樹,其構(gòu)造過程其構(gòu)造過程:(1) 由先序序列可知二叉樹的根為由先序序列可知二叉樹的根為A，A的左子樹的的左子樹的中序序列為中序序列為CBED，右子樹的中序序列為，右子樹的中序序列為FG。(2) 此外，此外，A的左

47、子樹的先序序列必為的左子樹的先序序列必為BCDE，右子，右子樹的前序序列為樹的前序序列為FG。(3) 類似地，可由左子樹的先序序列和中序序列構(gòu)類似地，可由左子樹的先序序列和中序序列構(gòu)造造A的左子樹，由右子樹的先序序列和中序序列構(gòu)的左子樹，由右子樹的先序序列和中序序列構(gòu)造造A的右子樹。的右子樹。5.3 二叉樹的遍歷二叉樹的遍歷5.3.3 二叉樹遍歷的運(yùn)用實(shí)例1.1.計(jì)算二叉樹的結(jié)點(diǎn)數(shù)計(jì)算二叉樹的結(jié)點(diǎn)數(shù) 程序程序5.7 5.7 求二叉樹的結(jié)點(diǎn)數(shù)求二叉樹的結(jié)點(diǎn)數(shù)templatetemplateint BinaryTree:Size() int BinaryTree:Size() return Siz

48、e(root); return Size(root); templatetemplateint BinaryTree:Size(BTNodeint BinaryTree:Size(BTNode* * t) t) if(!t) return 0; if(!t) return 0; return Size(t-lChild) + Size(t- return Size(t-lChild) + Size(t-rChild) + 1;rChild) + 1; 利用二叉樹遍歷思想可以處理許多二叉樹的運(yùn)用問題。利用二叉樹遍歷思想可以處理許多二叉樹的運(yùn)用問題。A AB BD DC CE EF F5.3 二叉

49、樹的遍歷二叉樹的遍歷5.3.3 二叉樹遍歷的運(yùn)用實(shí)例2.2.二叉樹復(fù)制二叉樹復(fù)制程序程序5.8 5.8 二叉樹復(fù)制二叉樹復(fù)制templatetemplateBTNodeBTNode* * BinaryTree:Copy(BTNode BinaryTree:Copy(BTNode* * t) t) if(!root) return NULL; if(!root) return NULL; BTNode BTNode* * q = new BTNode(t-element); q = new BTNode(t-element); q-lChild = Copy(t-lChild); q-lChil

50、d = Copy(t-lChild); q-rChild = Copy(t-rChild); q-rChild = Copy(t-rChild); return q; return q; 利用二叉樹遍歷思想可以處理許多二叉樹的運(yùn)用問題。利用二叉樹遍歷思想可以處理許多二叉樹的運(yùn)用問題。A AB BD DC CE EF Ft tA AB BD DC CE EF Fq q=5.3 二叉樹的遍歷二叉樹的遍歷5.3.3 二叉樹遍歷的運(yùn)用實(shí)例3.3.補(bǔ)充：刪除二叉樹補(bǔ)充：刪除二叉樹templatetemplatevoid BinaryTree:Clear(BTNodevoid BinaryTree:Cle

51、ar(BTNode* * t) t) if(t) if(t) Clear(t-lChild); Clear(t-lChild); Clear(t-rChild); Clear(t-rChild); cout deleteelement.endl; cout deleteelement.=C CK K=再看一例再看一例5.5 樹和森林樹和森林5.5.1 森林與二叉樹的轉(zhuǎn)換1. 1. 樹樹(Tree)(Tree)轉(zhuǎn)換為二叉樹轉(zhuǎn)換為二叉樹(BTree)(BTree)算法算法留意：留意： 左 孩 子 右 兄 弟 。左 孩 子 右 兄 弟 。 ( ( 樹樹 二 叉 樹二 叉 樹 ) ) 二 叉 樹 中

52、有 兩 個(gè) 結(jié) 點(diǎn)二 叉 樹 中 有 兩 個(gè) 結(jié) 點(diǎn) X X 和和 Y Y ， 且， 且 X X 是是 Y Y 的 雙 親的 雙 親 樹的根結(jié)點(diǎn)沒有兄弟，所以樹對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)沒樹的根結(jié)點(diǎn)沒有兄弟，所以樹對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)沒有右子樹有右子樹二叉樹中二叉樹中樹中樹中Y Y是是X X左左孩子孩子Y Y是是X X孩子孩子Y Y是是X X右右孩子孩子Y Y是是X X兄弟兄弟5.5 樹和森林樹和森林5.5.1 森林與二叉樹的轉(zhuǎn)換2.2.森林森林(Forest)(Forest)轉(zhuǎn)換成二叉樹轉(zhuǎn)換成二叉樹(BTree)(BTree) 可以將任何森林獨(dú)一地表示成一棵二叉樹。可以將任何森林獨(dú)一地表示成一棵二叉樹

53、。方法如下：方法如下：(1)(1)假設(shè)假設(shè)F F為空，那么為空，那么B B為空二叉樹為空二叉樹(2)(2)假設(shè)假設(shè)F F非空，那么非空，那么B B的根是的根是F F中第一棵子樹中第一棵子樹T1T1的根的根R1R1，B B的左子樹是的左子樹是T1T1的子樹森林的子樹森林T11T11，T12T12，T1mT1m，B B的右的右子樹是森林子樹是森林T2T2，TnTn所對(duì)應(yīng)的二叉樹所對(duì)應(yīng)的二叉樹 最后所構(gòu)成的二叉樹就是森林所對(duì)應(yīng)的二叉樹。最后所構(gòu)成的二叉樹就是森林所對(duì)應(yīng)的二叉樹。5.5 樹和森林樹和森林5.5.1 森林與二叉樹的轉(zhuǎn)換2.2.森林森林(Forest)(Forest)轉(zhuǎn)換成二叉樹轉(zhuǎn)換成二叉

54、樹(BTree)(BTree)A AB BC CK KD DE EF FG GH HJ JA AB BC CK KD DE EH HF FJ JG GA AD DE EH HF FJ JG GB BC CK K5.5 樹和森林樹和森林5.5.1 森林與二叉樹的轉(zhuǎn)換3.3.二叉樹轉(zhuǎn)換成森林二叉樹轉(zhuǎn)換成森林(BF)(BF)A AB BC CK KD DE EF FG GH HJ JA AD DE EH HF FJ JG GB BC CK K1.1. 連線連線2.2. 去線去線3.3. 整形整形5.5 樹和森林樹和森林5.5.1 森林與二叉樹的轉(zhuǎn)換3.3.二叉樹轉(zhuǎn)換成森林二叉樹轉(zhuǎn)換成森林(BF)(B

55、F)一棵二叉樹一棵二叉樹B B轉(zhuǎn)換成的森林中有多少棵樹？轉(zhuǎn)換成的森林中有多少棵樹？ 一 棵 二 叉 樹一 棵 二 叉 樹轉(zhuǎn)化成的森林中轉(zhuǎn)化成的森林中所具有的樹的數(shù)所具有的樹的數(shù)目，等于二叉樹目，等于二叉樹從根結(jié)點(diǎn)開場(chǎng)沿從根結(jié)點(diǎn)開場(chǎng)沿右鏈到第一個(gè)沒右鏈到第一個(gè)沒有右孩子的結(jié)點(diǎn)有右孩子的結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)數(shù)所經(jīng)過的結(jié)點(diǎn)數(shù)目。目。A AB BE EC CD DF FG GH HI IJ J經(jīng)過經(jīng)過3個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，故森林中故森林中3棵樹棵樹5.5 樹和森林樹和森林5.5.1 森林與二叉樹的轉(zhuǎn)換3.3.二叉樹轉(zhuǎn)換成森林二叉樹轉(zhuǎn)換成森林(BF)(BF)A AB BC CD DE EF FG GH HI I

56、J JA AB BC CD DE EF FG GH HI IJ J5.5 樹和森林樹和森林5.5.2 樹和森林的存儲(chǔ)表示1. 1. 多重鏈表表示法多重鏈表表示法其中其中m m是樹的度。每個(gè)結(jié)點(diǎn)的指針域個(gè)數(shù)均為是樹的度。每個(gè)結(jié)點(diǎn)的指針域個(gè)數(shù)均為m m，故又，故又稱為等長(zhǎng)的多重鏈表。稱為等長(zhǎng)的多重鏈表。 優(yōu)點(diǎn)：處置簡(jiǎn)單。優(yōu)點(diǎn)：處置簡(jiǎn)單。缺陷：空指針域多，有浪費(fèi)。缺陷：空指針域多，有浪費(fèi)。 設(shè)樹中有設(shè)樹中有n n個(gè)結(jié)點(diǎn)，總共有個(gè)結(jié)點(diǎn)，總共有n n* *m m個(gè)指針域，其中，個(gè)指針域，其中，只需只需n-1n-1個(gè)非空指針域，故空指針域個(gè)數(shù)為：個(gè)非空指針域，故空指針域個(gè)數(shù)為： n n* *m-(n-1)

57、=n(m-1)+1m-(n-1)=n(m-1)+1 element child1 child2 childm5.5 樹和森林樹和森林5.5.2 樹和森林的存儲(chǔ)表示2. 2. 孩子兄弟表示法孩子兄弟表示法 孩子兄弟孩子兄弟( (左子左子/ /右兄弟右兄弟) )表示法本質(zhì)上就是樹所對(duì)應(yīng)的表示法本質(zhì)上就是樹所對(duì)應(yīng)的二叉樹的二叉鏈表表示法。其每個(gè)結(jié)點(diǎn)為：二叉樹的二叉鏈表表示法。其每個(gè)結(jié)點(diǎn)為：leftChild element rightSiblingD DE EF FG GH HJ JD DE EF FG GH HJ J J J G G F F H H E E D D 5.5 樹和森林樹和森林5.5.

58、2 樹和森林的存儲(chǔ)表示3. 3. 雙親表示法雙親表示法 每個(gè)結(jié)點(diǎn)有兩個(gè)域：每個(gè)結(jié)點(diǎn)有兩個(gè)域：elementelement和和parentparent。parentparent域?yàn)橛驗(yàn)橹赶蛟摻Y(jié)點(diǎn)的雙親結(jié)點(diǎn)的下標(biāo)。指向該結(jié)點(diǎn)的雙親結(jié)點(diǎn)的下標(biāo)。 可以對(duì)樹中結(jié)點(diǎn)按自上而下、自左向右可以對(duì)樹中結(jié)點(diǎn)按自上而下、自左向右( (按層次按層次) )的次的次序順序存儲(chǔ)起來。序順序存儲(chǔ)起來。思索：如何查找結(jié)點(diǎn)的雙親和孩子？思索：如何查找結(jié)點(diǎn)的雙親和孩子？012345DEFGHJ-1 00012element parent順序存儲(chǔ)的順序存儲(chǔ)的雙親表示法雙親表示法D DE EF FG GH HJ J雙親表示法雙親表示法

59、5.5 樹和森林樹和森林5.5.2 樹和森林的存儲(chǔ)表示4. 4. 三重鏈表表示法三重鏈表表示法優(yōu)點(diǎn)：可以很方便地得到節(jié)點(diǎn)的雙親和孩子信息。優(yōu)點(diǎn)：可以很方便地得到節(jié)點(diǎn)的雙親和孩子信息。leftChild element rightSibling parentD DE EF FG GH HJ J J J G G F F H H D D E E5.5 樹和森林樹和森林5.5.2 樹和森林的存儲(chǔ)表示5. 5. 帶右鏈的先序表示法帶右鏈的先序表示法 數(shù)據(jù)元素有三個(gè)數(shù)據(jù)項(xiàng)，數(shù)據(jù)元素有三個(gè)數(shù)據(jù)項(xiàng)，element, lTag, siblingelement, lTag, sibling。 sibling si

60、bling 指向結(jié)點(diǎn)的兄弟指向結(jié)點(diǎn)的兄弟 lTag lTag為為0 0表示有孩子，孩子存于相鄰單元表示有孩子，孩子存于相鄰單元 lTag lTag為為1 1表示無孩子表示無孩子 數(shù)據(jù)元素按對(duì)應(yīng)二叉樹的先序遍歷的順序存儲(chǔ)結(jié)點(diǎn)。數(shù)據(jù)元素按對(duì)應(yīng)二叉樹的先序遍歷的順序存儲(chǔ)結(jié)點(diǎn)。5.5 樹和森林樹和森林5.5.2 樹和森林的存儲(chǔ)表示5. 5. 帶右鏈的先序表示法帶右鏈的先序表示法5.5 樹和森林樹和森林5.5.3 樹和森林的遍歷 1按深度方向遍歷 對(duì)森林的深度遍歷與二叉樹類似，根據(jù)樹的遞歸定義，可以有兩種遍歷次序：先序遍歷和中序遍歷。森林森林(F)對(duì)應(yīng)對(duì)應(yīng)二叉樹二叉樹(B)先序遍歷先序遍歷等價(jià)于等價(jià)于先