今天的目標就是對樹狀結構有基本的認識！

樹（Tree） vs. 圖（Graph）

一個資料結構，如果他是沒有「循環」 (Cycle) 在內的，那他可以被拉成「樹」

如果存在「循環」在內，那他就叫「圖」

因此我們可以稱「樹是一種圖」

樹

以下的術語，我們會以搭配這張圖來輔助說明

節點家族

假設我是節點 D

• Parent Node(父節點)

  • D 的父節點為 B

• Child Node(子節點)

  • D 的子節點為 H, I

• Sibling Node(兄弟節點)

  • 父節點的所有子節點互為兄弟節點（表兄弟跟堂兄弟都不算）
  • D 的兄弟節點為 E

• Root Node(根節點)

  • 根節點沒有父節點，因此也沒有任何兄弟節點
  • 一棵樹只有一個根節點
  • 這棵樹的根節點是 A

• Leaf Node(葉節點) / Terminal Node(終端節點)

  • 葉節點沒有任何子節點
  • 這棵樹的葉節點是 F, G, H, I, J

Terms of Tree

• Degree（度）：子節點個數

  • 例：Degree(Leaf Node) = 0

• Level（階層）：以下我們以遞迴來定義

  • Level of Root = 1
  • Level of Child Node = Level of Parent Node + 1

• Height / Depth (深度):

  • 一棵樹中，最大的階層為這棵樹的深度

• Width (寬度):

  • 階層 n 的節點數量
  • 例：Width of Level 2 = 4

• Breadth (廣度):

  • 葉節點的數量
  • 例：Breadth of this tree = 5

Binary Tree vs. Binary Search Tree

二元樹（Binary Tree）：簡稱 BT

二元搜尋樹（Binary Search Tree） ：簡稱 BST
「二元搜尋樹」 是一種 「二元樹」( BST <= BT <= Tree )

所以，二元搜尋樹需要先滿足二元樹的條件！

Binary Tree

簡單來說，每一個節點最多有兩個分岔

Family of Nodes

一個節點的家族關係：

• Parent Node(父節點)：

  • 在二元樹裡面，一個節點最多有一個父節點
  • 如果一個節點沒有父節點，那他就是樹根(root)

• Child Node(子節點)：

  • 在二元樹裡面，一個節點最多有二個子節點(兩個分岔)
  • 如果一個節點沒有子節點，那他就是樹葉(leaf)

• Sibling Node(兄弟節點)：

  • 在二元樹裡面，一個節點最多有一個兄弟節點
  • 父節點有兩個分岔，自己是其中一個
  • 如果父節點有兩個子節點，那另一個節點就是自己的兄弟節點

下一篇開始，我們會把目標放在「二元搜尋樹」上