tree資料結構c：Tree(樹)

先備知識與注意事項

若熟悉Linked List(連結串列)將會更容易理解樹：Linked list是一維的線性結構(不是往前、就是往後)，樹(與Graph)則推廣成多維的結構。

圖一：A、B、C、D稱為node(節點)，用以代表資料(data)、狀態(state)。連結各個node之間的連結(link)稱為edge，可能是單方向，或者雙向。

關於Linked list，請參考：

OK Go[1].

目錄 隨處可見的Tree(樹)

Tree(樹)是用以描述具有階層結構(hierarchical structure)的問題的首選，階層結構意味著明確的先後次序，例如，若要印出ABC三個字母的所有排列組合(permutation)，直覺反射的圖像會是：

            

圖二：ABC字母排列組合。視R為樹根(root)，每一個選擇狀態視為node，此即為樹的結構。

圖二的邏輯為：從起點(R)開始，先決定第一個字母，再依序決定第二、第三個字母，並且，在每一次選擇字母時，可能有不止一個可供選擇的字母。最後一共走出六條路徑，得到六種排列組合，而且這六種排列方式只能經由一種唯一的選擇方式(唯一的路徑)產生。若將起點(R)視為樹根(root)，每一個字母選擇的狀態(例如：A、C、BC、CAB)都視為一個node，這樣的結構便能夠視為一棵樹。

另外如一本書的目錄、族譜、企業的職位關係，甚至是更廣義的「從家門口為起點尋找方圓一公里以內的便利商店」都能夠建立出樹的模型。

那麼，樹最根本的特徵是什麼？

以族譜為例，若定義包龍星是宋世傑的爸爸，那麼包龍星就絕對不能同時又是宋世傑的兒子。

圖三以node與edge描述此關係，並定義箭頭是從父指向子，則：

包龍星指向宋世傑的箭頭表示包為父、宋為子； 宋世傑指向包龍星的箭頭表示宋為父、包為子；

後者的箭頭即違反了最初「包龍星是宋世傑的爸爸」的命題，此即稱為cycle，也就是著名的「雞生蛋」與「蛋生雞」。

圖三：包龍星若是宋世傑的parent(父)，又同時為其child(子)，即形成cycle。

而樹的最根本特徵就是...