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

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

3、-);return i; /*查找成功返回所在單元下標；不成功返回查找成功返回所在單元下標；不成功返回0*/順序查找算法的時間復雜度為O(n)。710方法2：二分查找（Binary Search) 假設n個數據元素的關鍵字滿足有序（比如：小到大）并且是連續存放（數組），那么可以進行二分查找。例 假設有13個數據元素，按關鍵字由小到大順序存放.二分查找關健字為444的數據元素過程如下：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; /*計算中間元素坐標計算中間元素坐標*/if( K Elementmid)right = mid-1; /*調整右邊界調整右邊界*/else if( K Tbl-Elementmid) left = mid+1;/*調整左邊界調整左邊界*/else return mid;return NotFound;/*查找成功，返回數據元素的下標查找成功

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

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

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

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

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

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

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

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

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

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