本教學投影片係屬教科書著作之延伸，亦受著作權法之保護。

Presentation on theme: "本教學投影片係屬教科書著作之延伸，亦受著作權法之保護。"— Presentation transcript:

1 本教學投影片係屬教科書著作之延伸，亦受著作權法之保護。
請依出版社授權使用規範利用本教學資源，非經授權許可不得以影印、拷貝、列印等方法進行重製，亦不得改作、公開展示著作內容，亦請勿對第三人公開傳輸、散布。 戴顯權 著 / 資料結構 © 滄海圖書

2 Chapter 5 樹狀結構 戴顯權 著 / 資料結構 © 滄海圖書

3 本章內容 5.1 樹狀結構簡介 5.2 二元樹 5.3 二元樹的儲存方式 5.4 把樹轉換成二元樹 5.5 建立算術運算之二元樹
5.1　樹狀結構簡介 5.2　二元樹 5.3　二元樹的儲存方式 5.4　把樹轉換成二元樹 5.5　建立算術運算之二元樹 5.7　二元樹走訪的兩個應用 範例 5.8　** 引線二元樹 5.9　堆積 5.10 二元搜尋樹 5.11 樹的應用 戴顯權 著 / 資料結構 © 滄海圖書

4 樹狀結構簡介 戴顯權 著 / 資料結構 © 滄海圖書

5 樹狀結構的定義 戴顯權 著 / 資料結構 © 滄海圖書

6 符合樹狀結構 戴顯權 著 / 資料結構 © 滄海圖書

7 不合法的樹狀結構 戴顯權 著 / 資料結構 © 滄海圖書

8 樹的基本名詞 戴顯權 著 / 資料結構 © 滄海圖書

9 分支度(degree) 某節點的子樹個數 degree(A) = 3 degree(C) = 1 戴顯權 著 / 資料結構 © 滄海圖書

10 樹葉(leaf) / 終端節點(terminal node)
在樹狀結構中分支 度為零的節點 戴顯權 著 / 資料結構 © 滄海圖書

11 父節點(parent) 與子節點互為相對的 關係，即其子節點的 上一層節點 節點B 之父節點為A 節點I 的父節點為D 節點K 的父節點為F
戴顯權 著 / 資料結構 © 滄海圖書

12 兄弟(sibling) 具有同一個父節點 的所有節點彼此都 稱為兄弟，一個節 點的兄弟可以有不 只一個 H、I、J 三個節點互 為兄弟
戴顯權 著 / 資料結構 © 滄海圖書

13 祖先(ancestor) 從樹根節點到此節 點之路徑上的所有 節點 節點I 的祖先有節點 A 與節點D
戴顯權 著 / 資料結構 © 滄海圖書

14 後代(descendant) 包含所有在它的子 樹裡的節點 戴顯權 著 / 資料結構 © 滄海圖書

15 階層(level) 以樹根節點所在的 位置為階層1，並 往下逐層遞增，以 此來定義每一個節 點的所在階層
戴顯權 著 / 資料結構 © 滄海圖書

16 高度(height) / 深度(depth)
為此樹中最大的階 層數 戴顯權 著 / 資料結構 © 滄海圖書

17 樹的表示法 戴顯權 著 / 資料結構 © 滄海圖書

18 二元樹 二元樹(binary tree) 是最常用到的樹狀結構 它的任一節點的分支度都不超過2 對二元樹來說，左子樹與右子樹是有分別的
一般的樹狀結構中，子樹的順序是無關緊要的 戴顯權 著 / 資料結構 © 滄海圖書

19 二元樹 樹與二元樹的不同 對於樹來說，不論節點B 是節點A 的左兒子或右兒子，指 的都是相同的樹
戴顯權 著 / 資料結構 © 滄海圖書

20 二元樹的特性 在二元樹的第i 階層上，單層最多的節點個數為2i – 1, i  1
戴顯權 著 / 資料結構 © 滄海圖書

21 戴顯權 著 / 資料結構 © 滄海圖書

22 完滿二元樹 完滿二元樹(full binary tree) 是一棵每一個階 層都擁有最大可能節 點數的二元樹，因此 這棵二元樹看起來整 個都長得滿滿的 戴顯權 著 / 資料結構 © 滄海圖書

23 完整二元樹 是把圖5.10 的T4 根據節點 編號由大而小地去掉兩個 節點(依序是O、N) 所得 到的結果
是一棵節點數少於2k – 1 且大於2k–1 – 1、深度為k 的二元樹，而且編號順序 與完滿二元樹一樣 戴顯權 著 / 資料結構 © 滄海圖書

24 歪斜二元樹 一棵二元樹，它所擁有的節 點都沒有左子樹或者都沒有 右子樹
如果所有的節點都只有左子 樹，我們就稱之為左歪斜二 元樹。如果都只有右子樹， 我們就稱之為右歪斜二元樹 特性就是每一階層都只有一 個節點；也就是其節點數恰 等於階層數 戴顯權 著 / 資料結構 © 滄海圖書

25 二元樹的儲存方式 陣列表示法 鏈結表示法 戴顯權 著 / 資料結構 © 滄海圖書

26 陣列表示法 是利用一個一維陣列來儲存二元樹 戴顯權 著 / 資料結構 © 滄海圖書

27 鏈結表示法 戴顯權 著 / 資料結構 © 滄海圖書

28 鏈結表示法 戴顯權 著 / 資料結構 © 滄海圖書

29 鏈結表示法 戴顯權 著 / 資料結構 © 滄海圖書

30 把樹轉換成二元樹 保留所有節點的最左鏈結，將其他鏈結全部刪除。 把原本樹中同屬於一個父節點的兄弟由左而右用鏈 結連接起來。
把整個圖形依順時鐘方向旋轉 45。 戴顯權 著 / 資料結構 © 滄海圖書

31 例題一 將圖5.18 的樹轉成二元樹 戴顯權 著 / 資料結構 © 滄海圖書

32 例題一 第1 步　 保留所有節點的最左鏈 結，其他鏈結都刪除 戴顯權 著 / 資料結構 © 滄海圖書

33 例題一 第2 步　 把原本樹裡同屬於一個父 節點的兄弟節點由左而右 用右鏈結連接起來 戴顯權 著 / 資料結構 © 滄海圖書

34 例題一 第3 步　 把整個圖形依順時鐘方 向旋轉 45 戴顯權 著 / 資料結構 © 滄海圖書

35 例題二 將圖5.19 的樹轉成二元樹 戴顯權 著 / 資料結構 © 滄海圖書

36 例題二 第1 步　 保留所有節點的最左鏈結， 並刪除其他的所有鏈結 戴顯權 著 / 資料結構 © 滄海圖書

37 例題二 第2 步　 把原本樹裡同屬於一個父 節點的兄弟節點由左而右 用鏈結連接起來 戴顯權 著 / 資料結構 © 滄海圖書

38 例題二 第3 步　 將整個圖形依順時鐘方 向旋轉45 戴顯權 著 / 資料結構 © 滄海圖書

39 把樹林轉成二元樹的方法 刪除所有節點之右鏈結，只留下最左鏈結。
把原本樹裡同屬於一個父節點的兄弟由左而右用鏈 結連接起來，同時也把所有樹根由左而右用鏈結連 接起來。 把整個圖形依順時鐘方向旋轉45。 戴顯權 著 / 資料結構 © 滄海圖書

40 例題三 將圖5.20 的三棵樹轉換成一棵二元樹 戴顯權 著 / 資料結構 © 滄海圖書

41 例題三 第1 步　 保留每一個節點的最左鏈結，並且刪除其他的所有鏈結 戴顯權 著 / 資料結構 © 滄海圖書

42 例題三 第2 步 把原本樹中屬於同一個父節點的兄弟節點用右鏈結由左而 右連接起來，同時也把三個樹根由左而右用右鏈結連接起 來
第2 步　 把原本樹中屬於同一個父節點的兄弟節點用右鏈結由左而 右連接起來，同時也把三個樹根由左而右用右鏈結連接起 來 戴顯權 著 / 資料結構 © 滄海圖書

43 例題三 第3 步　 把整個圖形依順時鐘方 向旋轉45 戴顯權 著 / 資料結構 © 滄海圖書

44 建立算術運算之二元樹 考慮運算子的優先次序與結合性，適當地予以加入 括號。
從最內層的括號逐次向外處理，以運算子為樹根， 左運算元做為左子樹，右運算元做為右子樹。 戴顯權 著 / 資料結構 © 滄海圖書

45 例題四 例題四替算術式A*B+C**D–E 建立二元樹 我們要替算術式A*B+C**D–E 建立二元樹， 其中** 表示冪次方的符號
戴顯權 著 / 資料結構 © 滄海圖書

46 例題四 先按照運算子的優先權與結合性予以適當地加上括 號，得到(((A*B)+(C**D))–E)。上式中優先權最高的 為C**D 與A*B，先將它們以運算子為樹根分別建成 兩棵二元樹 戴顯權 著 / 資料結構 © 滄海圖書

47 例題四 當碰到相同的優先權時，我們採用左結合性，因此 我們接著建立((A*B)+(C**D)) 的二元樹
戴顯權 著 / 資料結構 © 滄海圖書

48 例題四 最後，我們再把(((A*B)+(C**D))–E) 也加到二元樹上 戴顯權 著 / 資料結構 © 滄海圖書

49 例題五 將(((A/(B**C)+(D*E))– (A*C)) 表示成算術運算二 元樹
戴顯權 著 / 資料結構 © 滄海圖書

50 二元樹之走訪 在樹狀結構上可以執行許多種運算，其中最常用到 的一種是走訪樹狀結構(traversing a tree)，即走訪完 樹中的每一個節點，並且每個節點都恰好走訪一次 右子樹(R) 左子樹(L) 成樹根(D) 戴顯權 著 / 資料結構 © 滄海圖書

51 二元樹之走訪 一棵二元樹的方式就根據走訪順序不同而分成三種：
先走訪左子樹，然後走訪樹根，最後再走訪右子樹(LDR) 的中序走訪法(inorder traversal) 先走訪樹根，接著走訪左子樹，最後再走訪右子樹(DLR) 的前序走訪法(preorder traversal) 先走訪左子樹，然後右子樹，最後再走訪樹根(LRD) 的 後序走訪法 (postorder traversal) 戴顯權 著 / 資料結構 © 滄海圖書

52 中序走訪法 如果樹根節點不是空節點，那麼執行下列的步驟： (遞迴地) 走訪左子樹。 輸出樹根。 (遞迴地) 走訪右子樹。
戴顯權 著 / 資料結構 © 滄海圖書

53 例題六 利用中序走訪法來走 訪圖5.26 的二元樹 戴顯權 著 / 資料結構 © 滄海圖書

54 例題六 第1 步　 把圖5.26 的二元樹分 割成樹根、左子樹， 以及右子樹三個部分 戴顯權 著 / 資料結構 © 滄海圖書

55 例題六 第2 步 　 先將圖5.26(a) 的左子樹放大來 看，並且同樣地把它分成樹根 (其值為“ – ” 的節點)、左子樹， 以及右子樹三個部分 戴顯權 著 / 資料結構 © 滄海圖書

56 例題六 第3 步 把圖5.26(b) 的左子樹放大來看 左子樹只有一個A 節點，因此 我們直接輸出“A” 再來直接輸出的樹根“ + ”
接著看到右子樹 戴顯權 著 / 資料結構 © 滄海圖書

57 例題六 第4 步 圖5.26(c) 的右子樹同樣分割成 左子樹、樹根，與右子樹三個 部分
圖5.26(d) 的左子樹只是一個節 點，因此立即輸出“B”，接著 輸出樹根“ * ”。最後由於右 子樹只有一個節點“C ”，因 此直接輸出“C ” 戴顯權 著 / 資料結構 © 滄海圖書

58 例題六 第5 步 到這裡我們已經把圖5.26(b) 的左子樹全部都走訪過了 接著就可以走訪圖5.26(b) 的樹根，即輸出“ – ”
然後再輸出圖5.26(b) 的右子樹，即輸出“D” 戴顯權 著 / 資料結構 © 滄海圖書

59 例題六 第6 步 到這裡我們已經把圖5.26(a) 的左子樹整個走訪完了，現 在可以輸出圖5.26(a) 的樹根“ + ”
第6 步　 到這裡我們已經把圖5.26(a) 的左子樹整個走訪完了，現 在可以輸出圖5.26(a) 的樹根“ + ” 再看圖5.26(a) 的右子樹並且同樣地把它分割成三個部分 戴顯權 著 / 資料結構 © 滄海圖書

60 例題六 第7 步　 這時圖5.26(e) 裡的左子樹只是一個節點，因此立即輸出 圖5.26(e) 的左子樹“E ”，緊接著輸出樹根“/ ”；然後我 們看到右子樹也只是一個節點，因此立即輸出節點“F ” 至此，我們已經把整棵二元樹裡的每個節點都走訪過了， 所得到的輸出結果是：A+B*C–D+E/F，是這個算術運算 式的中置表示法(infix expression) 戴顯權 著 / 資料結構 © 滄海圖書

61 例題六 戴顯權 著 / 資料結構 © 滄海圖書

62 前序走訪法 如果樹根節點不是空節點，那麼執行下列步驟： 輸出樹根。 (遞迴地) 走訪左子樹。 (遞迴地) 走訪右子樹。
戴顯權 著 / 資料結構 © 滄海圖書

63 例題七 例題七利用前序走訪法來 走訪圖5.27 (同圖5.26) 的 二元樹 戴顯權 著 / 資料結構 © 滄海圖書

64 例題七 第1 步　 把圖5.27 的二元樹區分 為樹根、左子樹，以及 右子樹三個部分 戴顯權 著 / 資料結構 © 滄海圖書

65 例題七 第2 步 前序走訪法要先輸出樹根， 因此直接輸出“ + ”
第2 步　 前序走訪法要先輸出樹根， 因此直接輸出“ + ” 接著走訪左子樹，我們先把 圖5.27(a) 的左子樹放大來看， 並且類似地把它分成樹根(其 值為“ – ” 的節點)、左子樹， 以及右子樹三個部分 戴顯權 著 / 資料結構 © 滄海圖書

66 例題七 第3 步 輸出樹根節點“ – ”，再把圖 5.27(b) 的左子樹放大來看， 接下來我們直接輸出這個再分 割後的樹根節點“ + ”
第3 步　 輸出樹根節點“ – ”，再把圖 5.27(b) 的左子樹放大來看， 接下來我們直接輸出這個再分 割後的樹根節點“ + ” 5.27(c) 的左子樹只剩下一個節 點，因此我們直接將該節點的 值“A”輸出 戴顯權 著 / 資料結構 © 滄海圖書

67 例題七 第4 步 接著看圖5.27(c) 的右子樹 圖5.27(c) 的右子樹同樣地可以分成 左子樹、樹根，以及右子樹三個部 分
第4 步　 接著看圖5.27(c) 的右子樹 圖5.27(c) 的右子樹同樣地可以分成 左子樹、樹根，以及右子樹三個部 分 首先，輸出樹根節點“ * ” 由於圖5.27(d) 的左子樹只有一個節 點，因此直接輸出“B” 我們也直接輸出右子樹的節點“C ” 戴顯權 著 / 資料結構 © 滄海圖書

68 例題七 第5 步 第6 步 接著我們走訪圖5.27(b) 的右子樹 由於該右子樹中僅含一個節點， 因此直接輸出樹根節點“D”
第5 步　 接著我們走訪圖5.27(b) 的右子樹 由於該右子樹中僅含一個節點， 因此直接輸出樹根節點“D” 第6 步　 現在再看圖5.27(a) 的右子樹，並 且同樣把它分成三個部分 戴顯權 著 / 資料結構 © 滄海圖書

69 例題七 第7 步 輸出圖5.27(e) 中的樹根節點“ / ”，由於其左子樹只有一 個節點，因此立即輸出節點“E ”
第7 步　 輸出圖5.27(e) 中的樹根節點“ / ”，由於其左子樹只有一 個節點，因此立即輸出節點“E ” 然後我們看到右子樹也只有一個節點，因此直接輸出節點 “F ” 這時候我們已經把整棵二元樹中的每個節點都走訪過了， 所得到的輸出結果為：+–+A*BCD/EF，這正是這個算術 運算式的前置表示法(prefix expression) 戴顯權 著 / 資料結構 © 滄海圖書

70 例題七 戴顯權 著 / 資料結構 © 滄海圖書

71 後序走訪法 如果樹根節點不是空節點，那麼執行下列步驟： (遞迴地) 走訪左子樹。 (遞迴地) 走訪右子樹。 輸出樹根。
戴顯權 著 / 資料結構 © 滄海圖書

72 例題八 利用後序走訪法來走訪 圖5.26 的二元樹 戴顯權 著 / 資料結構 © 滄海圖書

73 例題八 第1 步 把圖5.28 (同圖5.26) 的 二元樹區分為樹根、左 子樹，以及右子樹三個 部分
第1 步　 把圖5.28 (同圖5.26) 的 二元樹區分為樹根、左 子樹，以及右子樹三個 部分 戴顯權 著 / 資料結構 © 滄海圖書

74 例題八 第2 步　 由於後序走訪法得先走訪 左子樹，我們因此先將焦 點放在圖5.28(a)的左子樹， 並且同樣地把它分成樹根 (其值為“ – ” 的節點)、 左子樹，以及右子樹三個 部分 戴顯權 著 / 資料結構 © 滄海圖書

75 例題八 第3 步 再來仔細觀察5.28(b) 的左子 樹，如圖5.28(c) 所示
第3 步　 再來仔細觀察5.28(b) 的左子 樹，如圖5.28(c) 所示 經過再一次的分割，這時候圖 5.28(c) 的左子樹只剩下一個 節點，因此我們直接輸出它的 值“A” 接著我們看圖5.28(c) 的右子 樹 戴顯權 著 / 資料結構 © 滄海圖書

76 例題八 第4 步 把圖5.28(c) 的右子樹同樣地分成 左子樹、樹根，以及右子樹三個 部分，其結果如圖5.28(d) 所示
第4 步　 把圖5.28(c) 的右子樹同樣地分成 左子樹、樹根，以及右子樹三個 部分，其結果如圖5.28(d) 所示 圖5.28(d) 的左子樹只有一個節點， 因此直接輸出“B” 接下來直接輸出右子樹的節點 “C ” 最後回頭輸出樹根“ * ” 戴顯權 著 / 資料結構 © 滄海圖書

77 例題八 第5 步 第6 步 接著我們走訪並且輸出圖5.28(c) 的樹根“ + ” 然後我們輸出圖5.28(b) 的右子樹中唯一的節點“D”
第5 步　 接著我們走訪並且輸出圖5.28(c) 的樹根“ + ” 然後我們輸出圖5.28(b) 的右子樹中唯一的節點“D” 再走訪圖5.28(b) 的樹根“ – ”，即輸出“ – ” 第6 步　 是再看圖5.28(a)的右子樹， 並同樣把它分成三個部分 戴顯權 著 / 資料結構 © 滄海圖書

78 例題八 第7 步 由於圖5.28(e) 的左子樹只有一個節點，我們因此可以立 即輸出“E ”
第7 步　 由於圖5.28(e) 的左子樹只有一個節點，我們因此可以立 即輸出“E ” 然後我們看到右子樹也只有一個節點，因此直接輸出“F ” 緊接著輸出樹根“ / ” 最後，我們便可以輸出圖5.28(a) 的樹根“ + ” 了 到這裡我們已經把整棵二元樹裡的每個節點都走訪過了， 所得到的輸出結果為：ABC*+D–EF/+，這正是這個算術 運算式的後置表示法(postfix expression) 戴顯權 著 / 資料結構 © 滄海圖書

79 例題八 戴顯權 著 / 資料結構 © 滄海圖書

80 階層式走訪法 戴顯權 著 / 資料結構 © 滄海圖書

81 戴顯權 著 / 資料結構 © 滄海圖書

82 戴顯權 著 / 資料結構 © 滄海圖書

83 二元樹走訪的兩個應用範例 複製二元樹 測試兩棵二元樹是否相等 戴顯權 著 / 資料結構 © 滄海圖書

84 複製二元樹 戴顯權 著 / 資料結構 © 滄海圖書

85 測試兩棵二元樹是否相等 戴顯權 著 / 資料結構 © 滄海圖書

86 **引線二元樹 以指向樹中其他節點的指標來取代NULL 鏈結，這種 鏈結稱為引線(thread)
把每一個在一般二元樹中指向NULL 的鏈結取代以一 個引線，這樣的一棵二元樹就稱為引線二元樹 (thread binary tree) 戴顯權 著 / 資料結構 © 滄海圖書

87 引線二元樹 對每一個節點V 來說，如果節點V 的左鏈結指向 NULL，那麼把這個鏈結改成指向節點V 的中序前 行者(inorder predecessor)，亦即指向中序走訪時在 節點V之前拜訪的節點 對每一個節點V 來說，如果節點V 的右鏈結指向 NULL，那麼把這個鏈結改成指向節點V 的中序後 繼者(inorder successor)，亦即指向中序走訪時在節 點V 之後拜訪的節點 戴顯權 著 / 資料結構 © 滄海圖書

88 引線二元樹 戴顯權 著 / 資料結構 © 滄海圖書

89 引線二元樹 圖5.30 所示的二元樹加 上引線後的結果表為如 圖5.31 所示，其中圖 5.30 的中序走訪順序為： HDIBEAFCG
戴顯權 著 / 資料結構 © 滄海圖書

90 引線二元樹 要把引線二元樹儲存在記憶體裡，我們必須要能夠 區分引線與一般正常的鏈結；我們因此在節點的構 造中加入兩個欄位：left_thread 與right_thread 戴顯權 著 / 資料結構 © 滄海圖書

91 引線二元樹 戴顯權 著 / 資料結構 © 滄海圖書

92 引線二元樹 在圖5.31 中有兩個引線沒有指到任何地方，分別是 節點H 的左引線以及節點G 的右引線
對於一棵空的引線樹，它的首節點之data欄位並不包 含任何資料；同時它的right_child 指標指向它自己， 而且right_thread欄位的值設為FALSE；至於left_child 指標雖然也指向它自己，但是left_thread 欄位的值設 為TRUE 戴顯權 著 / 資料結構 © 滄海圖書

93 引線二元樹 一旦在這棵空的引線樹有了新加入節點，那麼 left_thread 欄位將變更為FALSE，同時left_child 也將 由引線改變成指向樹根節點的一般鏈結 戴顯權 著 / 資料結構 © 滄海圖書

94 引線二元樹 戴顯權 著 / 資料結構 © 滄海圖書

95 引線二元樹的中序走訪法 當引線二元樹做中序走訪時，沿著左邊的鏈結一直找下 去，直到碰到一個沒有左鏈結的節點時便輸出該節點為 第一個中序節點，接著直接利用它的右邊引線找出下一 個中序後繼者。不需要使用堆疊做推入與擠出的運算 當一個節點的right_thread 欄位為TRUE 時，那麼根據引 線的定義，節點的中序後繼者就是right_child 所指向的 節點；而當一個節點的right_thread 欄位為FALSE 時， 它的中序後繼者可以沿著節點的右子節點之左鏈結路徑 找，直到遇見一個left_thread 為TRUE 的節點便是 戴顯權 著 / 資料結構 © 滄海圖書

96 戴顯權 著 / 資料結構 © 滄海圖書

97 戴顯權 著 / 資料結構 © 滄海圖書

98 在引線二元樹中插入節點 因此時的child 節點插入到引 線二元樹後將成為終端節點 (樹葉)，故其left_child與 right_child 都是引線，而非一 般的鏈結，所以我們先做如 下設定： child->left_thread=TRUE; child->right_thread=TRUE; 戴顯權 著 / 資料結構 © 滄海圖書

99 child->left_child=parent;
在引線二元樹中插入節點 把child 插入到parent 的右子 節點後，child 的中序前行 者變成節點parent，如圖 5.35(a) 所示，其中鏈結的設 定如下： child->left_child=parent; 戴顯權 著 / 資料結構 © 滄海圖書

100 child->right_child=parent- >right_child;
在引線二元樹中插入節點 child 的中序後繼者是原來 parent 的中序後繼者，如 圖5.35(b) 所示，其中鏈結 的設定如下： child->right_child=parent- >right_child; 戴顯權 著 / 資料結構 © 滄海圖書

101 parent-> right_thread =FALSE;
在引線二元樹中插入節點 由於parent 節點的右兒子變成child 節點，因此 parent 節點的right_child 是一般的鏈結而非引線。 必須將其設定如下： parent-> right_thread =FALSE; 戴顯權 著 / 資料結構 © 滄海圖書

102 parent->right_child = child;
在引線二元樹中插入節點 最後，把parent 的右鏈結 指向child 即完成插入運 算，其結果如圖5.35(c) 所示，其中鏈結的設定如 下： parent->right_child = child; 戴顯權 著 / 資料結構 © 滄海圖書

103 在引線二元樹中插入節點 戴顯權 著 / 資料結構 © 滄海圖書

104 在引線二元樹中插入節點 戴顯權 著 / 資料結構 © 滄海圖書

105 引線二元樹 優點： 缺點： (1) 減少鏈結的浪費。 (2) 不用做中序走訪就可以找出任一節點的中序後繼者。
(3) 做中序走訪時，不需用到堆疊。 缺點： (1) 加入或刪除節點較慢。 (2) 每個節點多用兩個旗標欄位(flag，在此各用了一個位元 組) 來表示鏈結是否為引線。 戴顯權 著 / 資料結構 © 滄海圖書

106 堆積 堆積(heaps) 是完整二元樹的一種特別形式，它有兩 種型態： 最大堆積(max heap) 最小堆積(min heap)
戴顯權 著 / 資料結構 © 滄海圖書

107 最大樹 它是一棵樹，且每一個節點 的鍵值都不小於其子節點(如 果有的話) 的鍵值 最大堆積不僅是最大樹，而 且是完整二元樹
戴顯權 著 / 資料結構 © 滄海圖書

108 最小樹 它是一棵樹，且每一個節點 的鍵值都不大於它的子節點 (如果有的話) 的鍵值 最小堆積不僅是最小樹，而 且是完整二元樹
戴顯權 著 / 資料結構 © 滄海圖書

109 不合法的堆積 樹根節點值為29，而它的左 子節點值為大於樹根的45， 所以該樹只可能為最小堆積
樹根的右子節點值卻為小於 樹根的26，所以也不符合最 小堆積的條件，因此這棵二 元樹並不是一個堆積 戴顯權 著 / 資料結構 © 滄海圖書

110 不合法的堆積 其第四層由左向右列舉的 第四個位子(應為上一層節 點值29 的右子節點處) 是 空的，但第五個位子以後 卻又有其他節點，可見這 棵二元樹並不是一棵完整 二元樹，這同樣違反了堆 積的定義，因此也不是一 個合法的堆積 戴顯權 著 / 資料結構 © 滄海圖書

111 堆積的應用—優先權佇列 戴顯權 著 / 資料結構 © 滄海圖書

112 堆積的運算 1. 建立空的堆積。 2. 插入新的元素到堆積裡。 3. 從堆積中刪除最大元素。 戴顯權 著 / 資料結構 © 滄海圖書

113 在堆積中加入元素 假設我們現在要把1、5、21 三個值依序插入到圖5.40(a) 的最大堆積裡 戴顯權 著 / 資料結構 © 滄海圖書

114 在堆積中加入元素 首先，我們插入1 第一個步驟是先把1 這個值放 到串列的最後一個位子
第二個步驟是把1 這個值跟它 的父節點2 比較，如果這個值 大於它父節點的值就把這兩個 節點值交換 戴顯權 著 / 資料結構 © 滄海圖書

115 在堆積中加入元素 在這一次由於1 小於2，不 需要做交換，插入1 的工作 因此已經完成 接著插入元素5
同樣地，我們把它加入到 堆積的最後一個位置 戴顯權 著 / 資料結構 © 滄海圖書

116 在堆積中加入元素 接著跟它的父節點做比較， 由於5 大於2，因此必須做 交換 我們把5 和2 兩個值做交換
戴顯權 著 / 資料結構 © 滄海圖書

117 在堆積中加入元素 再把5 跟它的父節點20 做 比較。由於5 小於20，不 必做交換，插入元素5 的 工作因此已經完成
接下來，我們要插入元素 21 我們把21 加到堆積的最 後一個位置 戴顯權 著 / 資料結構 © 滄海圖書

118 在堆積中加入元素 把21 跟它的父節點比較， 21 > 14，因此把兩個值 交換 戴顯權 著 / 資料結構 © 滄海圖書

119 在堆積中加入元素 21 再跟15 比較，21 > 15，因此把兩個值交換 戴顯權 著 / 資料結構 © 滄海圖書

120 在堆積中加入元素 把21 跟20 做比較，21 > 20， 因此把21 移到樹根，插入21 的工作至此已經完成
把21 跟20 做比較，21 > 20， 因此把21 移到樹根，插入21 的工作至此已經完成 戴顯權 著 / 資料結構 © 滄海圖書

121 在堆積中加入元素 戴顯權 著 / 資料結構 © 滄海圖書

122 在堆積中加入元素 戴顯權 著 / 資料結構 © 滄海圖書

123 在堆積中加入元素 戴顯權 著 / 資料結構 © 滄海圖書

124 從堆積中刪除元素 我們要把20 移除 戴顯權 著 / 資料結構 © 滄海圖書

125 從堆積中刪除元素 然後把堆積裡的最後一個元 素10 放到樹根的地方，並 且刪除最後一個元素 戴顯權 著 / 資料結構 © 滄海圖書

126 從堆積中刪除元素 由於違反了最大堆積的定義， 因此必須向下做調整 此時樹根的左、右子節點中比 較大的是15，把樹根的值10 跟15 做比較
此時樹根的左、右子節點中比 較大的是15，把樹根的值10 跟15 做比較 由於15 > 10，因此把這兩個 值交換 戴顯權 著 / 資料結構 © 滄海圖書

127 從堆積中刪除元素 10 再跟14 比較 由於14 > 10，因此這兩個 值再交換 戴顯權 著 / 資料結構 © 滄海圖書

128 戴顯權 著 / 資料結構 © 滄海圖書

129 戴顯權 著 / 資料結構 © 滄海圖書

130 二元搜尋樹的條件 二元搜尋樹(binary search tree) 是一種很適合於做搜 尋運算的二元樹
它可能是空的，如果不是空的，它具有下列特性： 每一個節點恰有一個鍵值，且每一個節點的鍵值都不相 同，即鍵值是唯一的。 任何一個節點的鍵值都大於它的左子樹裡所有節點之鍵 值。 任何一個節點的鍵值都小於它的右子樹裡所有節點之鍵 值。 任何一個節點的左子樹與右子樹也都是二元搜尋樹。 戴顯權 著 / 資料結構 © 滄海圖書

131 二元搜尋樹 戴顯權 著 / 資料結構 © 滄海圖書

132 建立一棵二元搜尋樹 假設現在我們要替一組資料D、K、Q、F、A、P、C、 B 建立一棵二元搜尋樹 一開始我們以D 做為樹根
戴顯權 著 / 資料結構 © 滄海圖書

133 建立一棵二元搜尋樹 K 的ASCII 碼大於D 的ASCII 碼，因此把K 弄成是D 的右兒子 戴顯權 著 / 資料結構 © 滄海圖書

134 建立一棵二元搜尋樹 Q 比D 大，因此應該放在D 的右邊，而Q 又比K 大， 因此放入K 的右邊成為K 的右兒子
戴顯權 著 / 資料結構 © 滄海圖書

135 建立一棵二元搜尋樹 戴顯權 著 / 資料結構 © 滄海圖書

136 建立一棵二元搜尋樹 戴顯權 著 / 資料結構 © 滄海圖書

137 建立一棵二元搜尋樹 戴顯權 著 / 資料結構 © 滄海圖書

138 建立一棵二元搜尋樹 戴顯權 著 / 資料結構 © 滄海圖書

139 建立一棵二元搜尋樹 戴顯權 著 / 資料結構 © 滄海圖書

140 搜尋一棵二元搜尋樹 要找出鍵值為key 的元素。我們從樹根節點開始，首 先比較key與樹根節點裡的鍵值，如果相等則搜尋成 功並且結束
反之，則尋找樹根節點的右子樹 戴顯權 著 / 資料結構 © 滄海圖書

141 搜尋一棵二元搜尋樹 假設要在圖中搜尋樹裡尋找鍵 值為5 的節點
首先，我們先把5 跟樹根的鍵值 做比較，5 < 30，因此搜尋樹根 的左子樹 再比較發現5 = 5，因此成功地 搜尋到鍵值為5 的節點 戴顯權 著 / 資料結構 © 滄海圖書

142 搜尋一棵二元搜尋樹 假設要在圖中搜尋樹裡尋找鍵 值為8 的節點，我們先把8 跟樹 根的鍵值做比較，8 < 30，因此 搜尋樹根的左子樹
再比較發現8 > 5，因此尋找鍵 值為5 的節點的右子樹 其右子樹是空的，因此找不到 鍵值為8 的節點，搜尋結束並且 確定沒有鍵值為8 的節點 戴顯權 著 / 資料結構 © 滄海圖書

143 搜尋一棵二元搜尋樹 戴顯權 著 / 資料結構 © 滄海圖書

144 加入元素到二元搜尋樹 假設我們要在圖 (8)中加入一 筆資料E，那麼我們必須先 確定E 並不在這棵二元搜尋 樹中
戴顯權 著 / 資料結構 © 滄海圖書

145 加入元素到二元搜尋樹 最後一個被檢查到的節點 是F E < F，因此E 會被當作是 F 節點的左子節點
戴顯權 著 / 資料結構 © 滄海圖書

146 戴顯權 著 / 資料結構 © 滄海圖書

147 戴顯權 著 / 資料結構 © 滄海圖書

148 戴顯權 著 / 資料結構 © 滄海圖書

149 從二元搜尋樹中移除元素 如果該節點是一個樹葉節點， 即沒有子節點，那麼把該節 點直接去掉即可，不必做其 他處理。 例如，要把P 節點刪除
直接刪除後的結果如圖 (a)所示 戴顯權 著 / 資料結構 © 滄海圖書

150 從二元搜尋樹中移除元素 如果該節點只有一個子節點，並且 有一個父節點(不是樹根節點)，那 麼把它的父節點直接連到它的子節 點，並且把該節點去掉即可 例如，要刪除C 節點，我們只需要把 節點A 的右子節點改成節點B 即可 如果該節點沒有父節點，那麼該節點 為樹根節點，而且只有一個子節點， 因此只需要把子節點變成樹根節點即 可 戴顯權 著 / 資料結構 © 滄海圖書

151 從二元搜尋樹中移除元素 如果要刪除的節點有兩個子節點， 那麼找出它的左子樹中具有最大鍵 值的節點，或者是右子樹中含有最 小鍵值的節點，把要刪除的節點鍵 值跟剛剛選出的節點鍵值對調，再 去掉剛剛選出的節點即可 例如，要刪除圖的節點D，首先我們選 擇取代節點D 的是左子樹裡的最大鍵 值節點C，兩個鍵值交換後再刪除原來 為C、現在是D 的這個節點 戴顯權 著 / 資料結構 © 滄海圖書

152 從二元搜尋樹中移除元素 由於這個節點只有一個子節點，因 此我們就把這個問題轉變成要刪除 有一個子節點的節點的問題
因此可以根據上述第2 點的規則來做 刪除 刪除後的結果如圖(c) 所示 戴顯權 著 / 資料結構 © 滄海圖書

153 從二元搜尋樹中移除元素 如果選擇的是右子樹裡的最小值， 那麼選擇到的節點是E，把E 跟D 交 換，再刪除D
那麼問題變成了刪除樹葉節點的問 題，我們因此可以根據上述第1 點的 規則來刪除樹葉節點 其最後結果如圖(d) 所示 戴顯權 著 / 資料結構 © 滄海圖書

154 霍夫曼編碼 霍夫曼編碼的第一個步驟是根據所有可能符號的出 現機率建立一棵霍夫曼樹
建立霍夫曼樹的過程很簡單，首先，我們先把每個 符號攤開，成為霍夫曼樹的樹葉 這些樹葉將經由下列的演算法接成一棵樹 附在每一個樹葉的是每個符號的出現頻率或機率， 並且當作該樹葉的加權值(weight) 戴顯權 著 / 資料結構 © 滄海圖書

155 霍夫曼編碼 戴顯權 著 / 資料結構 © 滄海圖書

156 霍夫曼編碼 假設現在有一份文件，其字元符號的出現次數為： 我們以出現次數來表示其機率值，則這五個符號分 別為霍夫曼樹之樹葉，也是一開始的自由節點 戴顯權 著 / 資料結構 © 滄海圖書

157 霍夫曼編碼 首先，在第一個循環裡，我們找出D、E 為加權值最 小的兩個自由節點(選擇C、E 也可以)
這兩個節點由一個新生的父親節點取代。把父親節 點加入自由節點串列，其加權值為6 + 5 = 11 D、E 則從自由節點串列中除名 戴顯權 著 / 資料結構 © 滄海圖書

158 霍夫曼編碼 一旦這個步驟完成，我們便已經知道D 與E 最後編碼 完成時它們的碼的最後一個位元是什麼
在從父親節點到D 的樹枝上標0，從父親節點到E 的 樹枝上標1，這兩個位元將分別是D 與E 的霍夫曼碼 的LSB (least significant bit) 戴顯權 著 / 資料結構 © 滄海圖書

159 霍夫曼編碼 在下一個循環中，加權值最小的兩個節點是B 與C。 把這兩個節點連接到另外一個新生父親節點，並且 從自由節點串列中除名
父親節點則加入成為新的自由節點，其加權值為 = 13 戴顯權 著 / 資料結構 © 滄海圖書

160 霍夫曼編碼 在下一個循環裡，加權值最小 的兩個自由節點為D 與E 的父 親節點以及B 與C 的父親節點
新生的父親節點則加入成為自 由節點，其加權值為 = 24 24 戴顯權 著 / 資料結構 © 滄海圖書

161 霍夫曼編碼 最後，只剩下兩個自由節 點，我們新產生一個父親 節點，即最後的樹根，把 這兩個節點連接起來
新生的父親節點其加權值 為39，是剩下的唯一一個 自由節點，表示演算法已 經完成 戴顯權 著 / 資料結構 © 滄海圖書

162 霍夫曼編碼 要知道某一個符號的霍夫曼碼，我們 必須從該符號所屬的樹葉走到樹根， 並且列舉這個路徑上所經過的位元
我們需要一個堆疊，在從樹葉走向樹 根的過程中把所碰到的位元依序推入 堆疊內，並且在到達樹根後把堆疊內 的位元依序彈出來。如此我們才可以 得到所想要符號的霍夫曼碼 戴顯權 著 / 資料結構 © 滄海圖書

163 霍夫曼編碼 假設我們現在有一張八種灰階度(gray-levels) 的影像 戴顯權 著 / 資料結構 © 滄海圖書

164 霍夫曼編碼 使用的是上表中的霍夫曼碼，那麼每一個像素的平 均編碼位元數減為： 戴顯權 著 / 資料結構 © 滄海圖書

165 四分樹 四分樹(quadtree) 就是一種把資料根據所在位置分割 成四個部分的樹狀結構，它尤其在二維的數位影像 處理上應用最廣
所謂的四分樹就是把二維平面資料分割成等大小的 四個部分，每一部分就是一個子節點；每一部分可 以根據需要再繼續分割成四個部分，亦即每個子節 點又分下去成為四個更小的子節點，以此類推 戴顯權 著 / 資料結構 © 滄海圖書

166 四分樹的結構 圖5.48 所示的是一個二維 平面上的點資料，我們希 望能夠把這些點用四分樹 結構記錄下來
戴顯權 著 / 資料結構 © 滄海圖書

167 四分樹的結構 首先，我們把整個平面分割 成四等份，並且依序把(1)、 (2)、(3)、(4) 四部分做為子 節點
其中每一個節點上有一個單 位元的值，稱為該節點的狀 態值，狀態值為1 表示這個 節點所代表的區域要再分割 下去，而0則表示不再做分 割 戴顯權 著 / 資料結構 © 滄海圖書

168 四分樹的結構 接著，我們把包含一個 點以上的部分繼續分割 下去，直到每一個小部 分只含一個資料點為止 它所對應的四分樹如圖 5.51 所示
請注意，該樹所有葉節 點上的狀態值都是0 戴顯權 著 / 資料結構 © 滄海圖書

169 四分樹的結構 戴顯權 著 / 資料結構 © 滄海圖書

170 四分樹的應用— 以資料壓縮為例 圖5.52顯示一張大小為 像素(pixel) 的二元影 像(只有黑與白兩種顏色)。 我們要替它找出一個緊湊 的表示法 戴顯權 著 / 資料結構 © 滄海圖書

171 四分樹的應用— 以資料壓縮為例 首先把這整張影像分割 成四張256  256大小的 子影像
我們可以發現其中兩張 子影像A 與B 的像素值都 是0，就不需要再進行分 割 戴顯權 著 / 資料結構 © 滄海圖書

172 四分樹的應用— 以資料壓縮為例 其餘的兩張子影像C 與D。 這兩張子影像都同時含有0 與1 的像素值，因此需要 再細分下去才能做記錄
因此把需要細分的部分再 分割成128  128 大小的子 影像，又可以找到C1 與C3 兩張像素值全部都一樣的 子影像(都是0) 戴顯權 著 / 資料結構 © 滄海圖書

173 四分樹的應用— 以資料壓縮為例 我們把上圖的C2, C4, D1, D2, D3, D4 再分割下去
圖5.54(a)所示的是分割到最 小64  64 子影像的結果 戴顯權 著 / 資料結構 © 滄海圖書

174 四分樹的應用— 以資料壓縮為例 圖5.54(b) 所示的則是分割到 最小32  32 子影像的結果 戴顯權 著 / 資料結構 © 滄海圖書

175 四分樹的應用— 以資料壓縮為例 戴顯權 著 / 資料結構 © 滄海圖書

176 四分樹的應用— 以資料壓縮為例 戴顯權 著 / 資料結構 © 滄海圖書