iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 26
0
Software Development

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

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

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

本文同時發布於好讀整理版


上一篇
[One Punch 一拳搞定前後端面試] DAY-25 -Binary Search Tree
下一篇
[One Punch 一拳搞定前後端面試] DAY-27 -Binary Search Tree - Contains
系列文
One Punch 一拳搞定前後端面試30

尚未有邦友留言

立即登入留言