6.1 樹狀結構的一些專有名詞 6.2 二元樹 6.3 二元樹的表示方法 6.4 二元樹的追蹤 6.5 引線二元樹 6.6 其它議題

Presentation on theme: "6.1 樹狀結構的一些專有名詞 6.2 二元樹 6.3 二元樹的表示方法 6.4 二元樹的追蹤 6.5 引線二元樹 6.6 其它議題"— Presentation transcript:

1 6.1 樹狀結構的一些專有名詞 6.2 二元樹 6.3 二元樹的表示方法 6.4 二元樹的追蹤 6.5 引線二元樹 6.6 其它議題
Chapter 6 樹狀結構 6.1 樹狀結構的一些專有名詞 6.2 二元樹 6.3 二元樹的表示方法 6.4 二元樹的追蹤 6.5 引線二元樹 6.6 其它議題

2 6.1 樹狀結構的一些專有名詞 我們利用圖6-1來說明樹的一些專有名詞。

3 6.1 樹狀結構的一些專有名詞 節點與邊：節點代表某項資料，而邊是指由一節點到另一節點的分支。如圖6-1有14個節點，其節點的資料是英文字母。 祖先(ancestor)節點與子孫(descendant)節點：若從節點X有一條路徑通往節點Y，則X是Y的祖先，Y是X的子孫。 父節點(parent node)與子節點(children node)：若節點X直接到節點Y，則稱X為Y的父節點，Y為X的子節點。

4 6.1 樹狀結構的一些專有名詞 兄弟節點(sibling node)：擁有相同父節點的子節點。
6.1 樹狀結構的一些專有名詞 兄弟節點(sibling node)：擁有相同父節點的子節點。 非終點節點(non-terminal node)：有子節點的節點。 終點節點(terminal node)或樹葉節點 (leaf node)：沒有子節點的節點稱為終點節點。

5 6.1 樹狀結構的一些專有名詞 分支度(degree)：一個節點的分支度是它擁有的子節點數。
6.1 樹狀結構的一些專有名詞 分支度(degree)：一個節點的分支度是它擁有的子節點數。 階度(level)：樹中節點世代的關係，一代為一個階度，樹根的階度為1。 高度(height)：樹中某節點的高度表示此節點，至樹葉節點的最長路徑 (Path)長度。 深度(depth)：某個節點的深度為樹根至此節點的路徑長度。

6 6.1 樹狀結構的一些專有名詞 樹林(forest)是由n個(n > 0)互斥樹(disjoint trees)所組合而成的，若移去樹根將形成樹林。 樹的表示方法除了以圖6-1表示外，亦可以(A(B(E(J), F(K, L)), C(G), D(H(M, N), I))來表示。

7 6.1 樹狀結構的一些專有名詞 由於每個節點分支度不一樣，所以儲存的欄位長度是變動的，為了能夠儲存所有節點起見，必須使用固定長度，即取決這棵樹那一節點所擁有的最多子節點數。因此節點的資料結構如下：

8 6.1 樹狀結構的一些專有名詞 假設有一棵k分支度的樹，總共有n個節點，那麼它需要nk個LINK欄位。
6.1 樹狀結構的一些專有名詞 假設有一棵k分支度的樹，總共有n個節點，那麼它需要nk個LINK欄位。 共用了n-1個LINK，造成了nk-(n-1)=nk-n+1個LINK浪費掉。估計大約有三分之二的LINK都是空的。由於此原因，所以將樹化為二元樹(binary tree)是有必要的。

9 6.2 二元樹 二元樹(binary tree)定義如下：二元樹是由節點所組成的有限集合，這個集合不是空集合就是由樹根、左子樹(left subtree)和右子樹(right subtree)所組成的。

10 6.2 二元樹 二元樹與一般樹不同的地方是： 二元樹的節點個數可以是零，而一般樹至少由一個節點所組成。
6.2 二元樹 二元樹與一般樹不同的地方是： 二元樹的節點個數可以是零，而一般樹至少由一個節點所組成。 二元樹有排列順序的關係，而一般樹則沒有。 二元樹中每一節點的分支度至多為2， 而一般樹無此限制。

11 6.2 二元樹 如圖6-2之(a)與(b)是不一樣的兩棵二元樹

12 6.2 二元樹 有一棵階度等於k的二元樹，若含有2k-1個節點數時，則稱之滿枝二元樹(fully binary tree)，如圖6-3之(c)。 若含有的節點數少於2k-1，而且節點排列的順序同滿枝二元樹，則稱之為完整二元樹(complete binary tree) 。

13 6.2 二元樹 有關二元樹的一些現象如下： 一棵二元樹在第i階度的最多節點數為 2i-1，i ≥ 1。
6.2 二元樹 有關二元樹的一些現象如下： 一棵二元樹在第i階度的最多節點數為 2i-1，i ≥ 1。 一棵階度(或深度)為k的二元樹，最多的節點數為2k-1，k ≥ 1。 一棵二元樹，若n0表示所有的樹葉節點， n2表示所有分支度為2的節點，則n0=n2+1。

14 6.2 二元樹 由於二元樹所有節點的分支度皆小於等於2，因此n=n0+n1+n2。
6.2 二元樹 由於二元樹所有節點的分支度皆小於等於2，因此n=n0+n1+n2。 除了樹根外每一節點皆有分支(branch)指向它本身，假若有B個分支個數，則n=B+1；每一分支皆由分支度為1或2的節點引出，所以B=n1+2n2，將它代入n=B+1 => n=n1+2n2+1。而n也等於n0+n1+n2 ， 故n0+n1+n2==n1+2n2+1∴n0 = n2+1，得証。

15 6.3 二元樹的表示方法 二元樹的節點儲存在一維陣列中呢？我們可以想像此二元樹為滿枝二元樹，第i階度具有2 i-1個節點，依此類推。
6.3 二元樹的表示方法 二元樹的節點儲存在一維陣列中呢？我們可以想像此二元樹為滿枝二元樹，第i階度具有2 i-1個節點，依此類推。 循序表示法，對完整二元樹或滿枝二元樹相當合適，其他的二元樹則會造成許多空間的浪費。

16 6.3 二元樹的表示方法

17 6.3 二元樹的表示方法 此時我們可以利用鏈結方式來解決這些問題，將每一節點劃分三個欄位，左鏈結(left link)以LLINK表示，資料(data)以DATA表示，右鏈結(right link)以RLINK表示。如圖6-5所示：

18 6.3 二元樹的表示方法 圖6-5每一節點的資料結構表示法將圖 6-3之(a)、(b)畫成圖6-6之(a)、(b)。

19 6.4 二元樹的追蹤 二元樹的追蹤(traversal)可分成三種： 中序追蹤(inorder)：先拜訪左子樹，然後拜訪樹根，再拜訪右子樹。
6.4 二元樹的追蹤 二元樹的追蹤(traversal)可分成三種： 中序追蹤(inorder)：先拜訪左子樹，然後拜訪樹根，再拜訪右子樹。 前序追蹤(preorder)： 先拜訪樹根，然後拜訪 左子樹，再拜訪右子樹。 後序追蹤(postorder)： 先拜訪左子樹，然後拜 訪右子樹，再拜訪樹根。

20 6.4 二元樹的追蹤 圖6-7以中序追蹤後資料排列是A/B%C*D+E，前序追蹤資料排列是+*/A%BCDE，而後序追蹤資料排列是ABC%/D*E+。

21 6.5 引線二元樹 一般而言，一個n節點的二元樹，共有2n個LINK欄位，實際上只用了n-1個，造成2n-(n-1)=n+1 個LINK欄位的浪費，為了充分利用這些空的LINK欄位，將空的LINK換成一種叫引線二元樹(thread binary tree)。 二元樹轉成引線二元樹只要先把二元樹以中序追蹤方式將資料排列好，然後把缺少左或右LINK的節點挑出，看看其相鄰的左、右節點，將這些節點的左、右LINK空欄位指向其相鄰的左、右節點。

22 6.5 引線二元樹

23 6.5 引線二元樹 圖6-8之(a)，節點E的相鄰左、右節點分別是B和A，因此E的左LINK指到B節點，而右LINK指到A節點。
6.5 引線二元樹 圖6-8之(a)，節點E的相鄰左、右節點分別是B和A，因此E的左LINK指到B節點，而右LINK指到A節點。 讀者會問那H節點的左LINK指到那裏，而G節點的右LINK又會指到那裏，回答這問題前，請看引線二元樹的資料結構，如下所示：

24 6.5 引線二元樹 當LBIT=1時，LLINK是正常指標。 當LBIT=0時，LLINK是引線。 當RBIT=1時，RLINK是正常指標。
6.5 引線二元樹 當LBIT=1時，LLINK是正常指標。 當LBIT=0時，LLINK是引線。 當RBIT=1時，RLINK是正常指標。 當RBIT=0時，RLINK是引線。

25 6.5 引線二元樹 假定所有引線二元樹都有一個開頭節點(head node)；此時圖6-8之(b)引線二元樹在記憶體內完整的表示如圖6-9。
6.5 引線二元樹 假定所有引線二元樹都有一個開頭節點(head node)；此時圖6-8之(b)引線二元樹在記憶體內完整的表示如圖6-9。 在圖6-9中節點H的LLINK和節點G的RLINK皆指向開頭節點。注意開頭節點沒有資料，而且開頭節點的RLINK指向它本身(RBIT永遠為1)。當各節點的LLINK或RLINK為1時，指向某一節點的指標是實線，否則為虛線。

26 6.5 引線二元樹

27 6.5 引線二元樹 引線二元樹的優點： 我們可以利用引線二元樹來追蹤任一節點中序後繼者(inorder successor) 。

28 6.5 引線二元樹 我們要將引線二元樹的所有節點以中序方式列出，則只要重覆呼叫insuc()即可，作法如下：

29 6.5 引線二元樹 除了可以追蹤引線二元樹中序後繼者，當然也可以追蹤引線二元樹的中序前行者，其作法如下：

30 6.5 引線二元樹 引線二元樹若要加入或刪除某一節點，則動作較一般二元樹慢，因為牽涉到引線的重排，下面我們來討論如何加入一節點於引線二元樹。

31 6.5 引線二元樹

32 6.5 引線二元樹

33 6.5 引線二元樹 假設有一棵引線二元樹如圖6-10之(a)與圖6-11(a)，若各自加入一節點T於節點S的右方，需考慮S節點的右方是實線或虛線，即rbit是1或0，圖形將變成如圖6-10之(b)與圖6-11之(b)，注意圖6-10之(a)的S指向節點3，而圖6-11之(a)的S指向節點2。

34 6.5 引線二元樹

35 6.6 其它議題 一般樹化為二元樹，其步驟如下： 將節點的所有兄弟(sibling)連接在一起。 把所有不是連到最左邊的子節點鏈結刪除。
6.6 其它議題 一般樹化為二元樹，其步驟如下： 將節點的所有兄弟(sibling)連接在一起。 把所有不是連到最左邊的子節點鏈結刪除。 順時針旋轉45度，如圖6-12(a)、(b)、 (c)所示。

36 6.6 其它議題

37 6.6 其它議題 樹林轉換為二元樹如圖6-13所示，其步驟如下： 先將樹林中的每棵樹化為二元樹(不旋 轉45度)。
6.6 其它議題 樹林轉換為二元樹如圖6-13所示，其步驟如下： 先將樹林中的每棵樹化為二元樹(不旋 轉45度)。 把所有二元樹的樹根節點全部鏈結在一起。 旋轉45度。

38 6.6 其它議題

39 6.6 其它議題 每一棵二元樹皆有唯一的一對中序與前序次序，也有唯一的中序與後序次序。換句話說，給予一對中序與前序或中序與後序即可決定一棵二元樹。然而給予前序和後序次序，並不能決定唯一的二元樹，可能會產生兩棵不同的二元樹。

40 6.6 其它議題 如給予中序次序是FDHGIBEAC，而前序次序是ABDFGHIEC。由前序次序知，A是樹根，且由中序次序知C是A的右子點。

41 6.6 其它議題 由前序知B是FDHGIE的父節點，並從中序次序知E是B的右子點。

42 6.6 其它議題 再由前序次序知D是FHGI的父節點，由中序知F是D的左子點，HGI是D的右子點。

43 6.6 其它議題 最後由前序次序知G是HI的父節點，並從中序次序知H是G的左子點，I是G的右子點。