Jimmy 的架站筆記

嗨~我是 Jimmy!我可能不是你認識的第 1 個 Jimmy,但一定是最帥的那個。


資料結構筆記 3 - Tree

By Jimmy 2022-04-10
發表於 資工 資料結構-資工
Tags: tree
資料結構筆記 3 - Tree

1. 定義與特性

1.1 定義

Tree 是最常見的 non-linear data structure,構成 tree 的基本單位為 node,以下為 tree 的定義:

1.2 特性

n 為 tree 中的 node 數,任一 n > 0 的 tree 有以下的特性:

tree

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:

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。

tree

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。

tree

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 學演算法(十二)- 樹 & 二元樹


你可能也會喜歡

演算法筆記 0 – 演算法定義與 Big O Notation

演算法筆記 0 – 演算法定義與 Big O Notation

1. 演算法定義 一般來說,符合以下這 5 種特性(Characteristics)就可以稱為演算法: 1.1 輸入(Input) An algorithm may have many inputs or no inputs at all. 演算法應該具有 0 個或多個輸入。 1.2 輸出(Output) An algorithm should result at least one outpu

Read More
資料結構筆記 4 - Binary Tree (二元樹)

資料結構筆記 4 - Binary Tree (二元樹)

1. Binary Tree 定義 Binary tree 是定義更狹窄的 tree,一棵 binary tree 的定義如下: - 每個 node 最多有兩個 subTree (也就是最多有兩個 child node) - Left subTree (左子樹) 和 right subTree (右子樹) 是有順序的,順序不能任意顛倒 - 即使某個 node 只有一個 subTree,也必須區分

Read More