簡介

樹(Tree)是一種常見的資料結構，他是一種階層式(Hierarchical)的資料集
我們觀察這棵樹之後可以發現他由某些東西組成，包含樹葉、樹枝和樹幹；
同樣地，在程式世界裡有著類似的對應，樹的最開始會有一個根節點，就像樹的樹根一樣，所有的資料都是由這裡開始發展，接著會有一些其他的節點，有些節點可能在最末端，稱之為葉節點，就像樹的樹葉一樣，其他的節點則像樹的樹枝一樣。
不過在程式世界裡面，我們習慣把根節點放在最上面，而在我們生活中其實也很常使用
上圖的區長為根節點，最下面的各單位則為葉節點。

定義

在數學的圖論和資料結構所提到的樹其實有些差異，在這裡先說明兩者的不同，數學中對樹的定義這裡簡化如下：
圖中任兩點存在一條路經相通，但不存在環(Cycle)。
不過在資料結構裡面所說的樹，指的是數學裡的有根樹(Rooted tree)，定義如下：
有一個特殊節點為根節點的樹。
在資料結構中的實作會有父節點和子節點的分別，所以可以進一步的定義：
樹存在一個為根節點，根節點沒有父節點(不可以有迴圈)。
每個節點只有一個父節點(子樹不交集)。
tree 上圖藍色線段的部分是符合樹的條件，而紅色的線段C->B和C->E違反了每個節點只有一個父節點，形成交集或連結；而線段D->A則違反了必須存在一個根節點，形成了迴圈；而這兩點正是對應到數學的環。
在樹的資料結構中有一些專有名詞，解釋和定義如下：
根(Root)節點：沒有父節點的節點。
葉(Leaf)節點：沒有子節點的節點。或稱終端(Terminal)、外部(External)或外(Outer)節點。
分枝(Branch)節點：有子節點的節點。或稱非終端(Non-terminal)、內部(Internal)或內(Inner)節點。
子(Child)節點：一個節點的下一層節點。
父(Parent)節點：一個節點的上一層節點。
祖先(Ancestor)節點：從根節點到此節點路徑上的所有節點，不包含此節點。
兄弟(Sibling)節點：相同父節點的所有節點彼此稱為兄弟節點。
節點分支度(Degree)；一個節點的子節點個數。
階層(Level)：若某節點之父節點的階層為n，則該節點階層為n+1，且根節點階層為1。
樹分支度：樹當中節點分支度最大值。
深度(Depth)：樹當中節點階層最大值。或稱高度(Height)。
森林(Forest)：許多不相交的樹可組成森林。
K元樹(K-ary tree)：一個樹的節點之子節點都不超過K個，稱為K元樹，例如K=2為二元樹。K為變數，也常用N表示。
以下面的樹為例子：

tree

根節點：A
葉節點：DEGH
分支節點：ABCF
A的子節點：BC
B的子節點：DEF
...
C的父節點：A
D的父節點：B
... H的祖先節點：ABF
G的祖先節點：AC
... E的兄弟節點：DF
B的兄弟節點：C
...
B的分支度：3
H的分支度：0
... 樹的分支度：3
樹的深度：4
實作
由於樹的用途相當多變，所以實作的介面和方式也不同，這裡實作一種類型，介面如下：
parent：取得父節點。
children：取得子節點。
add：加入子節點。
remove：移除節點。
clone：複製樹。
level：節點的階層。
depth：樹的深度。
degree：取得分支度。
size：子樹的節點個數。
連結串列
實作上可以用連結串列完成，本文簡單利用一個參考指向父節點，同時搭配內建的連結串列表示子節點來實作。除了連結串列之外也可使用其他的資料集合來取代，例如動態陣列等。