자바스크립트를 이용하여 트리와 traverse, searching 을 구현해 봅시다.

Tree

class TreeNode {
  data
  children
  constructor(data) {
    this.data = data
    this.children = []
  }
}

Binary Tree

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

InOrder

왼쪽 가지 -> 현재 노드 방문-> 오른쪽 가지 순서대로 노드를 방문하고 출력

구체적으로,
1. 현재 노드의 왼쪽 가지가 있다면, 왼쪽 가지로 탐색
2. 현재 노드의 왼쪽 가지가 없다면, 현재 노드 방문
3. 현재 노드 방문 후, 오른쪽 가지가 있다면, 오른쪽 가지 탐색
4. 현재 노드에 대한 서브트리 탐색이 끝나면, 부모 노드에 대해 2번 재귀적으로 실행

const inOrderTraversal = (node) => {
  if (node !== null) {
    if (node.left !== null) inOrderTraversal(node.left)
    visit(node)
    if (node.right !== null) inOrderTraversal(node.right)
  }
}

PreOrder

현재 노드 방문 -> 왼쪽 가지 -> 오른쪽 가지

const preOrderTraversal = (node) => {
  if (node !== null) {
    visit(node)
    if (node.left !== null) preOrderTraversal(node.left)
    if (node.right !== null) preOrderTraversal(node.right)
  }
}

PostOrder

왼쪽 가지 -> 오른쪽 가지 -> 현재 노드 방문

const postOrderTraversal = (node) => {
  if (node !== null) {
    if (node.left !== null) postOrderTraversal(node.left)
    if (node.right !== null) postOrderTraversal(node.right)
    visit(node)
  }
}

Binary Search Tree

왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

O(logN) 탐색시간 이점 (균형 잡힌 경우)

BST insert 함수 구현

class BST {
  root
  constructor(root = null) {
    this.root = root
  }
  insert(data, currentNode) {
    if (currentNode === null) currentNode = new BinaryTree(data)
    else if (data < currentNode.data) {
      if (currentNode.left === null) currentNode.left = new BinaryTree(data)
      else this.insert(data, currentNode.left)
    } else if (data > currentNode.data) {
      if (currentNode.right === null) currentNode.right = new BinaryTree(data)
      else this.insert(data, currentNode.right)
    }
  }
}

올바른 BST 인지 테스트

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

const visitArr = []
const visit = (node) => {
  console.log(node.data)
}

const postOrderTraversal = (node) => {
  if (node !== null) {
    if (node.left !== null) postOrderTraversal(node.left)
    if (node.right !== null) postOrderTraversal(node.right)
    visit(node)
  }
}

class BST {
  root
  constructor(root = null) {
    this.root = root
  }
  insert(data, currentNode) {
    if (currentNode === null) currentNode = new BinaryTree(data)
    else if (data < currentNode.data) {
      if (currentNode.left === null) currentNode.left = new BinaryTree(data)
      else this.insert(data, currentNode.left)
    } else if (data > currentNode.data) {
      if (currentNode.right === null) currentNode.right = new BinaryTree(data)
      else this.insert(data, currentNode.right)
    }
  }
}
const bst = new BST(new BinaryTree(8))
bst.insert(4, bst.root)
bst.insert(10, bst.root)
bst.insert(2, bst.root)
bst.insert(6, bst.root)
bst.insert(20, bst.root)

postOrderTraversal(bst.root)

출력 (postOrderTraversal)
2
6
4
20
10
8

Binary Heap

• 최대값과 최소값을 빠르게 탐색하기 위해 고안된 자료구조
• Complete Binary Tree

1. Binary Heap에 노드 삽입
   1) 맨 마지막 노드에 삽입
   2) 노드 인덱스, 부모 노드 인덱스
   3) Heapify
   
2. Binary Heap에 노드 출력
   1) 맨 첫 번째 요소 pop
   2) 맨 마지막 요소를 맨 첫 번째 요소로 넣기
   3) Heapify (왼쪽 자식 우선 탐색)

class MinHeap {
  heap
  constructor() {
    this.heap = [null]
  }
  heapPush(value) {
    this.heap.push(value)
    let currIdx = this.heap.length
    let parentIdx = Math.floor(currIdx / 2)

    while (this.heap[currIdx] > this.heap[parentIdx] || currIdx === 1) {
      ;[this.heap[currIdx], this.heap[parentIdx]] = [this.heap[parentIdx], this.heap[currIdx]]
      currIdx = parentIdx
      parentIdx = Math.floor(currIdx / 2)
    }
  }
  heapPop() {
    this.heap[1] = this.heap.pop()
    let currIdx = 1
    let leftChildIdx = currIdx * 2,
      rightChildIdx = currIdx * 2 + 1

    while (leftChildIdx <= this.heap.length) {
      // left, right child 존재
      if (rightChildIdx <= this.heap.length) {
        if (this.heap[currIdx] > this.heap[leftChildIdx]) {
          ;[this.heap[currIdx], this.heap[leftChildIdx]] = [this.heap[leftChildIdx], this.heap[currIdx]]
          currIdx = leftChildIdx
          leftChildIdx = currIdx * 2
          rightChildIdx = currIdx * 2 + 1
        } else if (this.heap[currIdx] > this.heap[rightChildIdx]) {
          ;[this.heap[currIdx], this.heap[rightChildIdx]] = [this.heap[rightChildIdx], this.heap[currIdx]]
          currIdx = rightChildIdx
          leftChildIdx = currIdx * 2
          rightChildIdx = currIdx * 2 + 1
        } else break
      } else {
        // left child 만 존재
        if (this.heap[currIdx] > this.heap[leftChildIdx]) {
          ;[this.heap[currIdx], this.heap[leftChildIdx]] = [this.heap[leftChildIdx], this.heap[currIdx]]
          currIdx = leftChildIdx
          leftChildIdx = currIdx * 2
          rightChildIdx = currIdx * 2 + 1
        } else break
      }
    }
  }
}