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

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

2、1313個(gè)結(jié)點(diǎn)的樹個(gè)結(jié)點(diǎn)的樹樹的抽象數(shù)據(jù)類型定義樹的抽象數(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ù)據(jù)類型定義樹的抽象數(shù)據(jù)類型定義數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 D D ：D D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。樹的抽象數(shù)據(jù)類型定義樹的抽象數(shù)據(jù)類型定義數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：若若|D|=0|D|=0，則稱為空樹；，則稱為空樹；否則否

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本身是一棵符合本本身是一棵符合本定義的樹，稱為根定義的樹，稱為根rootroot的子樹。的子樹。樹的基本操作樹的基本操作2 2）插入類）插入類1 1）查找類）查找類3 3）刪除類）刪除類樹的基本操作樹的基本操作- -查找類查找類Root(T) / Root(T) / 求樹的根結(jié)點(diǎn)求樹的根結(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)的最左孩子最左孩子 樹的基本操作樹的基本操作- -查找類查找類RightSibling(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)求當(dāng)前結(jié)點(diǎn)的右兄弟的右兄弟TreeEmpty(T) / / 判定樹是否為空樹判定樹是否為空樹 TreeDepth(T) / / 求樹的深度求樹的深度TraverseTree( T,

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

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

7、元素+ +若干指向若干指向子樹的分支子樹的分支結(jié)點(diǎn)的度結(jié)點(diǎn)的度: :分支的個(gè)數(shù)分支的個(gè)數(shù)樹的度樹的度: :樹中所有結(jié)點(diǎn)的度的最大值樹中所有結(jié)點(diǎn)的度的最大值基本術(shù)語基本術(shù)語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ù)語基本術(shù)語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ù)語基本術(shù)語ABCDEFGHIJM

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

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

10、據(jù)元素其它數(shù)據(jù)元素(一個(gè)前驅(qū)、一個(gè)前驅(qū)、一個(gè)后繼一個(gè)后繼)二叉樹的定義二叉樹的定義 二叉樹或?yàn)榭諛洌换蚴怯梢粋€(gè)根結(jié)點(diǎn)加上兩棵分二叉樹或?yàn)榭諛?；或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為別稱為左子樹左子樹和和右子樹右子樹的、的、互不交的互不交的二叉樹組成。二叉樹組成。ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹EF二叉樹的五種基本形態(tài)二叉樹的五種基本形態(tài)N1 1）空樹）空樹2 2）只含根結(jié)點(diǎn)）只含根結(jié)點(diǎn)N3 3）左子樹為空樹）左子樹為空樹R二叉樹的五種基本形態(tài)二叉樹的五種基本形態(tài)NNLRL5 5）左右子樹均不為空樹）左右子樹均不為空樹4 4）右子樹為空樹）右子樹為空樹基本操作基本操作查找類查找類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)二叉樹的重要特性二叉樹的重要特性 性質(zhì)性質(zhì) 1 1 ： 在二叉樹的第在二叉樹的第 i i 層上至多有層上至多有2 2i-1 i-1 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。(i1)(i1)二叉樹具有以下五條重要性質(zhì)：二叉樹具有以下五條重要性質(zhì)：二叉樹的重要特性二叉樹的重要特性ACGBDEFK LHJIM NO1234層號(hào)二叉樹的重要特性二叉樹的重要特性用歸

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); ;二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹，則二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹，則第第 i i 層的結(jié)點(diǎn)數(shù)層的結(jié)點(diǎn)數(shù) = = 2i-2 2 = 2i-1 。二叉樹的重要特性二叉樹的重要特性性質(zhì)性質(zhì) 2 2 ： 深度為深度為 k k 的二叉樹上至多含的二叉樹上至多含 2 2k k-1 -1 個(gè)個(gè)結(jié)點(diǎn)（結(jié)點(diǎn)（k1k1）

14、二叉樹的重要特性二叉樹的重要特性證明：證明： 20+21+ +2k-1 = 2k-1 第第1 1層層: 2: 20 0第第2 2層層: 2: 21 1第第i i層層: 2: 2i-1i-1二叉樹的重要特性二叉樹的重要特性性質(zhì)性質(zhì) 3 3 ： 對(duì)任何一棵二叉樹，若它含有對(duì)任何一棵二叉樹，若它含有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è) 二叉樹上結(jié)點(diǎn)總數(shù)二叉樹上結(jié)點(diǎn)總數(shù) n = n0 + n1 + n2 式式1二叉樹的重要特性二叉樹的重要特性123456789 10設(shè)二叉樹上分支總數(shù)設(shè)二叉樹上分支總數(shù)(

15、 (邊數(shù)邊數(shù)) )為為b b ，由樹的性質(zhì)：，由樹的性質(zhì)： n =b+1，二叉樹的重要特性二叉樹的重要特性又因?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二叉樹的重要特性二叉樹的重要特性二叉樹的重要特性二叉樹的重要特性兩類特殊的二叉樹：兩類特殊的二叉樹：1 1）滿二叉樹：指的是）滿二叉樹：指的是深度為深度為k k且含有且

16、含有2 2k k-1-1個(gè)個(gè)結(jié)點(diǎn)的二叉樹。結(jié)點(diǎn)的二叉樹。123456789 10 11 12 13 14 15二叉樹的重要特性二叉樹的重要特性2）完全二叉樹：樹中所含的 n 個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為 1 至 n 的結(jié)點(diǎn)一一對(duì)應(yīng)。abcdefghij123456789 10二叉樹的重要特性二叉樹的重要特性性質(zhì)性質(zhì) 4 4 ： 具有具有 n n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n +1二叉樹的重要特性二叉樹的重要特性證明：證明：由性質(zhì)由性質(zhì)2：1-k-1層結(jié)點(diǎn)數(shù)為：層結(jié)點(diǎn)數(shù)為： 2k-1 -1 假設(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)成的樹一定是滿二叉樹層構(gòu)成的樹一定是滿二叉樹二叉樹的重要特性二叉樹的重要特性 所以：所以：2k-1 - 1 n 2k - 1 2k-1 n 2k 于是：于是：k-1 log2 n n，則該結(jié)點(diǎn)無左孩子，則該結(jié)點(diǎn)無左孩子, 否則，編號(hào)為否則，編號(hào)為 2i 的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)。的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)。 若若 2i+1n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)，否則，編號(hào)，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)，否則，編號(hào)為為2i+1 的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。123456789 10二叉樹的重要特性二叉樹的重要特性證明證明2 2歸納證明

18、歸納證明1、i=1，左孩子是，左孩子是2。如果。如果n2，則左孩子不存在。，則左孩子不存在。 右孩子是右孩子是3。如果如果n3，則右孩子不存在，則右孩子不存在。123456789 10二叉樹的重要特性二叉樹的重要特性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二叉樹的重要特性二叉樹的重要特性根據(jù)歸納假設(shè)，k的左右孩子分別是2k和2k+1，k+1的左右孩子為2k+2和2k+3，滿足2(k+1)和2(k+1)+1.二叉樹的重要特性二叉樹的重要特性3.2、如果k與 k + 1時(shí)不在同一層，那么k一定是某一層最右邊的結(jié)點(diǎn)，k+1是下一層的最左邊的結(jié)點(diǎn)，假設(shè)k所在的層為j-1層，