Table of Contents
1. 定義與特性
1.1 定義
Tree 是最常見的 non-linear data structure,構成 tree 的基本單位為 node,以下為 tree 的定義:
- Root Node:(根節點)為 tree 的起點,每一個 tree 僅有一個且唯一的 root node
- A 為 root node
- SubTree:每個 node 底下可以分為互不相交的有限集合,稱為 subTree,以下用 T 來表示
- A 有兩個 subTree: T1(B, D, G, H, I)、T2(C, E, F)
- B 有一個 subTree: T1(D, G, H, I)
- C 有兩個 subTree: T1(E)、T2(F)
- D 有三個 subTree: T1(G)、T2(H)、T3(I)
1.2 特性
n 為 tree 中的 node 數,任一 n > 0 的 tree 有以下的特性:
- Degree:每個 node 擁有的 subTree 個數稱為 degree
- A 的 degree = 2
- B 的 degree = 1
- C 的 degree = 2
- D 的 degree = 3
- Leaf Node / External Node:degree = 0 的 node 稱為 leaf node (葉節點) 或 external node (外部節點)
- E, F, G, H, I 為 leaf node 亦為 external node
- Internal Node:degree >= 1 的 node 稱為 internal node (內部節點)
- B, C, D 為 internal node
- Child Node:node 的 subTree 的 root node 稱為該 node 的 child node
- B, C 為 A 的 child node
- D 為 B 的 child node
- G, H, I 為 D 的 child node
- E, F 為 C 的 child node
- Parent Node:node 的 subTree 的 root node 稱該 node 為 parent node
- A 為 B, C 的 parent node
- B 為 D 的 parent node
- D 為 G, H, I 的 parent node
- C 為 E, F 的 parent node
- Siblings:parent node 一樣的 node 稱為 siblings
- B, C 為彼此的 siblings
- G, H, I 為彼此的 siblings
- E, F 為彼此的 siblings
- Ancestor Node:某個 node 到 root node 路徑上的任意 node 皆為該 node 的 ancestor node
- A, B, D 為 G 的 ancestor node
- A, C 為 E 的 ancestor node
- Descendant Node:某個 node 的 subTree 上的所有節點皆為該 node 的 descendant node
- A 的 descendant node 為此 tree 中的所有 node (除了 A)
- B 的 descendant node 為 D, G, H, I
- C 的 descendant node 為 E, F
- Level:node 的 level 從 root node 定義起,root node 的 level 為 1,其 child 的 level 為 2,以此類推
- A 的 level = 1
- B, C 的 level = 2
- D, E, F 的 level = 3
- G, H, I 的 level = 4
- Depth:depth 為某個 node 到 root node 的 level 差
- B, C 的 depth = 1
- D, E, F 的 depth = 2
- G, H, I 的 depth = 3
- 此 tree 的 depth = 4
2. JavaScript 實作
2.1 Node
class Node {
constructor(data) {
this.data = data;
this.children = [];
}
add(data) {
this.children.push(new Node(data));
}
remove(data) {
this.children = this.children.filter(node => node.data !== data);
}
}
2.2 Tree
2.2.1 建立 tree
以此圖為例,建立該 tree:
class Tree {
constructor() {
this.root = null;
}
}
const t = new Tree();
t.root = new Node('A');
t.root.add('B');
t.root.add('C');
t.root.children[0].add('D');
t.root.children[0].children[0].add('G');
t.root.children[0].children[0].add('H');
t.root.children[0].children[0].add('I');
t.root.children[1].add('E');
t.root.children[1].add('F');
通常 tree 裡面會有兩個 method 用來存取 (遍歷) tree 中的每個節點,稱為 traversal (走訪)。
2.2.2 BFS – Breadth-first Search (廣度優先搜尋)
廣度優先,就是會先訪問一樣深度的 (也就是一樣廣度的 node ) 後,再往更深的深度訪問。以下圖為例,遍歷的順序為:A, B, C, D, E, F, G, H, I。
traverseBF(fn) {
const arr = [this.root];
while (arr.length) {
const node = arr.shift();
arr.push(...node.children);
fn(node);
}
}
2.2.3 DFS – Depth-first Search (深度優先搜尋)
深度優先會由左至右訪問最深的 node 後,再往右側的 node 訪問,以下圖的 tree 為例,訪問的順序為:A, B, D, G, H, I, C, E, F。

traverseDF(fn) {
const arr = [this.root];
while (arr.length) {
const node = arr.shift();
arr.unshift(...node.children);
fn(node);
}
}
完整的 code:
class Tree {
constructor() {
this.root = null;
}
traverseBF(fn) {
const arr = [this.root];
while (arr.length) {
const node = arr.shift();
arr.push(...node.children);
fn(node);
}
}
traverseDF(fn) {
const arr = [this.root];
while (arr.length) {
const node = arr.shift();
arr.unshift(...node.children);
fn(node);
}
}
}
// Building a tree
const t = new Tree();
t.root = new Node('A');
t.root.add('B');
t.root.add('C');
t.root.children[0].add('D');
t.root.children[0].children[0].add('G');
t.root.children[0].children[0].add('H');
t.root.children[0].children[0].add('I');
t.root.children[1].add('E');
t.root.children[1].add('F');
// Traverse the tree
const lettersBF = [];
const lettersDF = [];
t.traverseBF(node => {
lettersBF.push(node.data);
});
t.traverseDF(node => {
lettersDF.push(node.data);
})
console.log(lettersBF);
/*
[
'A', 'B', 'C',
'D', 'E', 'F',
'G', 'H', 'I'
]
*/
console.log(lettersDF);
/*
[
'A', 'B', 'D',
'G', 'H', 'I',
'C', 'E', 'F'
]
*/
以上為最廣義的 tree 簡介,通常比較多應用的還有二元樹、紅黑樹等等,留待之後的文章介紹~
3. 參考資料
大話資料結構(全新彩色版)
The Coding Interview Bootcamp: Algorithms + Data Structures
Tree(樹): Intro(簡介)
JavaScript 學演算法(十二)- 樹 & 二元樹
如果覺得我的文章有幫助的話,歡迎幫我的粉專按讚哦~謝謝你!