樹狀結構導論(Tree).ppt

第六章　樹狀結構導論 6-1 樹 6-2 二元樹簡介 6-3 二元樹的儲存方式 6-4 二元樹的走訪 6-5 二元樹的進階研究 6-6 樹的二元樹表示法 樹 樹(tree)是一種特殊的資料結構，它可以用來描述有分支的結構，是由一個或一個以上的節點所組成的有限集合，且具有下列特質： 1.存在一個特殊的節點，稱為樹根(root)。 2.其餘的節點分為n?0個互斥的集合，T1,T2,T3…Tn，且每個集合稱為子樹。 接著再比較以下的兩個圖形： 上圖(a)是個合法的樹，符合樹是由一個或一個以上的節點所組成，節點間有連結且不形成無出口的迴圈。 圖(b)節點間不完全有連結且形成無出口迴圈，故不是一個合法的樹。 樹的專有名詞 樹的相關專有名詞。我們將以下的樹狀圖形為範本來為您說明： 樹根或根節點(root)：沒有父節點的節點為根節點，如上樹的根節點為A。 父節點(parent)：每一個節點的上層節點為父節點，如B的父節點為A，G的父節點為C。 子節點(children)：每一個節點的下層節點為子節點，如B的子節點有E及F，A的子節點有B、C、D。 兄弟節點(siblings)：有共同父節點的節點為兄弟節點，如B、C、D的父節點均為A，所以彼此為兄弟節點。 分支度(degree)：子樹的個數為該節點的分支度，如A的分支度為3，B的分支度為2。 終端節點或樹葉節點(terminal node)：沒有子節點的節點，即分支度為0的節點，例如EFGHD均為終端節點或樹葉。 非終端節點(non-terminal node)：樹葉以外的節點均為非終端節點，即分支度不為0的節點，如ABC均為非終端節點。 階層或階度(level)：樹的層級，假設樹根A為階層1，BCD節點即為階層2，EFGH為階層3。 高度(height)：樹的最大階度，例如此樹形圖的高度為3。 樹林(forest)：樹林是由n個互斥樹的集合(n?0)，移去樹根即為樹林。例如下圖為包含三樹的樹林。 祖先(ancestor)和子孫(decendent)：所謂祖先，是指從樹根到該節點路徑上所包含的節點，而子孫則是在該節點子樹中的任一節點。 範例 6.1.1 下列哪一種不是樹(Tree)？(A)一個節點(B)環狀串列(C)一個沒有迴路的連通圖(Connected Graph)(D)一個邊數比點數少1的連通圖。 範例 6.1.2 下圖中樹(tree)有幾個樹葉節點(leaf node)？(A)4(B)5(C)9(D)11 二元樹簡介 一般樹狀結構在電腦記憶體中的儲存方式是以鏈結串列(Linked List)為主。 對於n元樹(n-way樹)來說，因為每個節點的分支度都不相同，所以為了方便起見，我們必須取n為鏈結個數的最大固定長度，而每個節點的資料結構如下： 二元樹(Binary Tree)的定義 二元樹(又稱knuth樹)是一個由有限節點所組成的集合，此集合可以為空集合，或由一個樹根及左右兩個子樹所組成。 二元樹最多只能有兩個子節點，就是分支度小於或等於2。其電腦中的資料結構如下： 二元樹和一般樹不同之處 整理如下： 樹不可為空集合，但是二元樹可以。 樹的分支度為d≧0，但二元樹的節點分支度為0≦d≦2。 樹的子樹間沒有次序關係，二元樹則有。 建立二元樹必須遵守 左子樹的值一定完全小於樹根。 右子樹的值一定完全大於樹根。 底下就讓我們看一棵實際的二元樹，如下圖所示： 範例 6.2.1 試證明深度為k的二元樹的總節點數是2k-1。 範例 6.2.2 對於任何非空二元樹T，如果n0為樹葉節點數，且分支度為2的節點數是n2，試証明n0= n2+1。 範例 6.2.3 在二元樹中，階度(level)為i的節點數最多是 2i-1(i?0)，試證明之。 特殊二元樹簡介 完滿二元樹(Fully binary tree) 完整二元樹(Complete binary tree) 歪斜樹(skewed binary tree) 嚴格二元樹(strictly binary tree) 完滿二元樹(Fully binary tree) 如果二元樹的高度為h，樹的節點數為2h-1，h=0，則我們稱此樹為「完滿二元樹」(fully binary tree)，如下圖所示： 完整二元樹(Complete binary tree) 二元樹的深度為h，所含的節點數小於2h-1，但其節點的編號方式如同深度為h的完滿二元樹一般，從左到右，由上到下的順序一一對應結合。如下圖： 歪斜樹(skewed binary tree) 當一個二元樹完全沒有右節點或左節點時，我們就把它稱為左歪斜樹或右歪斜樹。 嚴格二元樹(strictly binary tree) 如果二元樹的每個非終端節點均有