樹狀結構(C++)
本單元目錄大綱
一、簡介樹狀結構
二、樹狀結構的名詞定義
三、實作二元樹資料結構的程式
3-1. 二元樹的定義
3-2.使用陣列建立二元樹
3-3.使用指標建立二元樹
四、二元樹的走訪
五、樹狀結構範例
樹狀結構是由點與邊所組成，樹狀結構廣泛應用在資訊系統與資料結構中，檔案系統內資料夾下可以有檔案與資料夾，從磁碟機開始，可以不斷的展開，用於儲存與分類檔案與資料夾，這就是樹狀結構的應用，如下圖，「本機」是樹狀結構的最上層，下方有「C」磁碟機，再點選C磁碟機下的「Windows」資料夾，就可以經由樹狀結構一層一層往下走訪檔案與資料夾。
樹狀結構常用於競賽，可以清楚表示競賽的過程與結果，例如：2018世足賽4強賽程表就會形成一個樹狀圖，利用樹狀圖可以清楚表示比賽的過程與結果。
資料結構的B tree是一種樹狀結構，能提供快速新增、刪除與搜尋功能與儲存大量資料，可以用於實作資料庫系統。以下介紹樹狀結構的定義、程式實作與範例解題。
一、簡介樹狀結構
什麼是樹狀結構？
樹狀結構的定義為每個點之間都可以找到路徑連通，但不會形成循環(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都是edge，上圖樹狀結構有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。
三、實作二元樹資料結構的程式
最簡單的樹狀結構就是二元樹，實作二元樹的程式碼讓讀者可以更加瞭解樹狀結構，並介紹二元樹的走訪，如何利用程式走過每個節點，並為下一章圖形結構(Graph)走訪進行暖場。
3-1. 二元樹的定義
二元樹須符合樹狀結構的定義，且二元樹中每個節點的最大分支度(degree)為2，左邊的分支樹稱作left subtree(左子樹)，右邊的分支樹稱作right subtree(右子樹)。
3-2.使用陣列建立二元樹
可以使用陣列建立二元樹，如下二元樹範例，本範例二元樹有6個節點。
假設以陣列btree進行儲存，每個節點就依照點所在位置依序放入陣列中，若二元樹有空節點也必須保留該元素的陣列空間，並將0填入到該保留空間，在後面章節中「樹的走訪」單元會使用到這個保留空間，表示該節點沒有元素。點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的元素內，有了此規則性才能使用程式存取二元樹的節點。
如果要使用陣列建立二元樹，C++程式碼如下。
想一想
二元樹使用陣列表示有什麼優缺點？使用陣列表示二元樹的優點是程式撰寫容易。那什麼情況下適合使用陣列表示二元樹？
假設二元樹如下，二元樹只有3個節點，節點都在右子樹。
發現出現許多空間的浪費，若圖形深度越深，二元樹都只用一個子樹情形下，空間的浪費就更加嚴重。若二元樹所有節點幾乎都可以填滿，就可以使用陣列進行二元樹的建立，不會浪費太多空間，若二元樹不一定能填滿，使用陣列就會造成空間浪費，可以使用指標方式建立二元樹，不會造成浪費太多空間，只需多增加指標空間而已，但程式會稍微複雜一點。
3-3.使用指標建立二元樹
二元樹需要兩個指標，一個指向左子樹，另一個指向右子樹，若子樹是空的時候設定為NULL，NULL就是空指標，程式會以數值0取代，在二元樹走訪時遇到NULL，就不能再走訪下去，必須倒退回去，二元樹的結構宣告如下。結構中data用於儲存資料，left與right指標用於指向左子樹與右子樹。
C++二元樹的結構宣告如下。
如果要將下圖的二元樹使用指標方式建立二元樹。
C++程式碼如下。
四、二元樹的走訪
二元樹如何走訪每一個點，每一個點都需要走過？使用遞迴呼叫走訪二元樹的程式碼最簡單，遞迴呼叫走訪左子樹，接著遞迴呼叫走訪右子樹就可以走訪所有的節點，配合顯示節點的資料就可以輸出所有節點的值，這是一種暴力演算法。「走訪左子樹」、「走訪右子樹」與「顯示節點的資料」三種操作，排列的可能性有6種可能結果，若「走訪左子樹」永遠比「走訪右子樹」優先，則只剩下3種可能結果，分別敘述如下。
(1) preorder(前序走訪)
先「顯示節點的資料」，再「走訪左子樹」，最後「走訪右子樹」。
(2) inorder(中序走訪)
先「走訪左子樹」，再「顯示節點的資料」，最後「走訪右子樹」。
(3) postorder(後序走訪)
先「走訪左子樹」，再「走訪右子樹」，最後「顯示節點的資料」。
這3種走訪都是深度優先走訪，會造成顯示節點資料的順序不相同。下一單元圖形走訪，也會提到深度優先走訪，樹狀結構是圖形結構的特例，樹狀結構所介紹的概念也可以應用到圖形結構，為圖形結構先打好基礎。
還有另一種走訪，同一個階層的節點優先走訪，不使用遞迴呼叫進行走訪，而是使用queue進行走訪，屬於寬度優先走訪，圖形結構也可以進行寬度優先走訪，樹狀結構的這種走訪方式，稱作level order(階層走訪)。
以下使用陣列與指標實作二元樹，並使用preorder(前序走訪)、inorder(中序走訪)、postorder(後序走訪)與level order(階層走訪)進行走訪，顯示節點的數值到螢幕。
(一)二元樹走訪--使用陣列
範例說明
請實作一個程式將以下二元樹，以陣列進行表示，並使用preorder(前序走訪)、inorder(中序走訪)、postorder(後序走訪)進行走訪，走訪過程中印出節點的資料。
預期程式執行結果
C++程式碼
以下圖示前序走訪(preorder)的遞迴呼叫過程。
以下為前序走訪(preorder)遞迴呼叫過程的說明：
(1) 呼叫preorder(1)，先顯示btree[1]節點資料「A」到螢幕。
(2) 接著走訪左子樹，遞迴呼叫preorder(2)，先顯示btree[2]節點資料「B」到螢幕。
(3) 接著走訪左子樹，遞迴呼叫preorder(4)，先顯示btree[4]節點資料「D」到螢幕。
(4) 接著走訪左子樹，遞迴呼叫preorder(8)，因為btree[8]為0，表示沒有節點，不做任何動作。
(5) 倒退回btree[4]。
(6) 接著走訪右子樹，遞迴呼叫preorder(9)，因為btree[9]為0，表示沒有節點，不做任何動作。
(7) 倒退回btree[4]，此時左右子樹皆已經拜訪過。
(8) 倒退回btree[2]。
(9) 接著走訪右子樹，遞迴呼叫preorder(5)，先顯示btree[5]節點資料「E」到螢幕。
(10) 接著走訪左子樹，遞迴呼叫preorder(10)，因為btree[10]為0，表示沒有節點，不做任何動作。
(11) 倒退回btree[5]。
(12) 接著走訪右子樹，遞迴呼叫preorder(11)，因為btree[11]為0，表示沒有節點，不做任何動作。
(13) 倒退回btree[5]，此時左右子樹皆已經拜訪過。
(14) 倒退回btree[2]，此時左右子樹皆已經拜訪過。
(15) 倒退回btree[1]。
(16) 接著走訪右子樹，遞迴呼叫preorder(3)，先顯示btree[3]節點資料「C」到螢幕。
(17) 接著走訪左子樹，遞迴呼叫preorder(6)，因為btree[6]為0，表示沒有節點，不做任何動作。
(18) 倒退回btree[3]。
(19) 接著走訪右子樹，遞迴呼叫preorder(7)，先顯示btree[7]節點資料「F」到螢幕。
(20) 接著走訪左子樹，遞迴呼叫preorder(14)，因為btree[14]為0，表示沒有節點，不做任何動作。
(21) 倒退回btree[7]。
(22) 接著走訪右子樹，遞迴呼叫preorder(15)，因為btree[15]為0，表示沒有節點，不做任何動作。
(23) 倒退回btree[7]，此時左右子樹皆已經拜訪過。
(24) 倒退回btree[3]，此時左右子樹皆已經拜訪過。
(25) 倒退回btree[1]，preorder(1)到此執行結束。
所以前序走訪後，會顯示「A B D E C F」在螢幕上。
中序走訪與後序走訪概念與前序走訪類似，請讀者可以自行演練。
(二)二元樹走訪--使用指標
範例說明
請實作一個程式將以下二元樹，以指標方式建立二元樹，並使用preorder(前序走訪)、inorder(中序走訪)、postorder(後序走訪)進行走訪，走訪過程中印出節點的資料。
預期程式執行結果
C++程式碼
(三)二元樹階層走訪--使用指標
範例說明
請實作一個程式將以下二元樹，以指標進行二元樹的建立，並使用level order(階層走訪)進行走訪，走訪過程中印出節點的資料。
預期程式執行結果
C++程式碼
五、樹狀結構範例
(一)前序與中序建立樹求後序走訪
給定26個節點以內的二元樹的前序走訪與中序走訪結果，每個節點都是大寫英文字母，且節點字母皆不相同，最後輸出後序走訪結果。
輸入說明
輸入兩行大寫英文字串，第一行為二元樹的前序走訪結果，第二行為二元樹的中序走訪結果。
輸出說明
輸出後序走訪的結果。
範例輸入
ABDECF
DBEACF
範例輸出
DEBFCA
(a)解題想法
前序走訪的第一個元素就是根節點，找出在中序走訪結果中此根節點字母的位置，將中序走訪結果切割成左右兩個字串，左右兩個字串可以是空字串，這兩個字串分別表示根節點的左子樹字母與右子樹字母，以此方式不斷決定左右子樹的根節點，再進行左右子樹的切割，最後獲得原來的二元樹。
(b)程式碼
(二)後序與中序建立樹求最小路徑和
給定1000個節點以內的二元樹的後序走訪與中序走訪結果，每個節點都是正整數，節點數值皆不相同，且節點數值小於10000，最後求所有根節點(root)到葉節點(leaft)路徑的最小整數和。
輸入說明
輸入一個整數N，表示二元樹有幾個節點，接下來輸入兩行整數數列，數字之間以空白鍵隔開，第一行為二元樹的中序走訪結果，第二行為二元樹的後序走訪結果。
輸出說明
求所有根節點(root)到葉節點(leaft)路徑的最小整數和。
範例輸入
7
4 2 6 5 1 3 7
4 6 2 1 7 3 5
範例輸出
9
(a)解題想法
後序走訪的最後一個元素就是根節點，找出在中序走訪結果中此根節點數字的位置，將中序走訪結果切割成左右兩個數列，左右兩個數列可以是空字串，這兩個數列分別表示根節點的左子樹數字與右子樹數字，以此方式不斷決定左右子樹的根節點，再進行左右子樹的切割，最後獲得原來的二元樹。
(b)程式碼
範例練習1 uva-679 - Dropping Balls
樹的任何一個點第一次走左邊，第二次走右邊
範例練習2 uva-839 - Not so Mobile
利用二元樹走訪解題
範例練習3 acm-297 – Quadtrees
建立樹、合併樹、DFS
範例練習5 APCS202001 第4題自動分裝
樹狀結構
範例練習6 APCS202210 第3題石窟探險
樹狀結構+DFS 樹狀結構+BFS
範例練習7 APCS10503第4題血緣關係
樹狀結構+DFS
以下為教學影片