Skip to main content

Binary Search Tree

本篇來介紹 Binary Search Tree(二元搜尋樹)

簡介 Binary Search Tree​

Binary Search Tree 規定：

  1. 每個 node 只能有兩個 children，或是沒有
  2. node 左邊的 child 只能小於 node
  3. node 右邊的 child 只能大於 node

若是只符合 1 ，不符合第 2 跟 3 ，它就是普通的 Binary Tree ，而非 Binary Search Tree。

大概長這樣子:

binary-search-tree

實作 BinarySearchTree 的 Node​

JavaScript 實作 BinarySearchTree 的 Node​

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

有些文章的 data 會是 key, value ，意思相同

Java 實作 BinarySearchTree 的 Node​

class BinarySearchTree {
  Node root;

  BinarySearchTree() {
      root = null;
  }

  class Node {
    int data;
    Node left;
    Node right;
  }

  public Node(int item) {
    data = item;
    left = right = null;
  }

}

下一篇我們來幫這個 BinarySearchTree 加一些功能吧！

本文同時發布於鐵人賽