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

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

2、ing）查找：根據(jù)某個給定關(guān)鍵字K ，從集合R中找出關(guān)鍵字與K相同的記錄靜態(tài)查找：集合中記錄是固定的 沒有插入和刪除操作，只有查找動態(tài)查找：集合中記錄是動態(tài)變化的 除查找，還可能發(fā)生插入和刪除45689靜態(tài)查找0K方法1：順序查找(數(shù)組存儲）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*/順序查找算法的時間復(fù)雜度為O(n)。710方法2：二分查找（Binary Search) 假設(shè)n個數(shù)據(jù)元素的關(guān)鍵字滿足有序（比如：小到大）并且是連續(xù)存放（數(shù)組），那么可以進(jìn)行二分查找。例 假設(shè)有13個數(shù)據(jù)元素，按關(guān)鍵字由小到大順序存放.二分查找關(guān)健字為444的數(shù)據(jù)元素過程如下：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; /*計算中間元素坐標(biāo)計算中間元素坐標(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;/*查找成功，返回數(shù)據(jù)元素的下標(biāo)查找成功

5、，返回數(shù)據(jù)元素的下標(biāo)*/*查找不成功，返回查找不成功，返回-1*/ 二分查找算法具有對數(shù)的時間復(fù)雜度O(logN)例 仍然以上面13個數(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個元素的二分查找判定樹 判定樹上每個結(jié)點(diǎn)需要的查找次數(shù)剛好為該結(jié)點(diǎn)所在的層數(shù); 查找成功時查找次數(shù)不會超過判39定樹的深度 n個結(jié)點(diǎn)的判定樹的深度14710為log2n+1. ASL = (4*4+4*3+2*2+1)/11 = 325811二分查找的啟示？LM4.2樹的定義樹（Tree）: n（n0）個結(jié)點(diǎn)構(gòu)成的有限集合。當(dāng)n=0時，稱為空樹；對于任一棵非空樹（n 0），它具備以下性質(zhì)： 樹中有一個稱為“根（Root）”的特殊結(jié)點(diǎn)，用 r 表示； 其余結(jié)點(diǎn)

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

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

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

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

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

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

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

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

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