[筆記] Master The Coding Interview – 14 @地瓜大的飛翔旅程

章節連結

課程相關資訊
範例程式碼
相關文章

這篇是 Udemy 上的知名課程 – Master the Coding Interview 的部分進修心得。這篇對應的內容是「Data Structures: Tree」關於樹的第二部分簡介。

課程對應章節：126~129

請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。

範例程式碼

Binary Search Tree 非常適合用於搜尋，運用 Parent / Children 的功能來找節點
[ 特色 ]
1. 往右走的子節點，數值會比父節點大；反之亦然
2. 若為 Unbalanced ，那就會使 BigO 變為 O (n) ，類似成 Linked List 的結構
3. Ordered / Flexible Size，至少比 O (n) 好。不過沒有 O (1) 的操作

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

class BinarySearchTree {
  constructor(){
    this.root = null;
  }
  insert(value){
    //Code here
    const newNode = new Node(value)
    if(!this.root){
      this.root = newNode
    }else{
      let currentNode = this.root
      while(true){
        if(value < currentNode.value){
          if(!currentNode.left){
            currentNode.left = newNode
            return this
          }
          currentNode = currentNode.left
        }else{
          if(!currentNode.right){
            currentNode.right = newNode
            return this
          }
          currentNode = currentNode.right
        }
      }
    }
  }
}

const tree = new BinarySearchTree();
tree.insert(9)
tree.insert(4)
tree.insert(6)
tree.insert(20)
tree.insert(170)
tree.insert(15)
tree.insert(1)
JSON.stringify(traverse(tree.root))

//     9
//  4     20
//1  6  15  170

function traverse(node) {
  const tree = { value: node.value };
  tree.left = node.left === null ? null : traverse(node.left);
  tree.right = node.right === null ? null : traverse(node.right);
  return tree;
}

class Node {

constructor(value){

this.left = null;

this.right = null;

this.value = value;

}

class BinarySearchTree {

constructor(){

this.root = null;

}

insert(value){

//Code here

const newNode = new Node(value)

if(!this.root){

this.root = newNode

}else{

let currentNode = this.root

while(true){

if(value < currentNode.value){

if(!currentNode.left){

currentNode.left = newNode

return this

}

currentNode = currentNode.left

}else{

if(!currentNode.right){

currentNode.right = newNode

return this

}

currentNode = currentNode.right

}

const tree = new BinarySearchTree();

tree.insert(9)

tree.insert(4)

tree.insert(6)

tree.insert(20)

tree.insert(170)

tree.insert(15)

tree.insert(1)

JSON.stringify(traverse(tree.root))

// 9

// 4 20

//1 6 15 170

function traverse(node) {

const tree = { value: node.value };

tree.left = node.left === null ? null : traverse(node.left);

tree.right = node.right === null ? null : traverse(node.right);

return tree;

}