Skip to main content

Binary Search Tree Insert

題目: 給一個值 x，請將這個值放到 Binary Search Tree 中適當的位置。

想法​

這題是碰到二元搜尋樹常碰到的問題。

放入時會通過每一個 node ，直到最後沒有 child 時，再決定要放到左邊或右邊。

塞入時只需檢查:

  1. 該 Node 是否有左邊 child ，且該 Node 的左邊 child 的值是否小於 x，若是就通過繼續往下，若是 null 則新增一個左邊 child Node。
  2. 該 Node 是否有右邊 child ，且該 Node 的右邊 child 的值是否大於 x，若是就通過繼續往下，若是 null 則新增一個右邊 child Node。

JavaScript 實作​

我們用 recursion (遞迴)方法來解決 insert(data)。

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

  insert(data) {
    if (data < this.data && this.left) {
      this.left.insert(data);
    } else if (data < this.data) {
      this.left = new Node(data);
    } else if (data > this.data && this.right) {
      this.right.insert(data);
    } else if (data > this.data) {
      this.right = new Node(data);
    }
  }

Java 實作​

Java 也用遞迴

public void insertNode(int key) {
    root = insertNode(root, new Node(key));
}

private Node insertNode(Node currentParent, Node newNode) {

    if (currentParent == null) {
        return newNode;
    } else if (newNode.key > currentParent.key) {
        currentParent.right = insertNode(currentParent.right, newNode);
    } else if (newNode.key < currentParent.key) {
        currentParent.left = insertNode(currentParent.left, newNode);
    }

    return currentParent;
}

本文同時發布於鐵人賽