第四章樹(shù)與樹(shù)的表示(一)

1、 4.1樹(shù)與樹(shù)的表示 樹(shù)型結(jié)構(gòu)是一類(lèi)非常重要的非線性結(jié)構(gòu)。直觀地，樹(shù)型結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)構(gòu)。 樹(shù)在計(jì)算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序中，用樹(shù)來(lái)表示源程序的語(yǔ)法結(jié)構(gòu)；在數(shù)據(jù)庫(kù)系統(tǒng)中，可用樹(shù)來(lái)組織信息；在分析算法的行為時(shí)，可用樹(shù)來(lái)描述其執(zhí)行過(guò)程等等。 本章將詳細(xì)討論樹(shù)和二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)，主要介紹樹(shù)和二叉樹(shù)的概念、術(shù)語(yǔ)，二叉樹(shù)的遍歷算法。樹(shù)和二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)以及建立在各種存儲(chǔ)結(jié)構(gòu)上的操作及應(yīng)用等。什么是樹(shù)客觀世界中許多事物存在層次關(guān)系人類(lèi)社會(huì)家譜社會(huì)組織結(jié)構(gòu)圖書(shū)信息管理什么是樹(shù)分層次組織在管理上具有更高的效率!數(shù)據(jù)管理的基本操作之一：查找如何實(shí)現(xiàn)有效率的查找？查找（Search

2、ing）查找：根據(jù)某個(gè)給定關(guān)鍵字K ，從集合R中找出關(guān)鍵字與K相同的記錄靜態(tài)查找：集合中記錄是固定的 沒(méi)有插入和刪除操作，只有查找動(dòng)態(tài)查找：集合中記錄是動(dòng)態(tài)變化的 除查找，還可能發(fā)生插入和刪除45689靜態(tài)查找0K方法1：順序查找(數(shù)組存儲(chǔ)）Tbl10123int SequentialSearch (StaticTable *Tbl, ElementType K) /*在表在表Tbl1Tbln中查找關(guān)鍵字為中查找關(guān)鍵字為K的數(shù)據(jù)元素的數(shù)據(jù)元素*/int i;Tbl-Element0 = K; /*建立哨兵建立哨兵*/for(i = Tbl-Length; Tbl-Elementi!= K; i

3、-);return i; /*查找成功返回所在單元下標(biāo)；不成功返回查找成功返回所在單元下標(biāo)；不成功返回0*/順序查找算法的時(shí)間復(fù)雜度為O(n)。710方法2：二分查找（Binary Search) 假設(shè)n個(gè)數(shù)據(jù)元素的關(guān)鍵字滿(mǎn)足有序（比如：小到大）并且是連續(xù)存放（數(shù)組），那么可以進(jìn)行二分查找。例 假設(shè)有13個(gè)數(shù)據(jù)元素，按關(guān)鍵字由小到大順序存放.二分查找關(guān)健字為444的數(shù)據(jù)元素過(guò)程如下：51639455198100202226321 368 444 501123456789101112131、left = 1, right = 13; mid = (1+13)/2 = 7:2、left = mid

4、+1=8, right = 13; mid = (8+13)/2 = 10:100 444;321 Length;/*初始左邊界初始左邊界*/*初始右邊界初始右邊界*/while ( left = right )mid = (left+right)/2; /*計(jì)算中間元素坐標(biāo)計(jì)算中間元素坐標(biāo)*/if( K Elementmid)right = mid-1; /*調(diào)整右邊界調(diào)整右邊界*/else if( K Tbl-Elementmid) left = mid+1;/*調(diào)整左邊界調(diào)整左邊界*/else return mid;return NotFound;/*查找成功，返回?cái)?shù)據(jù)元素的下標(biāo)查找成功

5、，返回?cái)?shù)據(jù)元素的下標(biāo)*/*查找不成功，返回查找不成功，返回-1*/ 二分查找算法具有對(duì)數(shù)的時(shí)間復(fù)雜度O(logN)例 仍然以上面13個(gè)數(shù)據(jù)元素構(gòu)成的有序線性表為例二分查找關(guān)健字為 43 的數(shù)據(jù)元素如下：51639455198100202226321 368 444 501123456789101112131、left = 1, right = 13; mid = (1+13)/2 = 7:100 43;2、 left = 1, right = mid-1= 6; mid = (1+6)/2 = 3: 39 43;4、left = 4, right = mid-1= 4; mid = (4+4)

6、/2 = 4: 45 43;5、left = 4, right = mid-1= 3; left right ? 查找失敗，結(jié)束;6 11個(gè)元素的二分查找判定樹(shù) 判定樹(shù)上每個(gè)結(jié)點(diǎn)需要的查找次數(shù)剛好為該結(jié)點(diǎn)所在的層數(shù); 查找成功時(shí)查找次數(shù)不會(huì)超過(guò)判39定樹(shù)的深度 n個(gè)結(jié)點(diǎn)的判定樹(shù)的深度14710為log2n+1. ASL = (4*4+4*3+2*2+1)/11 = 325811二分查找的啟示？LM4.2樹(shù)的定義樹(shù)（Tree）: n（n0）個(gè)結(jié)點(diǎn)構(gòu)成的有限集合。當(dāng)n=0時(shí)，稱(chēng)為空樹(shù)；對(duì)于任一棵非空樹(shù)（n 0），它具備以下性質(zhì)： 樹(shù)中有一個(gè)稱(chēng)為“根（Root）”的特殊結(jié)點(diǎn)，用 r 表示； 其余結(jié)點(diǎn)

7、可分為m(m0)個(gè)互不相交的有限集T1，T2，. ，Tm，其中每個(gè)集合本身又是一棵樹(shù)，稱(chēng)為原來(lái)樹(shù)的“子樹(shù)（SubTree）”ABCDEFBGCHIDJKEFGLHIMJK(b) 子樹(shù)TA1(c) 子樹(shù)TA2(d) 子樹(shù)TA3(e)子樹(shù)子樹(shù)TA4(a) 樹(shù)TD 樹(shù)與非樹(shù)?AAABCDBCDBCDEFGHEFGHEFGH 子樹(shù)是不相交的； 除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)父結(jié)點(diǎn)； 一棵N個(gè)結(jié)點(diǎn)的樹(shù)有N-1條邊。IJKMA樹(shù)的一些基本術(shù)語(yǔ)1. 結(jié)點(diǎn)的度（Degree）：結(jié)點(diǎn)的子樹(shù)個(gè)數(shù)2. 樹(shù)的度：樹(shù)的所有結(jié)點(diǎn)中最大的度數(shù)3. 葉結(jié)點(diǎn)（Leaf）：度為0的結(jié)點(diǎn)4. 父結(jié)點(diǎn)（Parent）：有子樹(shù)的結(jié)

8、點(diǎn)是其子樹(shù)BCD的根結(jié)點(diǎn)的父結(jié)點(diǎn)FGHIJK5. 子結(jié)點(diǎn)（Child）：若A結(jié)點(diǎn)是B結(jié)點(diǎn)的父結(jié)點(diǎn)，則稱(chēng)B結(jié)點(diǎn)是A結(jié)點(diǎn)的子結(jié)點(diǎn)；子結(jié)點(diǎn)也稱(chēng)孩子結(jié)點(diǎn)。6. 兄弟結(jié)點(diǎn)（Sibling）：具有同一父結(jié)點(diǎn)的各結(jié)點(diǎn)彼此是兄弟結(jié)點(diǎn)。LMA樹(shù)的一些基本術(shù)語(yǔ)7. 路徑和路徑長(zhǎng)度：從結(jié)點(diǎn)n1到nk的路徑為一個(gè)結(jié)點(diǎn)序列n1 , n2 , , nk , ni是 ni+1的父結(jié)點(diǎn)。路徑所包含邊的個(gè)數(shù)為路徑的長(zhǎng)度。8. 祖先結(jié)點(diǎn)(Ancestor)：沿樹(shù)根到某一結(jié)點(diǎn)路BCD徑上的所有結(jié)點(diǎn)都是這個(gè)結(jié)點(diǎn)的祖先結(jié)點(diǎn)。9. 子孫結(jié)點(diǎn)(Descendant)：某一結(jié)點(diǎn)的子樹(shù)FGHIJK中的所有結(jié)點(diǎn)是這個(gè)結(jié)點(diǎn)的子孫。10. 結(jié)點(diǎn)的層

9、次（Level）：規(guī)定根結(jié)點(diǎn)在1層，其它任一結(jié)點(diǎn)的層數(shù)是其父結(jié)點(diǎn)的層數(shù)加1。11. 樹(shù)的深度（Depth）：樹(shù)中所有結(jié)點(diǎn)中的最大層次是這棵樹(shù)的深度。LM12.有序樹(shù)和無(wú)序樹(shù)：對(duì)于一棵樹(shù)，若其中每一個(gè)結(jié)點(diǎn)的子樹(shù)（若有）具有一定的次序，則該樹(shù)稱(chēng)為有序樹(shù)，否則稱(chēng)為無(wú)序樹(shù)。13.森林(forest)：是m(m0)棵互不相交的樹(shù)的集合。顯然，若將一棵樹(shù)的根結(jié)點(diǎn)刪除，剩余的子樹(shù)就構(gòu)成了森林。樹(shù)的表示ABCDEFGHIJKLMBEFKLACDGHIJM兒子-兄弟表示法ElementFirstChild NextSiblingAANBCDEFGHIJBCDNKLMEFN NGN NHNIJN NKNLN NM

10、N NAN45BCDNEFNNGNNHINJNNKNLNNElementMNNLeftLeftRight二叉樹(shù)Right4.2 二叉樹(shù)及存儲(chǔ)結(jié)構(gòu)二叉樹(shù)(Binary tree)是n(n0)個(gè)結(jié)點(diǎn)的有限集合。若n=0時(shí)稱(chēng)為空樹(shù)，否則： 有且只有一個(gè)特殊的稱(chēng)為樹(shù)的根(Root)結(jié)點(diǎn)； 若n1時(shí)，其余的結(jié)點(diǎn)被分成為二個(gè)互不相交的子集T1,T2，分別稱(chēng)之為左、右子樹(shù)，并且左、右子樹(shù)又都是二叉樹(shù)。 由此可知，二叉樹(shù)的定義是遞歸的。 二叉樹(shù)具體五種基本形態(tài)TLTRTLTR(a)(b)(c)(d)(e) 二叉樹(shù)的子樹(shù)有左右順序之分空樹(shù)空樹(shù)只含根結(jié)點(diǎn)只含根結(jié)點(diǎn)右子樹(shù)為空樹(shù)右子樹(shù)為空樹(shù)左子樹(shù)為空樹(shù)左子樹(shù)為空樹(shù)左

11、右子樹(shù)均不左右子樹(shù)均不為空樹(shù)為空樹(shù)特殊二叉樹(shù) 斜二叉樹(shù)(Skewed Binary Tree)A 完美二叉樹(shù)(Perfect Binary Tree) 滿(mǎn)二叉樹(shù)(Full Binary Tree）1AB23C4B56C7DEFGD89 1011 1213 1415 完全二叉樹(shù)(Complete Binary Tree)有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，對(duì)樹(shù)中結(jié)點(diǎn)按HIJ2K L1AM N3O從上至下、從左到右順序進(jìn)行編號(hào)，編號(hào)為i（1 i n）結(jié)點(diǎn)與滿(mǎn)二叉樹(shù)中編號(hào)為 i 結(jié)點(diǎn)在二叉樹(shù)中位置相同84DB95E106FC7GHJK894101151213614157213894101152112673(a) 滿(mǎn)

12、二叉樹(shù)滿(mǎn)二叉樹(shù)(b) 完全二叉樹(shù)完全二叉樹(shù)1362455674213(c) 非完全二叉樹(shù)非完全二叉樹(shù)圖圖6-4 特殊形態(tài)的特殊形態(tài)的二叉二叉樹(shù)樹(shù)二叉樹(shù)幾個(gè)重要性質(zhì)性質(zhì)1： 在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)。(i1)性質(zhì)2： 深度為k的二叉樹(shù)上至多含2k-1個(gè)結(jié)點(diǎn)。(k1)性質(zhì)3： 對(duì)任何一棵二叉樹(shù)，若它含有n0個(gè)葉子結(jié)點(diǎn)、n2個(gè)度為2的結(jié)點(diǎn)， A 則必存在關(guān)系式：n0 = n2+1。 BCDJEKFH n0 = 4，n1 = 2 n2 = 3； n0 = n2 +1滿(mǎn)二叉樹(shù)的特點(diǎn)： 基本特點(diǎn)是每一層上的結(jié)點(diǎn)數(shù)總是最大結(jié)點(diǎn)數(shù)。 滿(mǎn)二叉樹(shù)的所有的支結(jié)點(diǎn)都有左、右子樹(shù)。 可對(duì)滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)進(jìn)行

13、連續(xù)編號(hào)，若規(guī)定從根結(jié)點(diǎn)開(kāi)始，按“自上而下、自左至右”的原則進(jìn)行。完全二叉樹(shù)(Complete Binary Tree)：如果深度為k，由n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿(mǎn)二叉樹(shù)中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)，該二叉樹(shù)稱(chēng)為完全二叉樹(shù)。 或深度為k的滿(mǎn)二叉樹(shù)中編號(hào)從1到n的前n個(gè)結(jié)點(diǎn)構(gòu)成了一棵深度為k的完全二叉樹(shù)。其中 2k-1 n2k-1 。 完全二叉樹(shù)是滿(mǎn)二叉樹(shù)的一部分，而滿(mǎn)二叉樹(shù)是完全二叉樹(shù)的特例。完全二叉樹(shù)的特點(diǎn)： 若完全二叉樹(shù)的深度為k ，則所有的葉子結(jié)點(diǎn)都出現(xiàn)在第k層或k-1層。對(duì)于任一結(jié)點(diǎn)，如果其右子樹(shù)的最大層次為l，則其左子樹(shù)的最大層次為l或l+1。性質(zhì)4：n個(gè)

14、結(jié)點(diǎn)的完全二叉樹(shù)深度為：2n +1。 其中符號(hào)： x表示不大于x的最大整數(shù)。 x 表示不小于x的最小整數(shù)。,二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義類(lèi)型名稱(chēng)：二叉樹(shù)數(shù)據(jù)對(duì)象集：一個(gè)有窮的結(jié)點(diǎn)集合。若不為空，則由根結(jié)點(diǎn)和其左、右二叉子樹(shù)組成。操作集： BT BinTree, Item ElementType，重要操作有：1、Boolean IsEmpty( BinTree BT )： 判別BT是否為空；2、void Traversal( BinTree BT )：遍歷，按某順序訪問(wèn)每個(gè)結(jié)點(diǎn)；：遍歷，按某順序訪問(wèn)每個(gè)結(jié)點(diǎn)；3、BinTree CreatBinTree( )：創(chuàng)建一個(gè)二叉樹(shù)。：創(chuàng)建一個(gè)二叉樹(shù)。常用的

15、遍歷方法有： void PreOrderTraversal( BinTree BT )：先序：先序-根、左子樹(shù)、右子樹(shù)；根、左子樹(shù)、右子樹(shù)； void InOrderTraversal( BinTree BT )： 中序-左子樹(shù)、根、右子樹(shù)； void PostOrderTraversal( BinTree BT )：后序：后序-左子樹(shù)、右子樹(shù)、根左子樹(shù)、右子樹(shù)、根 void LevelOrderTraversal( BinTree BT )：層次遍歷，從上到下、從左到右：層次遍歷，從上到下、從左到右5/25二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)1. 順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元依次“自上而下、自左至右”存儲(chǔ)完全二叉樹(shù)的數(shù)據(jù)元素。對(duì)于完全二叉樹(shù)上編號(hào)為i的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組的下標(biāo)值為i的分 量中。結(jié)點(diǎn)序號(hào)A1B2O3C4S5M6Q7W8K9n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)父子關(guān)系：非根結(jié)點(diǎn)（序號(hào) i 1）的父結(jié)點(diǎn)的序號(hào)是 i / 2 ;當(dāng) i / 2 =0時(shí)，該結(jié)點(diǎn)是樹(shù)的根結(jié)點(diǎn)。結(jié)點(diǎn)（序號(hào)為 i ）的左孩子結(jié)點(diǎn)的序號(hào)是 2i，（若2 i n，沒(méi)有左孩子）;結(jié)點(diǎn)（序號(hào)為 i ）的右孩子結(jié)點(diǎn)的序號(hào)是 2i+1，（若2 i +1 n，沒(méi)有右孩子）; 一般二叉樹(shù)也可以采用這種結(jié)構(gòu)，但會(huì)造成空間浪費(fèi)1A2A3BO4B56O7MMC