樹(Tree)資料結構介紹

Tree (樹) 主要是用來描述具有明確的先後順序的階層結構(hierarchical structure) 問題的資料結構。存在且只有唯一一個明確的起點(root node),其下的選擇狀態可視為樹的子節點(sub node),且不能存在cycle的關係(A是B的父親,B又是A的父親)。例如:族譜、企業架構、書的目錄等。

名詞解釋

  • root:最上層沒有父節點的節點。
  • 分支度(degree):一個節點下有幾個子節點稱之(A節點 degree 為3)。
  • sibilings:擁有相同父節點的節點(B節點 sibilings 為 C、D)
  • descendant:父節點下的子節點稱之(除A之外的節點都是)
  • leaf:沒有子節點的節點,稱為:leaf node(J、K、L、M、G、H、N)。
  • external node:沒有子節點的節點(等義於 leaf)
  • internal node:至少有一個子節點的節點(A、B、C、D、E、F、I)。
  • level:root節點為 level 1,往下一次遞增(由上往下)。
  • height of node:某個節點距離其下的leaf node的最長距離(由下往上),例如:F為1,D為 2。
  • depth:某個node與root的距離。

樹的特性

  • 若要在Tree中尋找某一個node,則只會存在唯一一條到達該node的路徑。
  • 每個node只有一個父節點(parent node),root node 除外。

樹的分類:

  • Binary Tree:每個 node 至多只有兩個Child
  • Binary Search Tree:從Binary Tree 增加Key大小規則
  • Red Black Tree(RBT):在每個node增加顏色(紅與黑)用來平衡樹的height,縮短搜尋時間。

若打破不能 cycle 的限制的話,就會變成Graph的資料結構。

樹的資料結構

type Node struct {
   Parent *Node
   Left  *Node
   Right *Node
   Data  int/string.....
}