iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 25
0
Software Development

One Punch 一拳搞定前後端面試系列 第 25

[One Punch 一拳搞定前後端面試] DAY-25 -Binary Search Tree

Binary Search Tree

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

本篇同時發布於好讀整理版 code101

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

敬請期待~

本篇同時發布於好讀整理版 code101


上一篇
[One Punch 一拳搞定前後端面試] DAY-24 -Tree Depth First Traversal
下一篇
[One Punch 一拳搞定前後端面試] DAY-26 -Binary Search Tree - Insert
系列文
One Punch 一拳搞定前後端面試30

尚未有邦友留言

立即登入留言