樹狀結構

樹狀結構的定義為每個點之間都可以找到路徑連通，但不會形成循環(cycle)，且設定其中一個點為root(根節點)，與root(根節點)相連的子樹(子樹1、子樹2、…與子樹n)，任兩個子樹之間沒有邊相連，若可以連通就會形成循環(cycle)，且子樹1、子樹2、…與子樹n也都是樹狀資料結構。

以下是樹狀結構，點1到點9每個點之間都可以找到路徑連通，且沒有形成循環(cycle)。假設點1為root(根節點)，其下方有三個子樹，子樹之間沒有邊相連，點2、點3與點4也是子樹。

下圖就不是樹狀結構，點1、點2與點3形成循環(cycle)

介紹一些樹狀結構的名詞定義，以下圖為範例進行說明。

(1)root(根節點)：點1就是root。

(2)edge(邊)：將點之間連接起來的線就是edge，上圖樹狀結構有8個邊。

(3)node(節點)：點1到點9都是node，上圖樹狀結構有9個點。

(4)parent(雙親節點)：點1是點2、點3與點4的parent。

(5)children(小孩節點)：點2、點3與點4是點1的children。

(6)sibling(手足節點)：點3與點4是點2的sibling。

(7)leaf node(葉節點)或terminal node(終節點)：節點下方沒有其他節點，點5、點6、點7、點8與點9是上圖樹狀結構的leaf(葉節點)，也可以稱為terminal node。

(8)internal node(內部節點)或nonterminal node(非終節點)：節點不是leaf(葉節點)就是internal node，點1、點2、點3與點4是本圖的internal node，也可以稱為nonterminal node。

(9)external node(外部節點)：與leaf(葉節點)定義相同，節點下方沒有其他節點，點5、點6、點7、點8與點9是此範例樹狀結構的external node。

(10)degree(分支度)：節點下有幾個分支，點1的degree為3，點2的degree為2，點7的degree為0。

(11)level(階層)：若定義root所在level為1，則點1的level為1，點2的level為2，點7的level為3。

(12)height(高度)或depth(深度)：樹狀結構的所有點的最大level(階層)稱作height或depth，此範例樹狀結構的height為3，也可以稱為depth為3。

所有點都可以與其他點相連的簡單圖，若邊的個數是點的個數少一個，則該圖形一定是樹狀結構，樹狀結構多一個邊會形成循環，少一個邊會無法連通。樹狀結構滿足以下特性，V表示點的個數，E表示邊的個數。

E = V – 1

最簡單的樹狀結構就是二元樹，實作二元樹的程式碼讓讀者可以更加瞭解樹狀結構，並介紹二元樹的走訪，如何利用程式走過每個節點。二元樹須符合樹狀結構的定義，且二元樹中每個節點的最大分支度(degree)為2，左邊的分支樹稱作left subtree(左子樹)，右邊的分支樹稱作right subtree(右子樹)。二元樹有分成歪斜二元樹(Skewed Binary Tree)、完整二元樹(Complete Binary Tree)與滿二元樹(Full Binary Tree)。

(一)歪斜二元樹

如果樹的每層節點只有左子樹或樹的每層節點只有右子樹，就是歪斜二元樹(Skewed Binary Tree)，如下圖。

(二)完整二元樹

二元樹除了最下層未全滿外，且最下層的元素從最左邊到最右邊依序擺放，其餘階層都要全滿，稱作完整二元樹(Complete Binary Tree)。

(三)滿二元樹(Full Binary Tree)

二元樹每一層都全滿，稱作滿二元樹(Full Binary Tree)。

6-2-1 二元樹的性質

以下為二元樹的性質。

(1)高度為h的二元樹最少節點個數為「h」，歪斜二元樹(Skewed Binary Tree)是高度h的最少節點二元樹，歪斜二元樹有h個節點。

(2)第i層的二元樹的節點個數最多為「2^(i-1)」，假設根節點(root)為第1層，滿二元樹每一層的元素個數最多，可以發現每一層都是上一層節點個數的兩倍，第1層節點為2^0個，第2層節點為2^1個，第3層節點為2^2個，第4層節點為2^3個，…，第i層節點為2^(i-1)個。

(3)高度為h的滿二元樹的總節點個數為「2^h-1」，假設根節點的高度為1，高度為h的滿二元樹的每一層節點相加可以獲得總節點數，公式如下。

(4) n0表示樹狀結構中葉節點(分支度為0)的節點個數與n2表示分支度為2的節點個數，則「n0 = n2+1」。

E表示邊的總數，N表示節點總數，n1表示分支度為1的節點個數，則有以下關係。

E = N – 1 ------------(1) 樹狀結構邊的個數為點的個數少1

N = n0 + n1 + n2 ----(2) 節點總數為分支度為0到2的節點數加總

E = n1 + 2*n2 --------(3) 邊的總數為分支度1的節點數加上2倍分支度2節點數

將(2)與(3)代入(1)，n1 + 2*n2 = n0 + n1 + n2 – 1，消去n1與移項後，獲得n0 = n2 + 1

6-2-2使用陣列建立二元樹

可以使用陣列建立二元樹，如下二元樹範例，本範例二元樹有6個節點。

假設以陣列btree進行儲存，每個節點就依照點所在位置依序放入陣列中，若二元樹有空節點也必須保留該元素的陣列空間，並將None填入到該保留空間，在後面章節中「樹的走訪」單元會使用到這個保留空間，表示該節點沒有元素。點A為root(根節點)放置於陣列btree的索引值為1的元素內，點B為點A的左邊小孩，放置在陣列btree的索引值為2*(1)的元素內，點C為點A的右邊小孩，放置在陣列btree的索引值為2*(1)+1的元素內。點D為點B的左邊小孩，所以放置在陣列btree的索引值為2*(2)的元素內，點E為點B的右邊小孩，所以放置在陣列btree的索引值為2*(2)+1的元素內，依此類推。

可以獲得節點與索引值編號的規則如下，點X放置在陣列btree的索引值為n的元素內，點Y為點X的左邊小孩，就放置在陣列btree的索引值為2*(n)的元素內，點Z為點X的右邊小孩，就放置在陣列btree的索引值為2*(n)+1的元素內，有了此規則性才能使用程式存取二元樹的節點。使用陣列建立二元樹，程式碼如下。

想一想

二元樹使用陣列表示有什麼優缺點？使用陣列表示二元樹的優點是程式撰寫容易。那什麼情況下適合使用陣列表示二元樹？

假設二元樹如下，二元樹只有3個節點，節點都在右子樹，是向右歪斜二元樹。

以陣列表示二元樹，陣列狀態如下。

陣列btree

發現出現許多空間的浪費，若圖形深度越深，二元樹都只用一個子樹情形下，空間的浪費就更加嚴重。若二元樹所有節點幾乎都可以填滿，就可以使用陣列進行二元樹的建立，不會浪費太多空間，若二元樹不一定能填滿，使用陣列就會造成空間浪費，可以使用指標方式建立二元樹，不會造成浪費太多空間，只需多增加指標空間而已，但程式會稍微複雜一點。

二元樹需要兩個指標，一個指向左子樹，另一個指向右子樹，若子樹是空的時候設定為None，None就是空指標，在二元樹走訪時遇到None，就不能再走訪下去，必須倒退回去，二元樹的類別BinaryTree宣告如下，類別BinaryTree中val用於儲存資料，left與right指標用於指向左子樹與右子樹，方法setLeft設定左子樹，方法setRight設定右子樹。

class BinaryTree:

def __init__(self, value):

self.val = value

self.left = None

self.right = None

def setLeft(self, left):

self.left = left

def setRight(self, right):

self.right = right

如果要將下圖的二元樹使用指標方式建立二元樹，程式碼如下。

二元樹如何走訪每一個點，每一個點都需要走過？使用遞迴呼叫走訪二元樹的程式碼最簡單，遞迴呼叫走訪左子樹，接著遞迴呼叫走訪右子樹就可以走訪所有的節點，配合顯示節點的資料就可以輸出所有節點的值，這是一種暴力演算法。「走訪左子樹」、「走訪右子樹」與「顯示節點的資料」三種操作，排列的可能性有6種可能結果，若「走訪左子樹」永遠比「走訪右子樹」優先，則只剩下3種可能結果，分別敘述如下。

(1) preorder(前序走訪)

先「顯示節點的資料」，再「走訪左子樹」，最後「走訪右子樹」。

(2) inorder(中序走訪)

先「走訪左子樹」，再「顯示節點的資料」，最後「走訪右子樹」。

(3) postorder(後序走訪)

先「走訪左子樹」，再「走訪右子樹」，最後「顯示節點的資料」。

這3種走訪都是深度優先走訪，會造成顯示節點資料的順序不相同。之後章節會介紹圖形走訪，也會提到深度優先走訪，樹狀結構是圖形結構的特例，樹狀結構所介紹的概念也可以應用到圖形結構，為圖形結構先打好基礎。

還有另一種走訪，同一個階層的節點優先走訪，不使用遞迴呼叫進行走訪，而是使用佇列進行走訪，屬於寬度優先走訪，圖形結構也可以進行寬度優先走訪，樹狀結構的這種走訪方式，稱作階層走訪(level order)。

以下使用陣列與指標實作二元樹，並使用前序走訪(preorder)、中序走訪(inorder)、後序走訪(postorder)與階層走訪(level order)進行走訪，顯示節點的數值到螢幕。

6-2-4-1二元樹走訪--使用陣列

(a)範例說明

實作一個程式，將以下二元樹以陣列進行實作，並使用前序走訪(preorder)、中序走訪(inorder)、後序走訪(postorder)進行走訪，走訪過程中印出節點的資料。

(b)預期程式執行結果

以下為前序走訪(preorder)遞迴呼叫過程的說明：

(1) 呼叫preorder(1)，先顯示btree[1]節點資料「A」到螢幕。

(2) 接著走訪左子樹，遞迴呼叫preorder(2)，先顯示btree[2]節點資料「B」到螢幕。

(3) 接著走訪左子樹，遞迴呼叫preorder(4)，先顯示btree[4]節點資料「D」到螢幕。

(4) 接著走訪左子樹，遞迴呼叫preorder(8)，因為btree[8]為None，表示沒有節點，不做任何動作。

(5) 倒退回btree[4]。

(6) 接著走訪右子樹，遞迴呼叫preorder(9)，因為btree[9]為None，表示沒有節點，不做任何動作。

(7) 倒退回btree[4]，此時左右子樹皆已經拜訪過。

(8) 倒退回btree[2]。

(9) 接著走訪右子樹，遞迴呼叫preorder(5)，先顯示btree[5]節點資料「E」到螢幕。

(10) 接著走訪左子樹，遞迴呼叫preorder(10)，因為btree[10]為None，表示沒有節點，不做任何動作。

(11) 倒退回btree[5]。

(12) 接著走訪右子樹，遞迴呼叫preorder(11)，因為btree[11]為None，表示沒有節點，不做任何動作。

(13) 倒退回btree[5]，此時左右子樹皆已經拜訪過。

(14) 倒退回btree[2]，此時左右子樹皆已經拜訪過。

(15) 倒退回btree[1]。

(16) 接著走訪右子樹，遞迴呼叫preorder(3)，先顯示btree[3]節點資料「C」到螢幕。

(17) 接著走訪左子樹，遞迴呼叫preorder(6)，因為btree[6]為None，表示沒有節點，不做任何動作。

(18) 倒退回btree[3]。

(19) 接著走訪右子樹，遞迴呼叫preorder(7)，先顯示btree[7]節點資料「F」到螢幕。

(20) 接著走訪左子樹，遞迴呼叫preorder(14)，因為btree[14]為None，表示沒有節點，不做任何動作。

(21) 倒退回btree[7]。

(22) 接著走訪右子樹，遞迴呼叫preorder(15)，因為btree[15]為None，表示沒有節點，不做任何動作。

(23) 倒退回btree[7]，此時左右子樹皆已經拜訪過。

(24) 倒退回btree[3]，此時左右子樹皆已經拜訪過。

(25) 倒退回btree[1]，preorder(1)到此執行結束。

所以前序走訪後，會顯示「A B D E C F」在螢幕上。

中序走訪與後序走訪概念與前序走訪類似，因為版面關係，請讀者自行演練。

(a)範例說明

請實作一個程式將以下二元樹，以指標方式建立二元樹，前序走訪(preorder)、中序走訪(inorder)、後序走訪(postorder)進行走訪，走訪過程中印出節點的資料。

(b)預期程式執行結果

(c)說明與程式

觀察前兩個範例，使用陣列或指標所建立二元樹的前序走訪、中序走訪與後序走訪結果，得知使用陣列或指標所建立的二元樹，並不會影響走訪結果。

(a)範例說明

請實作一個程式將以下二元樹，以指標進行二元樹的建立，並使用level order(階層走訪)進行走訪，走訪過程中印出節點的資料。

(b)預期程式執行結果

(c)說明與程式

階層走訪二元樹過程中佇列qu的新增與刪除元素過程。

Step1)發現點A，將A加入到佇列qu。

Step2)從佇列讀取第一個元素A，輸出A到螢幕上，將點A左子樹的點B與右子樹的點C加入到佇列qu，最後刪除第一個元素A。

Step3)從佇列讀取第一個元素B，輸出B到螢幕上，將點B左子樹的點D與右子樹的點E加入到佇列qu，最後刪除第一個元素B。

Step4)從佇列讀取第一個元素C，輸出C到螢幕上，因為點C左子樹是None，不執行任何動作，將右子樹的點F加入到佇列qu，最後刪除第一個元素C。

Step5)從佇列讀取第一個元素D，輸出D到螢幕上，因為點D左子樹與右子樹都是None，不執行任何動作，最後刪除第一個元素D。

Step6)從佇列讀取第一個元素E，輸出E到螢幕上，因為點E左子樹與右子樹都是None，不執行任何動作，最後刪除第一個元素E。

Step7)從佇列讀取第一個元素F，輸出F到螢幕上，因為點F左子樹與右子樹都是None，不執行任何動作，最後刪除第一個元素F，佇列qu是空的跳出迴圈。

Step8)輸出結果為「A B C D E F」。

符合以下定義，稱為二元搜尋樹(Binary Search Tree)，在平均情況下可以加速搜尋的速度，但在最差情況下與循序搜尋效率相同。

(1)如果左子樹不是空的，左子樹的所有點的鍵值小於根節點的鍵值。

(2)如果右子樹不是空的，右子樹的所有點的鍵值大於根節點的鍵值。

(3)左子樹與右子樹也是二元搜尋樹

(4)二元搜尋樹內所有鍵值都不相同

以下為二元搜尋樹範例。

二元搜尋樹的每一個節點需要兩個指標，一個指向左子樹，另一個指向右子樹，若子樹是空的時候設定為None，None就是空指標，在二元樹走訪時遇到None，就不能再走訪下去，必須倒退回去，二元樹的節點類別Node宣告如下。類別Node中val用於儲存資料，left與right指標用於指向左子樹與右子樹。類別BinarySearchTree用於建立二元搜尋樹，利用類別Node建立節點。

以下二元搜尋樹插入節點6，為了滿足二元搜尋樹，先比較根節點，發現節點6比根節點(10)小，往左邊走；接著比較左子樹的根節點5，發現節點6比較大，往右邊走；比較右子樹的根節點7，發現節點6比較小，往左邊走；發現左子樹是None，所以新增一個節點6，在節點7的左子樹。

新增節點6，二元搜尋樹如下。

插入節點的程式如下。

如果要搜尋節點9是否在以下二元搜尋樹中，先比較根節點10，發現9比10小，根據二元搜尋樹的定義，比根節點10小的數值會在左子樹，所以往左邊搜尋；比較左子樹的根節點5，發現9比5大，所以往右邊搜尋；比較右子樹的根節點7，發現9比7大，所以往右邊搜尋；比較右子樹的根節點9，發現找到節點9。

搜尋節點程式如下。

刪除節點時，如果左右子樹都有元素，則使用右子樹的最小元素(右子樹往左走到底)取代刪除節點，例如：刪除以下二元搜尋樹的元素5，左右子樹都有元素，取右子樹的最小元素，走到右子樹的根節點7，往左走到底遇到節點6，節點6取代節點5。

刪除節點5後，如下圖。

刪除節點7，因為節點7只有一個子樹，刪除節點7，將子樹取代節點7。

刪除節點7後，如下圖。

刪除節點11，因為節點11沒有子樹，直接刪除節點11。

刪除節點11，如下圖。

刪除節點程式如下。

6-3-4 二元搜尋樹的中序走訪

中序走訪二元搜尋樹會輸出已排序的所有鍵值，使用方法insert插入數值到二元搜尋樹，使用方法search_and_delete刪除數值。

程式執行結果

程式執行效率

在平均情況下，樹的每一階層層元素分布的很均勻時，二元搜尋樹的插入、刪除與搜尋演算法效率為O(log(n))，最差情況下，每一層都只有一個節點的傾斜樹，如下圖，插入、刪除與搜尋演算法效率為O(n)，與循序搜尋效率相同。

為了避免產生傾斜樹，而有了AVL樹與B樹的概念，將在之後章節介紹，可以保證樹的每一階層的元素個數足夠多，讓插入與搜尋更有效率。