資料結構 樹 (Tree)

2021-12-12 · 3 min read

如先前文章所言,本系列文章會以 JavaScript 學習演算法與資料結構為主題來撰寫。

這篇會講解 tree 這種資料結構,然後因為 tree 的類型有很多種,所以實作部分會在之後的文章進行。

什麼是 Tree?

Tree 是 graph 的其中一種形式,是一種具有多個 node 資料結構,且這些 node 之間有 parent / child 關係。

有關於 graph 的更詳細的內容,之後會寫在另一篇文章介紹。

Tree source: 樹 (資料結構) - 維基百科

樹的解析

術語

  • Root:tree 最上層的 node
  • Child:與另個 node 連結但離 root 比較遠的為 child node
  • Parent:與另個 node 連結但離 root 比較近的為 parent node
  • Siblings:有同一個 parent node 的 nodes
  • Leaf:沒有 children node 的 node
  • Edge:node 和 node 之間的連結

應用

Tree 的例子包含但不限於:

  • HTML DOM
  • 網路的路由機制
  • 程式語言的語法
  • 人工智慧的狀況處理以及行為等等(decision tree)
  • 作業系統中的資料夾機制
  • JSON
  • 電腦的資料夾系統

由以上的例子可知 Tree 其實早就用我們常使用的功能中,也可以想成是有分歧路線的 list。


常見的 Tree

接下來會用

Binary Heap 的部分,之後會寫成另篇文章來介紹。

Binary Tree

Binary Tree 的特徵是每個 node 最多含有兩個 children,且每一個 node 的值都不重複。

Binary Tree source: 二元樹 - 維基百科

Ref
用 JavaScript 實作二元搜尋樹(Binary Search Tree)用 JavaScript 實作佇列(Queue)

Comment