資料結構 樹 (Tree)
2021-12-12 · 3 min read
如先前文章所言，本系列文章會以 JavaScript 學習演算法與資料結構為主題來撰寫。
這篇會講解 tree 這種資料結構，然後因為 tree 的類型有很多種，所以實作部分會在之後的文章進行。
什麼是 Tree？
Tree 是 graph 的其中一種形式，是一種具有多個 node 資料結構，且這些 node 之間有 parent / child 關係。
有關於 graph 的更詳細的內容，之後會寫在另一篇文章介紹。
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 Tree
- Binary Search Tree
- Binary Heap
Binary Heap 的部分，之後會寫成另篇文章來介紹。
Binary Tree
Binary Tree 的特徵是每個 node 最多含有兩個 children，且每一個 node 的值都不重複。
source: 二元樹 - 維基百科