09級(jí)使用數(shù)據(jù)結(jié)構(gòu)第6章

1、第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)返回主目錄返回主目錄第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù) 學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo)領(lǐng)會(huì)樹(shù)和二叉樹(shù)的類型定義，理解樹(shù)和二叉領(lǐng)會(huì)樹(shù)和二叉樹(shù)的類型定義，理解樹(shù)和二叉樹(shù)的結(jié)構(gòu)差別樹(shù)的結(jié)構(gòu)差別熟記二叉樹(shù)的主要特性，并掌握它們的證明熟記二叉樹(shù)的主要特性，并掌握它們的證明方法方法熟練掌握二叉樹(shù)的各種遍歷算法，并能靈活熟練掌握二叉樹(shù)的各種遍歷算法，并能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其它操作運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其它操作理解二叉樹(shù)的線索化過(guò)程以及在中序線索化理解二叉樹(shù)的線索化過(guò)程以及在中序線索化樹(shù)上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法樹(shù)上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法熟練掌握二叉樹(shù)和樹(shù)的各

2、種存儲(chǔ)結(jié)構(gòu)及其建熟練掌握二叉樹(shù)和樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其建立的算法立的算法學(xué)會(huì)編寫(xiě)實(shí)現(xiàn)樹(shù)的各種操作的算法學(xué)會(huì)編寫(xiě)實(shí)現(xiàn)樹(shù)的各種操作的算法了解最優(yōu)樹(shù)的特性，掌握建立最優(yōu)樹(shù)和赫夫了解最優(yōu)樹(shù)的特性，掌握建立最優(yōu)樹(shù)和赫夫曼編碼的方法。曼編碼的方法。本章說(shuō)明本章說(shuō)明第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)本章說(shuō)明本章說(shuō)明 重點(diǎn)和難點(diǎn)重點(diǎn)和難點(diǎn)二叉樹(shù)和樹(shù)的遍歷及其應(yīng)用是本章的學(xué)習(xí)二叉樹(shù)和樹(shù)的遍歷及其應(yīng)用是本章的學(xué)習(xí)重點(diǎn)，而編寫(xiě)實(shí)現(xiàn)二叉樹(shù)和樹(shù)的各種操作的遞歸重點(diǎn)，而編寫(xiě)實(shí)現(xiàn)二叉樹(shù)和樹(shù)的各種操作的遞歸算法也恰是本章的難點(diǎn)所在。算法也恰是本章的難點(diǎn)所在。 知識(shí)點(diǎn)知識(shí)點(diǎn)樹(shù)的類型定義、二叉樹(shù)的類型定義、二叉樹(shù)的類型定義、二

3、叉樹(shù)的類型定義、二叉樹(shù)的存儲(chǔ)表示、二叉樹(shù)的遍歷以及其它操作的實(shí)樹(shù)的存儲(chǔ)表示、二叉樹(shù)的遍歷以及其它操作的實(shí)現(xiàn)、線索二叉樹(shù)、樹(shù)和森林的存儲(chǔ)表示、樹(shù)和森現(xiàn)、線索二叉樹(shù)、樹(shù)和森林的存儲(chǔ)表示、樹(shù)和森林的遍歷以及其它操作的實(shí)現(xiàn)、最優(yōu)樹(shù)和赫夫曼林的遍歷以及其它操作的實(shí)現(xiàn)、最優(yōu)樹(shù)和赫夫曼編碼編碼 學(xué)習(xí)指南學(xué)習(xí)指南本章是整個(gè)課程的第二個(gè)學(xué)習(xí)重點(diǎn)，也是本章是整個(gè)課程的第二個(gè)學(xué)習(xí)重點(diǎn)，也是整個(gè)課程中的一大難點(diǎn)。在本章的學(xué)習(xí)過(guò)程中主整個(gè)課程中的一大難點(diǎn)。在本章的學(xué)習(xí)過(guò)程中主要應(yīng)該學(xué)會(huì)如何根據(jù)二叉樹(shù)和樹(shù)的結(jié)構(gòu)及其操作要應(yīng)該學(xué)會(huì)如何根據(jù)二叉樹(shù)和樹(shù)的結(jié)構(gòu)及其操作的遞歸定義編寫(xiě)遞歸算法。的遞歸定義編寫(xiě)遞歸算法。第第 六六 章

4、章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.1 樹(shù)的定義和基本術(shù)語(yǔ)樹(shù)的定義和基本術(shù)語(yǔ) 樹(shù)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支樹(shù)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)關(guān)系定義的層次結(jié)構(gòu)1、樹(shù)的定義、樹(shù)的定義 定義：樹(shù)定義：樹(shù)(tree)是是n(n0)個(gè)結(jié)點(diǎn)的有限集個(gè)結(jié)點(diǎn)的有限集T，其中：，其中：有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹(shù)的根有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹(shù)的根(root)當(dāng)當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為時(shí)，其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的個(gè)互不相交的有限集有限集T1,T2,Tm，其中每一個(gè)集合本身又是，其中每一個(gè)集合本身又是一棵樹(shù)，稱為根的子樹(shù)一棵樹(shù)，稱為根的子樹(shù)(subtree)特點(diǎn)：特點(diǎn)：樹(shù)

5、中至少有一個(gè)結(jié)點(diǎn)樹(shù)中至少有一個(gè)結(jié)點(diǎn)根根樹(shù)中各子樹(shù)是互不相交的集合樹(shù)中各子樹(shù)是互不相交的集合第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.1 樹(shù)的定義和基本術(shù)語(yǔ)樹(shù)的定義和基本術(shù)語(yǔ)A只有根結(jié)點(diǎn)的樹(shù)只有根結(jié)點(diǎn)的樹(shù)ABCDEFGHIJKLM有子樹(shù)的樹(shù)有子樹(shù)的樹(shù)根根子樹(shù)子樹(shù)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)ADT Tree 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 D： 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R： 基本操作基本操作 P：InitTree(&T);DestroyTree(&T);CreateTree(&T,definition);ClearTree(&T);2、樹(shù)的抽象數(shù)據(jù)類型的定義、樹(shù)的抽象數(shù)據(jù)類型的定義P1186.1 樹(shù)的定義和

6、基本術(shù)語(yǔ)樹(shù)的定義和基本術(shù)語(yǔ)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)形表示法：自然界倒長(zhǎng)的樹(shù)樹(shù)形表示法：自然界倒長(zhǎng)的樹(shù)(Knuth開(kāi)初用正開(kāi)初用正長(zhǎng)的樹(shù)表示長(zhǎng)的樹(shù)表示)文氏表示法：用嵌套集合表示文氏表示法：用嵌套集合表示(a)嵌套括號(hào)表示法：廣義表表示法嵌套括號(hào)表示法：廣義表表示法凹入表示法：類似書(shū)目凹入表示法：類似書(shū)目3、樹(shù)的表示方法、樹(shù)的表示方法6.1 樹(shù)的定義和基本術(shù)語(yǔ)樹(shù)的定義和基本術(shù)語(yǔ)K LEADJIMHGCBF(a)ACDBEKLFGHMIJ(c)(b)(A(B(E(K,L),F),C(G),D(H(M),I,J)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)4、 樹(shù)的術(shù)語(yǔ)樹(shù)的術(shù)語(yǔ)6.1 樹(shù)的

7、定義和基本術(shù)語(yǔ)樹(shù)的定義和基本術(shù)語(yǔ)結(jié)點(diǎn)結(jié)點(diǎn)(node)表示樹(shù)中的元素，包括數(shù)據(jù)項(xiàng)及若表示樹(shù)中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹(shù)的分支干指向其子樹(shù)的分支結(jié)點(diǎn)的度結(jié)點(diǎn)的度(degree)結(jié)點(diǎn)擁有的子樹(shù)數(shù)結(jié)點(diǎn)擁有的子樹(shù)數(shù)葉子葉子(leaf)度為度為0的結(jié)點(diǎn)的結(jié)點(diǎn)孩子孩子(child)結(jié)點(diǎn)子樹(shù)的根稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)子樹(shù)的根稱為該結(jié)點(diǎn)的孩子雙親雙親(parents)孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的的兄弟兄弟(sibling)同一雙親的孩子同一雙親的孩子樹(shù)的度樹(shù)的度一棵樹(shù)中最大的結(jié)點(diǎn)度數(shù)一棵樹(shù)中最大的結(jié)點(diǎn)度數(shù)結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次(level)從根結(jié)點(diǎn)算起，根為第一層，從根結(jié)點(diǎn)算起，根

8、為第一層，它的孩子為第二層它的孩子為第二層第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)堂兄堂兄其父母為兄弟的結(jié)點(diǎn)互稱堂兄其父母為兄弟的結(jié)點(diǎn)互稱堂兄祖先祖先結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支上的結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)所有結(jié)點(diǎn)子孫子孫以某結(jié)點(diǎn)為根的子樹(shù)中的任一結(jié)點(diǎn)都稱為以某結(jié)點(diǎn)為根的子樹(shù)中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫該結(jié)點(diǎn)的子孫有序樹(shù)有序樹(shù)結(jié)點(diǎn)的子樹(shù)從左到右有順序，否則，稱結(jié)點(diǎn)的子樹(shù)從左到右有順序，否則，稱為無(wú)序樹(shù)為無(wú)序樹(shù)深度深度(depth)樹(shù)中結(jié)點(diǎn)的最大層次數(shù)樹(shù)中結(jié)點(diǎn)的最大層次數(shù)森林森林(forest)m(m0)棵互不相交的樹(shù)的集合棵互不相交的樹(shù)的集合6.1 樹(shù)的定義和基本術(shù)語(yǔ)樹(shù)

9、的定義和基本術(shù)語(yǔ)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.1 樹(shù)的定義和基本術(shù)語(yǔ)樹(shù)的定義和基本術(shù)語(yǔ)ABCDEFGHIJKLM結(jié)點(diǎn)結(jié)點(diǎn)A的度：的度：3結(jié)點(diǎn)結(jié)點(diǎn)B的度：的度：2結(jié)點(diǎn)結(jié)點(diǎn)M的度：的度：0葉子：葉子：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)結(jié)點(diǎn)A的孩子：的孩子：B，C，D結(jié)點(diǎn)結(jié)點(diǎn)B的孩子：的孩子：E，F(xiàn)結(jié)點(diǎn)結(jié)點(diǎn)I的雙親：的雙親：D結(jié)點(diǎn)結(jié)點(diǎn)L的雙親：的雙親：E結(jié)點(diǎn)結(jié)點(diǎn)B，C，D為兄弟為兄弟結(jié)點(diǎn)結(jié)點(diǎn)K，L為兄弟為兄弟樹(shù)的度：樹(shù)的度：3結(jié)點(diǎn)結(jié)點(diǎn)A的層次：的層次：1結(jié)點(diǎn)結(jié)點(diǎn)M的層次：的層次：4樹(shù)的深度：樹(shù)的深度：4結(jié)點(diǎn)結(jié)點(diǎn)F，G為堂兄弟為堂兄弟結(jié)點(diǎn)結(jié)點(diǎn)A是結(jié)點(diǎn)是結(jié)點(diǎn)F，G的祖先的祖先第第 六六 章章 樹(shù)

10、和二叉樹(shù)樹(shù)和二叉樹(shù)6.2 二二 叉叉 樹(shù)樹(shù)1、二叉樹(shù)定義、二叉樹(shù)定義定義：二叉樹(shù)是定義：二叉樹(shù)是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?shù)為空樹(shù)(n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹(shù)和右子樹(shù)的互不相交的二叉樹(shù)構(gòu)成為左子樹(shù)和右子樹(shù)的互不相交的二叉樹(shù)構(gòu)成特點(diǎn)特點(diǎn)每個(gè)結(jié)點(diǎn)至多有二棵子樹(shù)每個(gè)結(jié)點(diǎn)至多有二棵子樹(shù)(即不存在度大于即不存在度大于2的的結(jié)點(diǎn)結(jié)點(diǎn))二叉樹(shù)的子樹(shù)有左、右之分，且其次序不能任二叉樹(shù)的子樹(shù)有左、右之分，且其次序不能任意顛倒意顛倒基本形態(tài)基本形態(tài)A只有根結(jié)點(diǎn)只有根結(jié)點(diǎn)的二叉樹(shù)的二叉樹(shù) 空二叉樹(shù)空二叉樹(shù)AB右子樹(shù)為空右子樹(shù)為空AB左子樹(shù)為空

11、左子樹(shù)為空ABC左、右子樹(shù)左、右子樹(shù)均非空均非空第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)證明：用歸納法證明之證明：用歸納法證明之 i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，顯然，時(shí)，只有一個(gè)根結(jié)點(diǎn)，顯然，2i-1=20=1 是對(duì)的是對(duì)的 假設(shè)對(duì)所有假設(shè)對(duì)所有j, (1ji)命題成立，即第命題成立，即第j層層上上 至多有至多有2j-1個(gè)結(jié)點(diǎn)，可證明個(gè)結(jié)點(diǎn)，可證明j=i命題成立命題成立 那么，第那么，第i-1層至多有層至多有2i-2個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) 又二叉樹(shù)每個(gè)結(jié)點(diǎn)的度至多為又二叉樹(shù)每個(gè)結(jié)點(diǎn)的度至多為2 第第i層上最大結(jié)點(diǎn)數(shù)是第層上最大結(jié)點(diǎn)數(shù)是第i-1層的層的2倍，即倍，即 22i-2=2i-1 故命題得證故命題得證2

12、、二叉樹(shù)的性質(zhì)、二叉樹(shù)的性質(zhì)6.2 二二 叉叉 樹(shù)樹(shù))1(21 iii個(gè)個(gè)結(jié)結(jié)點(diǎn)點(diǎn)層層上上至至多多有有在在二二叉叉樹(shù)樹(shù)的的第第性質(zhì)性質(zhì)1：第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)性質(zhì)性質(zhì)2：深度為：深度為k的二叉樹(shù)至多有的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(k1)6.2 二二 叉叉 樹(shù)樹(shù)證明：由性質(zhì)證明：由性質(zhì)1，可得深度為，可得深度為k 的二叉樹(shù)最大結(jié)點(diǎn)數(shù)是的二叉樹(shù)最大結(jié)點(diǎn)數(shù)是122)(111kkikiii層的最大結(jié)點(diǎn)數(shù)第性質(zhì)性質(zhì)3：對(duì)任何一棵二叉樹(shù)：對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為，如果其終端結(jié)點(diǎn)數(shù)為n0，度為，度為2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n2，則，則n0=n2+1證明：設(shè)證明：設(shè)n1為二

13、叉樹(shù)為二叉樹(shù)T中度為中度為1的結(jié)點(diǎn)數(shù)的結(jié)點(diǎn)數(shù) 因?yàn)椋憾鏄?shù)中所有結(jié)點(diǎn)的度均小于或等于因?yàn)椋憾鏄?shù)中所有結(jié)點(diǎn)的度均小于或等于2 所以：其結(jié)點(diǎn)總數(shù)所以：其結(jié)點(diǎn)總數(shù)n=n0+n1+n2 又二叉樹(shù)中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都只有一又二叉樹(shù)中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都只有一 個(gè)分支進(jìn)入，設(shè)個(gè)分支進(jìn)入，設(shè)B為分支總數(shù)，則為分支總數(shù)，則n=B+1 又：分支由度為又：分支由度為1和度為和度為2的結(jié)點(diǎn)射出，的結(jié)點(diǎn)射出， B=n1+2n2 于是，于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)

14、點(diǎn)數(shù)完全二叉樹(shù)完全二叉樹(shù)定義：深度為定義：深度為k，有，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)當(dāng)且僅當(dāng)其個(gè)結(jié)點(diǎn)的二叉樹(shù)當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)從的滿二叉樹(shù)中編號(hào)從1至至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為特點(diǎn)特點(diǎn)葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)對(duì)任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為對(duì)任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為l，則其左分支下子孫的最大層次必為則其左分支下子孫的最大層次必為l 或或l+16.2 二二 叉叉 樹(shù)樹(shù)幾種特殊形式的二叉樹(shù)幾種特殊形式的二叉樹(shù)滿二叉樹(shù)滿二叉樹(shù)定義：定義：12個(gè)個(gè)結(jié)結(jié)點(diǎn)點(diǎn)的的二二叉叉樹(shù)樹(shù)

15、稱稱為為且且有有一一棵棵深深度度為為 kk第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.2 二二 叉叉 樹(shù)樹(shù)1231145891213671014151231145891267101234567123456思考：滿二叉樹(shù)與完全二叉樹(shù)的關(guān)系？思考：滿二叉樹(shù)與完全二叉樹(shù)的關(guān)系？第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)性質(zhì)性質(zhì)4：具有：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1 證明：設(shè)深度為證明：設(shè)深度為k，則由性質(zhì)，則由性質(zhì)2和完全二叉樹(shù)定義和完全二叉樹(shù)定義 (k-1層層)2k-1-1n2k-1(k層）或?qū)樱┗?k-1 n2k 于是于是k-1 log2nk 又又k是整數(shù)是

16、整數(shù) k=log2n+1性質(zhì)性質(zhì)5：對(duì)于一棵完全二叉樹(shù)，從上到下從左至右對(duì)結(jié)：對(duì)于一棵完全二叉樹(shù)，從上到下從左至右對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)點(diǎn)進(jìn)行編號(hào),根結(jié)點(diǎn)為根結(jié)點(diǎn)為1,則對(duì)任一結(jié)點(diǎn)則對(duì)任一結(jié)點(diǎn)i(1=in，則結(jié)點(diǎn)，則結(jié)點(diǎn)i無(wú)左子女，否則，其左子女為無(wú)左子女，否則，其左子女為2i如果如果2i+1n，則結(jié)點(diǎn)，則結(jié)點(diǎn)i無(wú)右子女，否則，其右子女為無(wú)右子女，否則，其右子女為2i+16.2 二二 叉叉 樹(shù)樹(shù)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)3、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)順序的存儲(chǔ)結(jié)構(gòu)順序的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)：按滿二叉樹(shù)的結(jié)點(diǎn)層次編號(hào)，依次存放二實(shí)現(xiàn)：按滿二叉樹(shù)的結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹(shù)中的數(shù)據(jù)元素叉樹(shù)中

17、的數(shù)據(jù)元素特點(diǎn)：特點(diǎn)：結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中浪費(fèi)空間，適于存滿二叉樹(shù)和完全二叉樹(shù)浪費(fèi)空間，適于存滿二叉樹(shù)和完全二叉樹(shù)abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 116.2 二二 叉叉 樹(shù)樹(shù)浪費(fèi)空間浪費(fèi)空間第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)二叉樹(shù)的順序存儲(chǔ)表示二叉樹(shù)的順序存儲(chǔ)表示 #define MAX_TREE_SIZE 100 Typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)號(hào)單元存儲(chǔ)根結(jié)點(diǎn) SqBiTree bt;缺點(diǎn)：按完全二叉樹(shù)形式存儲(chǔ)，

18、浪費(fèi)空間。缺點(diǎn)：按完全二叉樹(shù)形式存儲(chǔ)，浪費(fèi)空間。 例如，在最壞情況下，例如，在最壞情況下，n個(gè)結(jié)點(diǎn)的單枝樹(shù)，要占用個(gè)結(jié)點(diǎn)的單枝樹(shù)，要占用2n-1個(gè)元素的存儲(chǔ)空間。個(gè)元素的存儲(chǔ)空間。6.2 二二 叉叉 樹(shù)樹(shù)順序存儲(chǔ)結(jié)構(gòu)適用于滿二叉樹(shù)和完全二叉樹(shù)順序存儲(chǔ)結(jié)構(gòu)適用于滿二叉樹(shù)和完全二叉樹(shù)的存儲(chǔ)。的存儲(chǔ)。第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈表二叉鏈表表示表示typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree;lchild data rchild A

19、BCDEFG在在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域個(gè)空指針域 AB C D E F G6.2 二二 叉叉 樹(shù)樹(shù)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)三叉鏈表三叉鏈表表示表示typedef struct BiTNodeTElemType data;struct BiTNode *lchild, *rchild,*parent;BiTNode ,*Bitree;lchild data parent rchildABCDEFG A B C D E F G6.2 二二 叉叉 樹(shù)樹(shù)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 問(wèn)題

20、的提出問(wèn)題的提出 先左后右的遍歷算法先左后右的遍歷算法 算法的遞歸描述算法的遞歸描述 遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例1、遍歷二叉樹(shù)、遍歷二叉樹(shù) 算法的非遞歸描述算法的非遞歸描述第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù) 順著某一條搜索路徑巡訪二叉樹(shù)順著某一條搜索路徑巡訪二叉樹(shù)中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次。次，而且僅被訪問(wèn)一次。 問(wèn)題的提出問(wèn)題的提出“訪問(wèn)訪問(wèn)”的含義可以很廣，如：輸出結(jié)的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。點(diǎn)的信息等。6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二

21、叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) “遍歷遍歷”是任何類型均有的操作，是任何類型均有的操作，對(duì)線性結(jié)構(gòu)而言，只有一條搜索路對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。而二叉樹(shù)是非故不需要另加討論。而二叉樹(shù)是非線性結(jié)構(gòu)，線性結(jié)構(gòu)， 每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷即按什么樣的搜索則存在如何遍歷即按什么樣的搜索路徑進(jìn)行遍歷的問(wèn)題。路徑進(jìn)行遍歷的問(wèn)題。第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 對(duì)對(duì)“二叉樹(shù)二叉樹(shù)”而言，可以有三條搜索路而言，可以有三條搜索路徑：

22、徑：（1）先上后下的按層次遍歷；）先上后下的按層次遍歷；（2）先左（子樹(shù)）后右（子樹(shù)）的遍）先左（子樹(shù)）后右（子樹(shù)）的遍歷；歷；（3）先右（子樹(shù)）后左（子樹(shù)）的遍）先右（子樹(shù)）后左（子樹(shù)）的遍歷。歷。第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 先左后右的遍歷算法先左后右的遍歷算法先（根）序的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法后（根）序的遍歷算法根根左左子樹(shù)子樹(shù)右右子樹(shù)子樹(shù)根根根根根根根根根根訪問(wèn)根結(jié)點(diǎn)、遍歷左子樹(shù)、遍歷右子樹(shù)訪問(wèn)根結(jié)點(diǎn)、遍歷左子樹(shù)、遍歷右子樹(shù)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉

23、樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 若二叉樹(shù)為空樹(shù)，則空操作；否則，若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）訪問(wèn)根結(jié)點(diǎn)；）訪問(wèn)根結(jié)點(diǎn)；（2）先序遍歷左子樹(shù)；）先序遍歷左子樹(shù)；（3）先序遍歷右子樹(shù)。）先序遍歷右子樹(shù)。先（根）序的遍歷算法：先（根）序的遍歷算法：第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 若二叉樹(shù)為空樹(shù)，則空操作；否則，若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）中序遍歷左子樹(shù)；）中序遍歷左子樹(shù)；（2）訪問(wèn)根結(jié)點(diǎn)；）訪問(wèn)根結(jié)點(diǎn)；（3）中序遍歷右子樹(shù)。）中序遍歷右子樹(shù)。中（根）序的遍歷算法：中（根）序的遍歷算法：第第 六六

24、章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 若二叉樹(shù)為空樹(shù)，則空操作；否則，若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）后序遍歷左子樹(shù)；）后序遍歷左子樹(shù)；（2）后序遍歷右子樹(shù)；）后序遍歷右子樹(shù)；（3）訪問(wèn)根結(jié)點(diǎn)。）訪問(wèn)根結(jié)點(diǎn)。后（根）序的遍歷算法：后（根）序的遍歷算法：第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)ABCDEFGHK例如：例如：先序序列：先序序列：中序序列：中序序列：后序序列：后序序列：A B C D E F G H KB D C A E H G K FD C B H K G F E A第第 六六 章章

25、樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 算法的遞歸描述（算法的遞歸描述（6.1）第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)void preorder(BiTree *T) if (T) printf(%dt,T-data); preorder(T-lchild); preorder(T-rchild); 主程序主程序Pre( T )返回返回返回返回pre(T R);返回返回返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D

26、);pre(T L);DTCprintf(C);pre(T L);C返回返回T左是空返回左是空返回pre(T R);T左是空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回pre(T R);先序序列：先序序列：A B D C第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 算法的非遞歸描述算法的非遞歸描述 二叉樹(shù)表示表達(dá)式二叉樹(shù)表示表達(dá)式 基本思想基本思想 若表達(dá)式為數(shù)或簡(jiǎn)單變量，則相應(yīng)若表達(dá)式為數(shù)或簡(jiǎn)單變量，則相應(yīng)二叉樹(shù)只有根結(jié)點(diǎn)，其數(shù)據(jù)域存放表達(dá)二叉樹(shù)只有根結(jié)點(diǎn)，其數(shù)據(jù)域存放表達(dá)式信息；否則，表達(dá)式均可寫(xiě)成式信息；否

27、則，表達(dá)式均可寫(xiě)成（運(yùn)算符）（運(yùn)算符）形式，形式，其中，其中，“運(yùn)算符運(yùn)算符”可用二叉樹(shù)的根結(jié)點(diǎn)表可用二叉樹(shù)的根結(jié)點(diǎn)表示，示，“第一操作數(shù)第一操作數(shù)”用二叉樹(shù)的左子樹(shù)表用二叉樹(shù)的左子樹(shù)表示，示，“第二操作數(shù)第二操作數(shù)”用二叉樹(shù)的右子樹(shù)表用二叉樹(shù)的右子樹(shù)表示。操作數(shù)本身可以是表達(dá)式。示。操作數(shù)本身可以是表達(dá)式。第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)表達(dá)式表達(dá)式 = ( = (操作數(shù)操作數(shù)1)(1)(運(yùn)算符運(yùn)算符)()(操作數(shù)操作數(shù)2)2)運(yùn)算符運(yùn)算符操作數(shù)1操作數(shù)2第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和

28、線索二叉樹(shù)例如：例如： a+b a+b* *(c-d)-e/f (c-d)-e/f 的二叉樹(shù)表示。的二叉樹(shù)表示。abcef- -+* */d- -先序（前綴表達(dá)式）先序（前綴表達(dá)式）中序（中綴表達(dá)式）中序（中綴表達(dá)式）后序（后綴表達(dá)式）后序（后綴表達(dá)式）- + a- + a * * b -b -cd/efcd/efa+b*c-d-e/fabcd-*+ef/-第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)abc- -* *- -* *c cab b- -* *abc先序遍歷：先序遍歷：- * a b c第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷

29、二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)abc- -* *- -* *c cab b中序遍歷：中序遍歷： a * b - ca* *bc- -第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)abc- -* *- -* *c cab b后序遍歷：后序遍歷： a b * c -ab* *c c- -第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 二叉樹(shù)遍歷的非遞歸算法二叉樹(shù)遍歷的非遞歸算法6.2ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULL

30、ABCDEFGiP-AP-B訪問(wèn)：C(4)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)pABCDEFGiP-A訪問(wèn)：C B(5)ABCDEFGiP-AP-D訪問(wèn)：C Bp(6)ABCDEFGiP-AP-DP-E訪問(wèn)：C Bp(7)ABCDEFGiP-AP-D訪問(wèn)：C B Ep(8)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)ABCDEFGiP-AP-DP-G訪問(wèn)：C B EP=NULL(9)ABCDEFGiP-A訪問(wèn)：C B E G Dp(11)ABCDEFGiP-AP-F訪問(wèn)：C B E G Dp(1

31、2)ABCDEFGiP-AP-D訪問(wèn)：C B E Gp(10)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)ABCDEFGiP-A訪問(wèn)：C B E G D Fp=NULL(13)ABCDEFGi訪問(wèn)：C B E G D F Ap(14)ABCDEFGi訪問(wèn)：C B E G D F Ap=NULL(15)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例 統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù) 求二叉樹(shù)的深度求二叉樹(shù)的深

32、度 二叉樹(shù)表示表達(dá)式二叉樹(shù)表示表達(dá)式第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù) 算法基本思想算法基本思想: : 先序先序( (或中序或后序或中序或后序) )遍歷二叉樹(shù)，遍歷二叉樹(shù)，在遍歷過(guò)程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。在遍歷過(guò)程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。由此，需在遍歷算法中增添一個(gè)由此，需在遍歷算法中增添一個(gè)“計(jì)數(shù)計(jì)數(shù)”的參數(shù)，并將算法中的參數(shù)，并將算法中“訪問(wèn)結(jié)點(diǎn)訪問(wèn)結(jié)點(diǎn)”的操的操作改為作改為: :若是葉子，則計(jì)數(shù)器增若是葉子，則計(jì)數(shù)器增1 1。算法實(shí)現(xiàn)算法實(shí)現(xiàn)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉

33、樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)否則，整個(gè)二叉樹(shù)中的葉子結(jié)點(diǎn)個(gè)數(shù)等否則，整個(gè)二叉樹(shù)中的葉子結(jié)點(diǎn)個(gè)數(shù)等于其左子樹(shù)中的葉子結(jié)點(diǎn)個(gè)數(shù)和其右子于其左子樹(shù)中的葉子結(jié)點(diǎn)個(gè)數(shù)和其右子樹(shù)中的葉子結(jié)點(diǎn)個(gè)數(shù)之和。樹(shù)中的葉子結(jié)點(diǎn)個(gè)數(shù)之和。 另一種算法思想分析方法另一種算法思想分析方法: :若二叉樹(shù)為空，則葉子結(jié)點(diǎn)的個(gè)數(shù)為零若二叉樹(shù)為空，則葉子結(jié)點(diǎn)的個(gè)數(shù)為零; ;若二叉樹(shù)中只有一個(gè)若二叉樹(shù)中只有一個(gè)( (根根) )結(jié)點(diǎn)，則葉子結(jié)點(diǎn)，則葉子結(jié)點(diǎn)的個(gè)數(shù)為結(jié)點(diǎn)的個(gè)數(shù)為1;1;(后序遍歷后序遍歷)算法實(shí)現(xiàn)算法實(shí)現(xiàn)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)

34、求二叉樹(shù)的深度求二叉樹(shù)的深度算法基本思想算法基本思想: :若二叉樹(shù)為空樹(shù)，則深度為若二叉樹(shù)為空樹(shù)，則深度為0;0;否則，二叉樹(shù)的深度應(yīng)為其左、右子樹(shù)深否則，二叉樹(shù)的深度應(yīng)為其左、右子樹(shù)深度的最大值加度的最大值加1 1。由此，需先分別求得左、右子樹(shù)的深度。由此，需先分別求得左、右子樹(shù)的深度。 首先分析二叉樹(shù)的深度和它的左、右子樹(shù)深度之間的關(guān)系(后序遍歷后序遍歷)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)int Depth (BiTree T ) / 返回二叉樹(shù)的深度返回二叉樹(shù)的深度 if ( !T ) depthval = 0; else dept

35、hLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)也可以從另一角度去分析也可以從另一角度去分析: : 從二叉樹(shù)深度的定義還可知，二叉樹(shù)的從二叉樹(shù)深度的定義還可知，二叉樹(shù)的深度即為其葉子結(jié)點(diǎn)所在層次的最大值。深度即為其葉子結(jié)點(diǎn)所在層次的最大值。由此，可通過(guò)遍歷求得二叉樹(shù)中所有結(jié)點(diǎn)由此，

36、可通過(guò)遍歷求得二叉樹(shù)中所有結(jié)點(diǎn)的的“層次層次”，從中取其最大值。，從中取其最大值。算法中需引入一個(gè)計(jì)結(jié)點(diǎn)層次的參數(shù)。算法中需引入一個(gè)計(jì)結(jié)點(diǎn)層次的參數(shù)。 首先分析二叉樹(shù)的深度和結(jié)點(diǎn)的“層次”間的關(guān)系。第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)void Depth(BiTree T , int level, int &dval) if ( T ) if (leveldval) dval = level; Depth( T-lchild, level+1, dval ); Depth( T-rchild, level+1, dval ); / 調(diào)用之前

37、調(diào)用之前 level 的初值為的初值為 1。 / dval 的初值為的初值為 0.第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 不同的定義方法相應(yīng)有不同的存儲(chǔ)不同的定義方法相應(yīng)有不同的存儲(chǔ)結(jié)構(gòu)的建立算法結(jié)構(gòu)的建立算法第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 以字符串的形式以字符串的形式 “根根 左子樹(shù)左子樹(shù) 右子樹(shù)右子樹(shù)”定義一棵二叉樹(shù)（算法定義一棵二叉樹(shù)（算法6.4）例如例如: :A(B( ,C( , ),D( , )以字符串“A ”表示ABCD以空白字符

38、“ ”表示空樹(shù)空樹(shù)只含一個(gè)根結(jié)點(diǎn)只含一個(gè)根結(jié)點(diǎn)的二叉樹(shù)的二叉樹(shù)A以下列字符串表示第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)void CreateBiTree(BiTree &T) scanf(&ch); if (ch= ) T = NULL; else T =(BiTNode*) malloc(sizeof(BiTNode); T-data = ch; / 生成根結(jié)點(diǎn)生成根結(jié)點(diǎn) CreateBiTree(T-lchild); / 構(gòu)造左子樹(shù)構(gòu)造左子樹(shù) CreateBiTree(T-rchild); / 構(gòu)造右子樹(shù)構(gòu)造右子樹(shù) / CreateBiT

39、ree第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)A B C D A BCD上頁(yè)算法執(zhí)行過(guò)程舉例如下上頁(yè)算法執(zhí)行過(guò)程舉例如下: :ATBCD scanf(&ch); if (ch= ) T = NULL; else T = (BiTNode*) malloc(sizeof( BiTNode); T-data = ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); 第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 二叉樹(shù)的遍歷有許多重要性質(zhì)，現(xiàn)以例子二叉樹(shù)的

40、遍歷有許多重要性質(zhì)，現(xiàn)以例子加以說(shuō)明。加以說(shuō)明。例如：僅知二叉樹(shù)的先序序列例如：僅知二叉樹(shù)的先序序列“abcdefg” 不能唯不能唯一確定一棵二叉樹(shù)，如果同時(shí)已知二叉樹(shù)的中一確定一棵二叉樹(shù)，如果同時(shí)已知二叉樹(shù)的中序序列序序列“cbdaegf”，則會(huì)如何？，則會(huì)如何？二叉樹(shù)的先序序列二叉樹(shù)的中序序列左子樹(shù)左子樹(shù)左子樹(shù)左子樹(shù) 右子樹(shù)右子樹(shù)右子樹(shù)右子樹(shù)根根根根第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)a b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列中序序列6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)第第 六六 章章 樹(shù)和二叉樹(shù)

41、樹(shù)和二叉樹(shù)此例推論可知，二叉樹(shù)遍歷的重要性質(zhì)：此例推論可知，二叉樹(shù)遍歷的重要性質(zhì)： 若已知二叉樹(shù)的先序序列和中序序列，若已知二叉樹(shù)的先序序列和中序序列，可唯一確定一棵二叉樹(shù)；可唯一確定一棵二叉樹(shù)； 若已知二叉樹(shù)的后序序列和中序序列，若已知二叉樹(shù)的后序序列和中序序列，也可唯一確定一棵二叉樹(shù)。也可唯一確定一棵二叉樹(shù)。6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)2 2、線索二叉樹(shù)、線索二叉樹(shù) 線索二叉樹(shù)定義線索二叉樹(shù)定義 線索二叉樹(shù)的遍歷線索二叉樹(shù)的遍歷 中序遍歷二叉線索樹(shù)的算法中序遍歷二叉線索樹(shù)的算法

42、第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 二叉樹(shù)的遍歷本質(zhì)上是將一個(gè)復(fù)雜的非線性二叉樹(shù)的遍歷本質(zhì)上是將一個(gè)復(fù)雜的非線性結(jié)構(gòu)轉(zhuǎn)換為線性結(jié)構(gòu)，使每個(gè)結(jié)點(diǎn)都有了唯一前結(jié)構(gòu)轉(zhuǎn)換為線性結(jié)構(gòu)，使每個(gè)結(jié)點(diǎn)都有了唯一前驅(qū)和后繼（第一個(gè)結(jié)點(diǎn)無(wú)前驅(qū)，最后一個(gè)結(jié)點(diǎn)無(wú)驅(qū)和后繼（第一個(gè)結(jié)點(diǎn)無(wú)前驅(qū)，最后一個(gè)結(jié)點(diǎn)無(wú)后繼）。對(duì)于二叉樹(shù)的一個(gè)結(jié)點(diǎn)，查找其左、右后繼）。對(duì)于二叉樹(shù)的一個(gè)結(jié)點(diǎn)，查找其左、右孩子是方便的，其前驅(qū)后繼只有在遍歷中得到。孩子是方便的，其前驅(qū)后繼只有在遍歷中得到。為了容易找到前驅(qū)和后繼，有兩種方法：為了容易找到前驅(qū)和后繼，有兩種方法： 在結(jié)點(diǎn)結(jié)構(gòu)中增加向前和

43、向后的指針在結(jié)點(diǎn)結(jié)構(gòu)中增加向前和向后的指針fwdfwd和和bkdbkd，這種方法增加了存儲(chǔ)開(kāi)銷這種方法增加了存儲(chǔ)開(kāi)銷 利用二叉樹(shù)的空鏈指針。利用二叉樹(shù)的空鏈指針。 線索二叉樹(shù)定義線索二叉樹(shù)定義第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)v n n個(gè)結(jié)點(diǎn)的二叉鏈表有個(gè)結(jié)點(diǎn)的二叉鏈表有n+1n+1個(gè)空鏈域個(gè)空鏈域v證明：證明：v 因除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有一因除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有一指針射入。指針射入。v n n個(gè)結(jié)點(diǎn)便有個(gè)結(jié)點(diǎn)便有n-1n-1個(gè)指針，即有個(gè)指針，即有n-1n-1個(gè)非空鏈域。個(gè)非空鏈域。v 因有因有2n2n個(gè)鏈域個(gè)鏈域v 空鏈域個(gè)數(shù)為：空鏈域個(gè)數(shù)為：2n-(n-1)=n+12n-(

44、n-1)=n+16.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù) 為了節(jié)省存貯空間，我們可以利用這為了節(jié)省存貯空間，我們可以利用這些空鏈域來(lái)存放結(jié)點(diǎn)的前趨和后繼的信息。些空鏈域來(lái)存放結(jié)點(diǎn)的前趨和后繼的信息。為避免混淆，需在結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域：為避免混淆，需在結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域： lchildltagdatartagrchild( (特征位特征位) ) 0 lchild 0 lchild域指示結(jié)點(diǎn)的左孩子域指示結(jié)點(diǎn)的左孩子ltag= 1 lchildltag= 1 lchild域指示結(jié)點(diǎn)的前趨域指示結(jié)點(diǎn)的前趨 rtag= 0 rchildrtag=

45、0 rchild域指示結(jié)點(diǎn)的右孩子域指示結(jié)點(diǎn)的右孩子 1 rchild 1 rchild域指示結(jié)點(diǎn)的后繼域指示結(jié)點(diǎn)的后繼6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù) 線索鏈表：以上述結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉線索鏈表：以上述結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉鏈表鏈表 其中指向結(jié)點(diǎn)前趨和后繼的指針，其中指向結(jié)點(diǎn)前趨和后繼的指針，叫做線索叫做線索 線索二叉樹(shù)：加上線索的二叉樹(shù)線索二叉樹(shù)：加上線索的二叉樹(shù) 對(duì)二叉樹(shù)以某種次序遍歷使其變?yōu)閷?duì)二叉樹(shù)以某種次序遍歷使其變?yōu)榫€索二叉樹(shù)的過(guò)程叫做線索化。線索二叉樹(shù)的過(guò)程叫做線索化。例如：中序線索二叉樹(shù)例如：中序線索二叉樹(shù)作業(yè)：畫(huà)先序，后序

46、線索樹(shù)！作業(yè)：畫(huà)先序，后序線索樹(shù)！6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)abcef- -+* */d- -NILNIL中序線索二叉樹(shù)中序線索二叉樹(shù)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)0 01 10 0 - - 0 00 0 + + 0 00 0 / / 0 01 1 a a 1 10 0 * * 0 01 1 e e 1 11 1 b b 1 10 0 - - 0 01 1 c c 1 11 1 d d 1 11 1 f f 1 1thr

47、tbt中序線索鏈表中序線索鏈表頭結(jié)點(diǎn)：頭結(jié)點(diǎn)：lt=0, lc指向根結(jié)點(diǎn)指向根結(jié)點(diǎn)rt=1, rc指向遍歷序列中最后一個(gè)結(jié)點(diǎn)指向遍歷序列中最后一個(gè)結(jié)點(diǎn)遍歷序列中第一個(gè)結(jié)點(diǎn)的遍歷序列中第一個(gè)結(jié)點(diǎn)的lc域和最后域和最后一個(gè)結(jié)點(diǎn)的一個(gè)結(jié)點(diǎn)的rc域都指向頭結(jié)點(diǎn)域都指向頭結(jié)點(diǎn)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù) 只要先找到序列中的第一個(gè)結(jié)點(diǎn)，依次找只要先找到序列中的第一個(gè)結(jié)點(diǎn)，依次找結(jié)點(diǎn)的后繼直到其后繼為空為止。結(jié)點(diǎn)的后繼直到其后繼為空為止。6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 線索二叉樹(shù)的遍歷線索二叉樹(shù)的遍歷 在中序線索樹(shù)中找結(jié)點(diǎn)的后繼：在中序線索樹(shù)中找結(jié)點(diǎn)的后繼： (1) (1)若

48、結(jié)點(diǎn)的若結(jié)點(diǎn)的rtagrtag為為1 1（葉子），則其后繼為（葉子），則其后繼為線索線索rchildrchild所指結(jié)點(diǎn)所指結(jié)點(diǎn)（2 2）（否則）若結(jié)點(diǎn)的）（否則）若結(jié)點(diǎn)的rtagrtag為為0 0（非葉子），（非葉子），則其后繼為則其后繼為“從其右孩子沿著左鏈找到從其右孩子沿著左鏈找到ltagltag為為1 1的那個(gè)結(jié)點(diǎn)的那個(gè)結(jié)點(diǎn)” (” (即右子樹(shù)最左下的結(jié)點(diǎn)）即右子樹(shù)最左下的結(jié)點(diǎn)）第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 在中序線索樹(shù)中找結(jié)點(diǎn)的前驅(qū)：在中序線索樹(shù)中找結(jié)點(diǎn)的前驅(qū)： (1) (1)若結(jié)點(diǎn)的若結(jié)點(diǎn)的ltagltag為為1 1（葉

49、子），則其前驅(qū)為（葉子），則其前驅(qū)為線索線索lchildlchild所指結(jié)點(diǎn)所指結(jié)點(diǎn)（2 2）（否則）若結(jié)點(diǎn)的）（否則）若結(jié)點(diǎn)的ltagltag為為0 0（非葉子），（非葉子），則其前驅(qū)為則其前驅(qū)為“從其左孩子沿著右鏈找到從其左孩子沿著右鏈找到rtagrtag為為1 1的那個(gè)結(jié)點(diǎn)的那個(gè)結(jié)點(diǎn)”(”(即左子樹(shù)最右下的結(jié)點(diǎn)）即左子樹(shù)最右下的結(jié)點(diǎn)） 在后序線索二叉樹(shù)中查找結(jié)點(diǎn)的前驅(qū)和后繼在后序線索二叉樹(shù)中查找結(jié)點(diǎn)的前驅(qū)和后繼 要知道其雙親的信息，要使用棧，所以說(shuō)要知道其雙親的信息，要使用棧，所以說(shuō)后序線索二叉樹(shù)是不完善的。后序線索二叉樹(shù)是不完善的。第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.3 遍歷二叉

50、樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 二叉樹(shù)的二叉線索存儲(chǔ)表示二叉樹(shù)的二叉線索存儲(chǔ)表示Typedef enum Link,Thread pointerTag;Typedef enum Link,Thread pointerTag; /Link=0: /Link=0:指針，指針，Thread=1Thread=1：線索：線索Typedef struct BiThrNode Typedef struct BiThrNode TElemType data; TElemType data; struct BiThrNode struct BiThrNode * *lchild, lchild, * *r

51、child;rchild; PointerTag Ltag, PointerTag Ltag, Rtag;Rtag;BiThrNode, BiThrNode, * *BiThrTree;BiThrTree;第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)二叉樹(shù)的線索化：是在遍歷的過(guò)程中，將二叉樹(shù)的線索化：是在遍歷的過(guò)程中，將二叉鏈表中的空指針改為線索二叉鏈表中的空指針改為線索中序遍歷的線索化算法中序遍歷的線索化算法 在二叉樹(shù)的線索鏈表上加一個(gè)頭結(jié)點(diǎn)，在二叉樹(shù)的線索鏈表上加一個(gè)頭結(jié)點(diǎn)，令其令其lchildlchild指向二叉樹(shù)的根結(jié)點(diǎn)，指向二叉樹(shù)的根結(jié)點(diǎn)，rchildrchild指向中序遍歷時(shí)訪問(wèn)的最后一

52、個(gè)結(jié)點(diǎn)指向中序遍歷時(shí)訪問(wèn)的最后一個(gè)結(jié)點(diǎn) 令二叉樹(shù)中序序列中的第一個(gè)結(jié)點(diǎn)的令二叉樹(shù)中序序列中的第一個(gè)結(jié)點(diǎn)的lchildlchild和最后一個(gè)結(jié)點(diǎn)的和最后一個(gè)結(jié)點(diǎn)的rchildrchild均指向頭均指向頭結(jié)點(diǎn)（象雙向鏈表，可雙向遍歷）結(jié)點(diǎn)（象雙向鏈表，可雙向遍歷） 設(shè)指針設(shè)指針p p指向當(dāng)前訪問(wèn)結(jié)點(diǎn)，指向當(dāng)前訪問(wèn)結(jié)點(diǎn)，prepre指向指向其前驅(qū)結(jié)點(diǎn)其前驅(qū)結(jié)點(diǎn) 6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 中序遍歷二叉線索樹(shù)的算法中序遍歷二叉線索樹(shù)的算法第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù) 中序遍歷二叉線索樹(shù)中序遍歷二叉線索樹(shù)T T的非遞歸算法的非遞歸算法思想：找左子樹(shù)的最左葉子結(jié)點(diǎn)，訪問(wèn)

53、思想：找左子樹(shù)的最左葉子結(jié)點(diǎn)，訪問(wèn) 訪問(wèn)后繼結(jié)點(diǎn)訪問(wèn)后繼結(jié)點(diǎn) 6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 學(xué)習(xí)線索化時(shí)，有三點(diǎn)必須注意：學(xué)習(xí)線索化時(shí)，有三點(diǎn)必須注意： 何種序的線索化，是先序、中序還是后序何種序的線索化，是先序、中序還是后序 要前驅(qū)線索化、后繼線索化還是全線索化要前驅(qū)線索化、后繼線索化還是全線索化 （前（前驅(qū)后繼都要）驅(qū)后繼都要） 只有空指針處才能加線索只有空指針處才能加線索; ;第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.4 樹(shù)和森林樹(shù)和森林1 1、樹(shù)的三種存儲(chǔ)結(jié)構(gòu)、樹(shù)的三種存儲(chǔ)結(jié)構(gòu) 雙親表示法雙親表示法 孩子鏈表表示法孩子鏈表表示法 樹(shù)的二叉鏈表樹(shù)的二叉鏈表( (孩

54、子孩子- -兄弟）兄弟） 存儲(chǔ)表示法存儲(chǔ)表示法第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.4 樹(shù)和森林樹(shù)和森林ABCDEFGr=0n=60 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5data parent 雙親表示法雙親表示法雙親雙親位置位置缺點(diǎn)：只反映了雙親位置缺點(diǎn)：只反映了雙親位置第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.4 樹(shù)和森林樹(shù)和森林 typedef struct PTNode ElemType data; int parent; / 雙親位置域 PTNode; data parent#define MAX_TREE_SIZE 100結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):C語(yǔ)

55、言的類型描述語(yǔ)言的類型描述:第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.4 樹(shù)和森林樹(shù)和森林typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; / 根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù) PTree;樹(shù)結(jié)構(gòu)樹(shù)結(jié)構(gòu):第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.4 樹(shù)和森林樹(shù)和森林r=0n=6 data firstchildABCDEFG0 A -11 B 02 C 03 D 04 E 25 F 26 G 464 5 1 2 3 孩子鏈表表示法孩子鏈表表示法-1 0 0 0 2 2 4parent第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.4 樹(shù)

56、和森林樹(shù)和森林typedef struct CTNode int child; struct CTNode *next; *ChildPtr;孩子結(jié)點(diǎn)結(jié)構(gòu)孩子結(jié)點(diǎn)結(jié)構(gòu): child nextchildC語(yǔ)言的類型描述語(yǔ)言的類型描述:第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.4 樹(shù)和森林樹(shù)和森林 typedef struct ElemType data; ChildPtr firstchild; / 孩子鏈的頭指針 CTBox;雙親結(jié)點(diǎn)結(jié)構(gòu)雙親結(jié)點(diǎn)結(jié)構(gòu) data firstchild第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.4 樹(shù)和森林樹(shù)和森林typedef struct CTBox nodes

57、MAX_TREE_SIZE; int n, r; / 結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置 CTree;樹(shù)結(jié)構(gòu)樹(shù)結(jié)構(gòu):第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.4 樹(shù)和森林樹(shù)和森林ABCDEFGroot AB C E D F G AB C E D F G 樹(shù)的二叉鏈表樹(shù)的二叉鏈表 ( (孩子孩子- -兄弟）存儲(chǔ)表示法兄弟）存儲(chǔ)表示法root第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.4 樹(shù)和森林樹(shù)和森林typedef struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;C語(yǔ)

58、言的類型描述語(yǔ)言的類型描述:結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu): firstchild data nextsibling第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.4 樹(shù)和森林樹(shù)和森林2 2、森林與二叉樹(shù)的轉(zhuǎn)換、森林與二叉樹(shù)的轉(zhuǎn)換 森林和二叉樹(shù)的對(duì)應(yīng)關(guān)系森林和二叉樹(shù)的對(duì)應(yīng)關(guān)系 森林轉(zhuǎn)換成二叉樹(shù)森林轉(zhuǎn)換成二叉樹(shù) 二叉樹(shù)轉(zhuǎn)換成森林二叉樹(shù)轉(zhuǎn)換成森林第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.4 樹(shù)和森林樹(shù)和森林 森林和二叉樹(shù)的對(duì)應(yīng)關(guān)系森林和二叉樹(shù)的對(duì)應(yīng)關(guān)系設(shè)森林設(shè)森林 F = ( T1, T2, , Tn ); T1 = ( root，t11, t12, , t1m );二叉樹(shù)二叉樹(shù) B =( LBT, Node(roo

59、t), RBT );第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.4 樹(shù)和森林樹(shù)和森林T1T11,T12,T1mT2,TnLBTRBTroot第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.4 樹(shù)和森林樹(shù)和森林BCADEBACDE二叉鏈表二叉鏈表作為中間作為中間媒介媒介第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.4 樹(shù)和森林樹(shù)和森林BCADBACDFEGHIJACDBGHIJEFFEHIJG樹(shù)與二樹(shù)與二叉樹(shù)對(duì)叉樹(shù)對(duì)應(yīng)應(yīng)樹(shù)根相樹(shù)根相連連森林與森林與二叉樹(shù)二叉樹(shù)對(duì)應(yīng)對(duì)應(yīng)第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.4 樹(shù)和森林樹(shù)和森林由森林轉(zhuǎn)換成二叉樹(shù)的轉(zhuǎn)換規(guī)則為由森林轉(zhuǎn)換成二叉樹(shù)的轉(zhuǎn)換規(guī)則為:若 F = ，即m

60、=0，則 B = ; 由 ROOT( T1 ) 對(duì)應(yīng)得到Node(root);否則，即m0由 (T2, T3, Tn ) 對(duì)應(yīng)得到 RBT。RBT是由是由 (T2, T3, Tn ) 轉(zhuǎn)換的二叉樹(shù)轉(zhuǎn)換的二叉樹(shù)若 F = T1 ,T2, T3, Tn ,則按如下規(guī)則轉(zhuǎn)換二叉樹(shù)B=(root, LBT, RBT) ：第第 六六 章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)6.4 樹(shù)和森林樹(shù)和森林由二叉樹(shù)轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為由二叉樹(shù)轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為:由LBT 對(duì)應(yīng)得到 ( t11, t12, ，t1m);若 B = , 則 F = ;否則，由 Node(root) 對(duì)應(yīng)得到 ROOT( T1 );由RBT 對(duì)