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 加一些功能吧!

本文同時發布於鐵人賽