數(shù)據(jù)結(jié)構(gòu)-樹(shù)、二叉樹(shù)及性質(zhì)

1、二叉樹(shù)的類型定義二叉樹(shù)的類型定義樹(shù)的類型定義樹(shù)的類型定義小結(jié)和作業(yè)小結(jié)和作業(yè)樹(shù)樹(shù)（Tree)和二叉樹(shù)（和二叉樹(shù)（Binary Tree）基本操作基本操作樹(shù)的抽象數(shù)據(jù)類型定義樹(shù)的抽象數(shù)據(jù)類型定義樹(shù)的表示方法樹(shù)的表示方法樹(shù)的基本術(shù)語(yǔ)樹(shù)的基本術(shù)語(yǔ)樹(shù)型結(jié)構(gòu)和線性結(jié)構(gòu)結(jié)構(gòu)特點(diǎn)的對(duì)比樹(shù)型結(jié)構(gòu)和線性結(jié)構(gòu)結(jié)構(gòu)特點(diǎn)的對(duì)比樹(shù)的類型定義樹(shù)的類型定義二叉樹(shù)的五種基本形態(tài)二叉樹(shù)的五種基本形態(tài)二叉樹(shù)的定義二叉樹(shù)的定義主要基本操作主要基本操作二叉樹(shù)的重要特性二叉樹(shù)的重要特性二叉樹(shù)的類型定義二叉樹(shù)的類型定義樹(shù)的抽象數(shù)據(jù)類型定義樹(shù)的抽象數(shù)據(jù)類型定義樹(shù)的示例：樹(shù)的示例：AACGBDEFKLHMIJ只有根結(jié)點(diǎn)的樹(shù)只有根結(jié)點(diǎn)的樹(shù)有有

2、1313個(gè)結(jié)點(diǎn)的樹(shù)個(gè)結(jié)點(diǎn)的樹(shù)樹(shù)的抽象數(shù)據(jù)類型定義樹(shù)的抽象數(shù)據(jù)類型定義ACGBDEFKLHMIJA A是根；是根；其余結(jié)點(diǎn)分成三個(gè)互不相交的子集，其余結(jié)點(diǎn)分成三個(gè)互不相交的子集，T1=B,E,F,K,L； T2=C,G；T3=D,H,I,J,M；T1,T2,T3T1,T2,T3都是根都是根A A的子樹(shù)，且本身也是一棵樹(shù)。的子樹(shù)，且本身也是一棵樹(shù)。樹(shù)的抽象數(shù)據(jù)類型定義樹(shù)的抽象數(shù)據(jù)類型定義數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 D D ：D D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。樹(shù)的抽象數(shù)據(jù)類型定義樹(shù)的抽象數(shù)據(jù)類型定義數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：若若|D|=0|D|=0，則稱為空樹(shù)；，則稱為空樹(shù)；否則否

3、則: : (1) (1) 在在D D中存在唯一的稱為根的數(shù)據(jù)元素中存在唯一的稱為根的數(shù)據(jù)元素root,root, (2) (2) 當(dāng)當(dāng)n1n1時(shí)，其余結(jié)點(diǎn)可分為時(shí)，其余結(jié)點(diǎn)可分為m (m0)個(gè)互不相個(gè)互不相交的有限集交的有限集T1, T2, , Tm, ,其中其中T Ti i本身是一棵符合本本身是一棵符合本定義的樹(shù)，稱為根定義的樹(shù)，稱為根rootroot的子樹(shù)。的子樹(shù)。樹(shù)的基本操作樹(shù)的基本操作2 2）插入類）插入類1 1）查找類）查找類3 3）刪除類）刪除類樹(shù)的基本操作樹(shù)的基本操作- -查找類查找類Root(T) / Root(T) / 求樹(shù)的根結(jié)點(diǎn)求樹(shù)的根結(jié)點(diǎn) Value(T, cur_e)

4、 / Value(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的元素值求當(dāng)前結(jié)點(diǎn)的元素值 Parent(T, cur_e) /Parent(T, cur_e) /求當(dāng)前結(jié)點(diǎn)的雙求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)親結(jié)點(diǎn)LeftChild(T, cur_e)/ LeftChild(T, cur_e)/ 求當(dāng)前結(jié)點(diǎn)的求當(dāng)前結(jié)點(diǎn)的最左孩子最左孩子 樹(shù)的基本操作樹(shù)的基本操作- -查找類查找類RightSibling(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)求當(dāng)前結(jié)點(diǎn)的右兄弟的右兄弟TreeEmpty(T) / / 判定樹(shù)是否為空樹(shù)判定樹(shù)是否為空樹(shù) TreeDepth(T) / / 求樹(shù)的深度求樹(shù)的深度TraverseTree( T,

5、 Visit() ) / / 遍歷遍歷樹(shù)的基本操作樹(shù)的基本操作插入類插入類InitTree(&T) / / 初始化置空樹(shù)初始化置空樹(shù) CreateTree(&T, definition) / / 按定義構(gòu)造樹(shù)按定義構(gòu)造樹(shù)Assign(T, cur_e, value) / / 給當(dāng)前結(jié)點(diǎn)賦值給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T, &p, i, c) / / 將以將以c c為根的樹(shù)插入為結(jié)點(diǎn)為根的樹(shù)插入為結(jié)點(diǎn)p p的的 第第i i棵子樹(shù)棵子樹(shù)樹(shù)的基本操作樹(shù)的基本操作刪除類刪除類ClearTree(&T) / 將樹(shù)清空將樹(shù)清空 DestroyTree(&

6、amp;T) / 銷毀樹(shù)的結(jié)構(gòu)銷毀樹(shù)的結(jié)構(gòu)DeleteChild(&T, &p, i) / / 刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)p p的第的第i i棵子樹(shù)棵子樹(shù)樹(shù)的表示方法樹(shù)的表示方法嵌套集合表示法嵌套集合表示法廣義表廣義表凹入表示法凹入表示法圖圖樹(shù)的表示方法樹(shù)的表示方法ACGBDEFKLHJI樹(shù)的表示方法樹(shù)的表示方法ALEKBFCDGHIJ樹(shù)樹(shù)根根T3T2T1樹(shù)的表示方法樹(shù)的表示方法樹(shù)的表示方法樹(shù)的表示方法ABEKLFDHMIJ樹(shù)的表示方法樹(shù)的表示方法A( )T1T3T2樹(shù)根B(E, F(K, L), C(G), D(H, I, J(M)基本術(shù)語(yǔ)基本術(shù)語(yǔ)DHIJM結(jié)點(diǎn)結(jié)點(diǎn): : 數(shù)據(jù)元素?cái)?shù)據(jù)

7、元素+ +若干指向若干指向子樹(shù)的分支子樹(shù)的分支結(jié)點(diǎn)的度結(jié)點(diǎn)的度: :分支的個(gè)數(shù)分支的個(gè)數(shù)樹(shù)的度樹(shù)的度: :樹(shù)中所有結(jié)點(diǎn)的度的最大值樹(shù)中所有結(jié)點(diǎn)的度的最大值基本術(shù)語(yǔ)基本術(shù)語(yǔ)DHIJM葉子結(jié)點(diǎn)葉子結(jié)點(diǎn): :分支分支( (非終端非終端) )結(jié)點(diǎn)結(jié)點(diǎn): :度為零的結(jié)點(diǎn)度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)基本術(shù)語(yǔ)基本術(shù)語(yǔ)ABCDEFGHIJMKL( (從根到結(jié)點(diǎn)的從根到結(jié)點(diǎn)的) )路徑：路徑：由從根到該結(jié)點(diǎn)所由從根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成經(jīng)分支和結(jié)點(diǎn)構(gòu)成孩子結(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)基本術(shù)語(yǔ)基本術(shù)語(yǔ)ABCDEFGHIJM

8、KL結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次: :樹(shù)的深度：樹(shù)的深度：假設(shè)根結(jié)點(diǎn)的層次為假設(shè)根結(jié)點(diǎn)的層次為1,1,第第i i 層結(jié)點(diǎn)的子樹(shù)的根層結(jié)點(diǎn)的子樹(shù)的根結(jié)點(diǎn)的層次為結(jié)點(diǎn)的層次為i+1i+1樹(shù)中葉子結(jié)點(diǎn)所在的最大層次樹(shù)中葉子結(jié)點(diǎn)所在的最大層次1234基本術(shù)語(yǔ)基本術(shù)語(yǔ)( () ) 有確定的根；有確定的根；( () ) 樹(shù)根和子樹(shù)根之間為有向關(guān)系。樹(shù)根和子樹(shù)根之間為有向關(guān)系。有向樹(shù)：有向樹(shù)：基本術(shù)語(yǔ)基本術(shù)語(yǔ)有序樹(shù)：有序樹(shù)：子樹(shù)之間存在確定的次序關(guān)系。子樹(shù)之間存在確定的次序關(guān)系。無(wú)序樹(shù)：無(wú)序樹(shù)：子樹(shù)之間不存在確定的次序關(guān)系。子樹(shù)之間不存在確定的次序關(guān)系。森林：森林：是是 m m（m0m0）棵互不相交的樹(shù)的集合）棵互

9、不相交的樹(shù)的集合基本術(shù)語(yǔ)基本術(shù)語(yǔ)ArootBEFKLCGDHIJMF任何一棵非空樹(shù)是一個(gè)二元組任何一棵非空樹(shù)是一個(gè)二元組 Tree = Tree = （rootroot，F(xiàn) F）其中：其中：root root 被稱為根結(jié)點(diǎn)，被稱為根結(jié)點(diǎn)，F(xiàn) F 被稱為子樹(shù)森林被稱為子樹(shù)森林樹(shù)型結(jié)構(gòu)和線性結(jié)構(gòu)結(jié)構(gòu)特點(diǎn)的對(duì)比樹(shù)型結(jié)構(gòu)和線性結(jié)構(gòu)結(jié)構(gòu)特點(diǎn)的對(duì)比線性結(jié)構(gòu)線性結(jié)構(gòu)樹(shù)型結(jié)構(gòu)樹(shù)型結(jié)構(gòu)根結(jié)點(diǎn)（無(wú)前驅(qū)）根結(jié)點(diǎn)（無(wú)前驅(qū)）第一個(gè)數(shù)據(jù)元素?zé)o前驅(qū)第一個(gè)數(shù)據(jù)元素?zé)o前驅(qū)最后一個(gè)數(shù)據(jù)元素最后一個(gè)數(shù)據(jù)元素(無(wú)后繼無(wú)后繼)多個(gè)葉子結(jié)點(diǎn)多個(gè)葉子結(jié)點(diǎn)(無(wú)后繼無(wú)后繼)其它數(shù)據(jù)元素其它數(shù)據(jù)元素(一個(gè)前一個(gè)前驅(qū)、多個(gè)后繼驅(qū)、多個(gè)后繼)其它數(shù)

10、據(jù)元素其它數(shù)據(jù)元素(一個(gè)前驅(qū)、一個(gè)前驅(qū)、一個(gè)后繼一個(gè)后繼)二叉樹(shù)的定義二叉樹(shù)的定義 二叉樹(shù)或?yàn)榭諛?shù)；或是由一個(gè)根結(jié)點(diǎn)加上兩棵分二叉樹(shù)或?yàn)榭諛?shù)；或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為別稱為左子樹(shù)左子樹(shù)和和右子樹(shù)右子樹(shù)的、的、互不交的互不交的二叉樹(shù)組成。二叉樹(shù)組成。ABCDEFGHK根結(jié)點(diǎn)左子樹(shù)右子樹(shù)EF二叉樹(shù)的五種基本形態(tài)二叉樹(shù)的五種基本形態(tài)N1 1）空樹(shù)）空樹(shù)2 2）只含根結(jié)點(diǎn)）只含根結(jié)點(diǎn)N3 3）左子樹(shù)為空樹(shù)）左子樹(shù)為空樹(shù)R二叉樹(shù)的五種基本形態(tài)二叉樹(shù)的五種基本形態(tài)NNLRL5 5）左右子樹(shù)均不為空樹(shù)）左右子樹(shù)均不為空樹(shù)4 4）右子樹(shù)為空樹(shù)）右子樹(shù)為空樹(shù)基本操作基本操作查找類查找類Root(T) V

11、alue(T, e) Parent(T, e) LeftChild(T, e) RightChild(T, e) LeftSibling(T, e) RightSibling(T, e)BiTreeEmpty(T) BiTreeDepth(T)基本操作基本操作查找類查找類PreOrderTraverse(T, Visit()InOrderTraverse(T, Visit()PostOrderTraverse(T, Visit()LevelOrderTraverse(T, Visit()基本操作基本操作插入類插入類InitBiTree(&T)Assign(T, &e, valu

12、e)CreateBiTree(&T, definition)InsertChild(T, p, LR, c)基本操作基本操作刪除類刪除類ClearBiTree(&T)DestroyBiTree(&T)DeleteChild(T, p, LR)二叉樹(shù)的重要特性二叉樹(shù)的重要特性 性質(zhì)性質(zhì) 1 1 ： 在二叉樹(shù)的第在二叉樹(shù)的第 i i 層上至多有層上至多有2 2i-1 i-1 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。(i1)(i1)二叉樹(shù)具有以下五條重要性質(zhì)：二叉樹(shù)具有以下五條重要性質(zhì)：二叉樹(shù)的重要特性二叉樹(shù)的重要特性ACGBDEFK LHJIM NO1234層號(hào)二叉樹(shù)的重要特性二叉樹(shù)的重要特性用歸

13、納法證明用歸納法證明： 歸納基礎(chǔ)：歸納基礎(chǔ)： 歸納假設(shè)：歸納假設(shè)： 歸納證明：歸納證明：i i = = 1 1 層時(shí)，只有一個(gè)根結(jié)點(diǎn)，層時(shí)，只有一個(gè)根結(jié)點(diǎn)， 2 2i-1 i-1 = = 2 20 0 = = 1 1；假設(shè)第假設(shè)第i-1i-1層上至多有層上至多有2 2i-2i-2個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn); ;二叉樹(shù)上每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)，則二叉樹(shù)上每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)，則第第 i i 層的結(jié)點(diǎn)數(shù)層的結(jié)點(diǎn)數(shù) = = 2i-2 2 = 2i-1 。二叉樹(shù)的重要特性二叉樹(shù)的重要特性性質(zhì)性質(zhì) 2 2 ： 深度為深度為 k k 的二叉樹(shù)上至多含的二叉樹(shù)上至多含 2 2k k-1 -1 個(gè)個(gè)結(jié)點(diǎn)（結(jié)點(diǎn)（k1k1）

14、二叉樹(shù)的重要特性二叉樹(shù)的重要特性證明：證明： 20+21+ +2k-1 = 2k-1 第第1 1層層: 2: 20 0第第2 2層層: 2: 21 1第第i i層層: 2: 2i-1i-1二叉樹(shù)的重要特性二叉樹(shù)的重要特性性質(zhì)性質(zhì) 3 3 ： 對(duì)任何一棵二叉樹(shù)，若它含有對(duì)任何一棵二叉樹(shù)，若它含有n0 個(gè)葉子個(gè)葉子結(jié)點(diǎn)、結(jié)點(diǎn)、n2 個(gè)度為個(gè)度為 2 的結(jié)點(diǎn)，則必存在關(guān)系的結(jié)點(diǎn)，則必存在關(guān)系式：式：n0 = n2+1證明：證明：設(shè)設(shè) 二叉樹(shù)上結(jié)點(diǎn)總數(shù)二叉樹(shù)上結(jié)點(diǎn)總數(shù) n = n0 + n1 + n2 式式1二叉樹(shù)的重要特性二叉樹(shù)的重要特性123456789 10設(shè)二叉樹(shù)上分支總數(shù)設(shè)二叉樹(shù)上分支總數(shù)(

15、 (邊數(shù)邊數(shù)) )為為b b ，由樹(shù)的性質(zhì)：，由樹(shù)的性質(zhì)： n =b+1，二叉樹(shù)的重要特性二叉樹(shù)的重要特性又因?yàn)槎葹橛忠驗(yàn)槎葹? 1的點(diǎn)引出一條邊的點(diǎn)引出一條邊度為度為2 2的點(diǎn)引出的點(diǎn)引出2 2條邊條邊 所以：所以：b=n1 + 2n2123456789 10所以：所以：n=n1 + 2n2 + 1 式式2由式由式1 1和和2 2得到：得到： n0 + n1 + n2= n1 + 2n2+1整理后整理后 n0 = n2 + 1二叉樹(shù)的重要特性二叉樹(shù)的重要特性二叉樹(shù)的重要特性二叉樹(shù)的重要特性兩類特殊的二叉樹(shù)：兩類特殊的二叉樹(shù)：1 1）滿二叉樹(shù)：指的是）滿二叉樹(shù)：指的是深度為深度為k k且含有且

16、含有2 2k k-1-1個(gè)個(gè)結(jié)點(diǎn)的二叉樹(shù)。結(jié)點(diǎn)的二叉樹(shù)。123456789 10 11 12 13 14 15二叉樹(shù)的重要特性二叉樹(shù)的重要特性2）完全二叉樹(shù)：樹(shù)中所含的 n 個(gè)結(jié)點(diǎn)和滿二叉樹(shù)中編號(hào)為 1 至 n 的結(jié)點(diǎn)一一對(duì)應(yīng)。abcdefghij123456789 10二叉樹(shù)的重要特性二叉樹(shù)的重要特性性質(zhì)性質(zhì) 4 4 ： 具有具有 n n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 log2n +1二叉樹(shù)的重要特性二叉樹(shù)的重要特性證明：證明：由性質(zhì)由性質(zhì)2：1-k-1層結(jié)點(diǎn)數(shù)為：層結(jié)點(diǎn)數(shù)為： 2k-1 -1 假設(shè)完全二叉樹(shù)的深度為假設(shè)完全二叉樹(shù)的深度為k k。由性質(zhì)由性質(zhì)2，1至至

17、k層結(jié)點(diǎn)數(shù)最多為：層結(jié)點(diǎn)數(shù)最多為： 2k -1 由定義：由定義： 1-k-1層構(gòu)成的樹(shù)一定是滿二叉樹(shù)層構(gòu)成的樹(shù)一定是滿二叉樹(shù)二叉樹(shù)的重要特性二叉樹(shù)的重要特性 所以：所以：2k-1 - 1 n 2k - 1 2k-1 n 2k 于是：于是：k-1 log2 n n，則該結(jié)點(diǎn)無(wú)左孩子，則該結(jié)點(diǎn)無(wú)左孩子, 否則，編號(hào)為否則，編號(hào)為 2i 的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)。的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)。 若若 2i+1n，則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)，否則，編號(hào)，則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)，否則，編號(hào)為為2i+1 的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。123456789 10二叉樹(shù)的重要特性二叉樹(shù)的重要特性證明證明2 2歸納證明

18、歸納證明1、i=1，左孩子是，左孩子是2。如果。如果n2，則左孩子不存在。，則左孩子不存在。 右孩子是右孩子是3。如果如果n3，則右孩子不存在，則右孩子不存在。123456789 10二叉樹(shù)的重要特性二叉樹(shù)的重要特性2、假設(shè) i = k時(shí)，命題成立，即如果有左孩子，左孩子為 2k，如果有右孩子，右孩子為2k + 1。3、當(dāng) i = k + 1時(shí)，3.1、如果k與 k + 1時(shí)在同一層，根據(jù)編號(hào)規(guī)則，結(jié)點(diǎn)k和結(jié)點(diǎn)k+1 相鄰，其孩子結(jié)點(diǎn)（如果有）也相鄰。 1232j-1kk+12k 2k+12k+22k+32j2j+1二叉樹(shù)的重要特性二叉樹(shù)的重要特性根據(jù)歸納假設(shè)，k的左右孩子分別是2k和2k+1，k+1的左右孩子為2k+2和2k+3，滿足2(k+1)和2(k+1)+1.二叉樹(shù)的重要特性二叉樹(shù)的重要特性3.2、如果k與 k + 1時(shí)不在同一層，那么k一定是某一層最右邊的結(jié)點(diǎn)，k+1是下一層的最左邊的結(jié)點(diǎn)，假設(shè)k所在的層為j-1層，