[資料結構]Binary Tree — 二元樹

發表於 2021-10-02 更新於 2023-12-01 分類於演算法

想必大家在刷leetcode時候，刷到特定的題目的時候都曾經看過這樣的圖片，這就是Binary tree，但在認識Binary tree之前，讓我們先來認識tree這種資料結構吧!

想必大家在刷 leetcode 時候，刷到特定的題目的時候都曾經看過這樣的圖片，這就是 Binary tree，但在認識 Binary tree 之前，讓我們先來認識 tree 這種資料結構吧!

Tree

是一種抽象的資料結構，由一個以上的節點所組成，每個節點可以有多個子節點，最頂端的根節點稱為 root ，最下面的層級的節點稱為 leaves(2, 1, 7 …)

而節點與節點之間的關係名詞可以參考下圖

Root — 根節點，最上層的節點
Edge— 節點與節點之間的連結
Parent — 父節點，與節點相鄰的上層節點
Children — 子節點，與節點相鄰的下層節點
Siblings — 兄弟節點，層級在同一層，而且擁有共同的父節點
Leaf nodes — 葉子節點，沒有子節點的節點
Subtree — 子樹，該節點以及其左右子節點
Height — 樹的高度，可以解讀為樹有幾層

Binary Tree — 二元樹

每個節點的子節點最少 0 個，最多2個，每個節點會紀錄三種資料

自己本身的值
left-child，左子節點
right-child，右子節點

與一般樹的比較如下，Binary Tree 每個節點最多就是兩個子節點

Binary Tree 的種類

full

所有的 leaf node 都在同一個層級
每個節點的子節點為 0 個或是 2 個

Complete

除了最後一層 leaf node 之外，每層都是填滿的狀態
所有的 leaf node 都會向左靠攏，因此 leaf nodes 有可能會沒有右邊的兄弟節點

Degenerate

每個節點只會有一個右子節點或是左子節點

Perfect

所有的 leaf node 都在同一個層級
除了 leaf node 之外，每個節點都有兩個子節點

Balance

左子樹和右子樹的層級相差不超過 1

Skewed

每個節點固定只有右子節點或左子節點，如下圖

Binary Search Tree(縮寫 BST) — 二元搜尋樹

具有 Binary Tree 的特性，每個節點的子節點不超過 2 個，除此之外，左邊的子節點必定小於根節點，右邊的子節點必定大於根節點，因此整棵樹最左邊的節點必定是最小的，最右邊的節點必定是最大的，也因為 Binary Search Tree 這樣的特性，所以不管是新增節點、刪除節點、搜尋節點的時間複雜度都是 O(log n)。

用 js 實作出 Binary Search Tree

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
    this.queue = [];
  }
  insertNode(value) {
    let current = new TreeNode(value);
    let target = null;
    let nowPos = this.root;
    while (nowPos !== null) {
      target = nowPos;
      if (current.value < nowPos.value) {
        nowPos = nowPos.left;
      } else {
        nowPos = nowPos.right;
      }
    }
    if (target === null) {
      this.root = current;
    } else if (current.value < target.value) {
      target.left = current;
    } else {
      target.right = current;
    }
  }
}

let tree = new BinarySearchTree();
tree.insertNode(10);
tree.insertNode(8);
tree.insertNode(11);
tree.insertNode(5);
tree.insertNode(9);
tree.insertNode(15);
tree.insertNode(2);
tree.insertNode(19);
tree.insertNode(13);