我們前幾天講了鏈結串列、堆疊、佇列，這些線性資料結構(走訪時只能沿著一條線走)，今天要來看非線性的資料結構啦 !

樹(Tree)是什麼?

樹 (Tree)是由一個或一個以上的節點 (Node) 跟連接節點的邊（Edge）所組成的結構，且不會形成環（Cycle）

合法的樹節點間可以相互連結，但不能形成沒有出口的迴圈。

林(Forest)

森林（Forest）是由多棵彼此獨立的樹所組成的集合
另外，一棵樹移除根節點後，剩下的子樹集合也會形成一個森林（Forest）

很多地方都能看到樹
例如國高中就學過的 排列組合

圖片來源*https://i.ytimg.com/vi/MgQexDhd5_Y/maxresdefault.jpg

常見名詞

分支度( Degree)

一個節點所有的子樹(subtree)個數
上圖中各分支度 : A 的 degree 為3，B 的 degree 為2，C 的 degree 為0

根節點（Root）

樹最頂端、唯一沒有父節點的節點
上圖中的 A 就是根節點，整棵樹都是從這裡開始往下展開

父節點（Parent）與子節點（Child）

越靠近根節點的那一個是父節點，越遠離根節點的那一個是子節點

• 父節點 (Parent) : 有子節點的節點就是父節點，換句話說，某節點上一層、直接與其相連的節點，每個節點除了根節點(Root)以外都有父節點
• 子節點 (Child) : 某個節點下一層節點即為子節點

兄弟節點 (siblings)

有共同parent的節點
如上圖，B、C、D有共同parent A，所以他們三個互為兄弟節點 (siblings)

葉節點（Leaf）或稱終端節點 (Terminal nodes)

分支度為0，也就是沒有任何子節點的節點，也就是樹狀結構末端的節點
上圖中的 E、F、G、H、I 都是葉節點。

子樹（Subtree）

以某個節點為根，往下延伸出去的整個結構，本身也是一棵完整的樹。例如以 B 為根，B、E、F 這三個節點加上它們之間的連接，就構成一棵子樹

邊（Edge）

連接兩個節點之間的線，代表父子關係。一棵有 n 個節點的樹，會恰好有 n-1 條邊（因為每個節點除了根節點以外，都恰好有一條邊連向它的父節點）。

階層 (level)

樹的層級，設樹根(root)為第 1 層，其他節點的階層為父節點 (parent) 的階層+1

如圖所示，A 的 level 為 1，B、C、D的 level為 2，E、F、G、H、I的level為3

高度（Height）與深度（Depth）

• 深度（Depth）：從根節點數到某個節點，中間經過的邊的數量。根節點自己的深度是 0
• 高度（Height）：從某個節點數到它底下最遠的葉節點，中間經過的邊的數量。葉節點自己的高度是 0

為什麼會需要樹狀結構

前面學過的鏈結串列，走訪起來永遠只有一條路徑，適合處理一筆接一筆的資料。但現實中很多資料本身就有階層關係，例如：

• 檔案總管裡的資料夾巢狀結構（一個資料夾底下有多個子資料夾）
• 公司組織圖（一個主管底下管理多名下屬）
• 網頁的 HTML DOM 結構（一個標籤底下包著多個子標籤）
• 遊戲場景的地形資訊

這些情境如果硬要用線性結構表示會很麻煩，樹狀結構天生就適合表達「一對多」的父子階層關係，這也是它跟前面介紹過的線性資料結構最根本的差異

下一篇會接著介紹樹狀結構中最常見的類型 : 二元樹（Binary Tree），以及它的走訪方式

參考資料和書籍

1. Tree(樹): Intro(簡介)
2. https://program-lover.blogspot.com/2008/12/tree.html
3. 二元樹_NTUCPC
4. 圖解資料結構×演算法:運用C++ 胡昭明