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;
}

本文同時發布於鐵人賽