트리

일반적인 트리

class TreeNode {
  constructor(val) {
    this.value = val;
    this.children = [];
  }
}

이진 트리

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

class BinaryTree {
  constructor() {
    this._root = null;
  }

  // 선순위 순회
  traversePreOreder(node = this._root) {
    if (node instanceof BinaryTreeNode) {
      console.log(node.value);
      if (node.left) this.traversePreOreder(node.left);
      if (node.right) this.traversePreOreder(node.right);
    }
  }

  // 재귀를 사용하지 않는 선순위 순회
  traversePreOrederIterative(node = this._root) {
    const nodeStack = [];
    if (node instanceof BinaryTreeNode) nodeStack.push(node);

    while (nodeStack.length > 0) {
      const cur = nodeStack.pop();
      console.log(cur.value);

      if (cur.right) nodeStack.push(cur.right);
      if (cur.left) nodeStack.push(cur.left);
    }
  }

  // 중순위 순회
  traverseInOrder(node = this._root) {
    if (node instanceof BinaryTreeNode) {
      if (node.left) this.traverseInOrder(node.left);
      console.log(node.value);
      if (node.right) this.traverseInOrder(node.right);
    }
  }

  // 재귀를 사용하지 않는 중순위 선회
  traverseInOrderOterative(node = this._root) {
    const cur = node;
    const stack = [];
    let done = false;

    while (!done) {
      if (cur !== null) {
        stack.push(cur);
        cur = cur.left;
      } else {
        if (stack.length > 0) {
          cur = stack.pop();
          console.log(cur.value);
          cur = cur.right;
        } else {
          done = true;
        }
      }
    }
  }

  // 후순위 선회
  traversePostOrder(node = this._root) {
    if (node instanceof BinaryTreeNode) {
      if (node.left) this.traversePostOrder(node.left);
      if (node.right) this.traversePostOrder(node.right);
      console.log(node.value);
    }
  }

  // 재귀를 사용하지 않는 후순위 순회
  traversePostOrderIterative(node = this._root) {
    const stack1 = [];
    const stack2 = [];
    if (node instanceof BinaryTreeNode) stack1.push(node);

    while (stack1.length > 0) {
      const cur = stack1.pop();
      stack2.push(cur.value);

      if (cur.left) stack1.push(cur.left);
      if (cur.right) stack1.push(cur.right);
    }

    while (stack2.length > 0) {
      console.log(stack2.pop());
    }
  }

  // 단계순위 순회
  traverseLevelOrder(node = this._root) {
    const queue = [];
    if (node instanceof BinaryTreeNode) queue.push(node);

    while (queue.length > 0) {
      const cur = queue.shift();
      console.log(cur.value);
      if (cur.left) queue.push(cur.left);
      if (cur.right) queue.push(cur.right);
    }
  }
}

이진 검색 트리

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

class BinarySearchTree {
  constructor() {
    this._root = null;
  }

  // 삽입
  insert(val) {
    const node = new BinaryTreeNode(val);
    if (!this._root) this._root = node;
    else {
      const cur = this._root;
      while (1) {
        if (cur.value > val) {
          if (cur.left) cur = cur.left;
          else {
            cur.left = node;
            break;
          }
        } else if (cur.value < val) {
          if (cur.right) cur = cur.right;
          else {
            cur.right = node;
            break;
          }
        } else break;
      }
    }
  }

  // 삭제
  remove(val) {
    function findMin(node) {
      const cur = node;
      while (cur.left) {
        cur = cur.left;
      }
      return cur;
    }

    function deleteRecursively(node, data) {
      if (!node) return null;
      if (data < node.value) {
        node.left = deleteRecursively(node.left, data);
      } else if (data > node.value) {
        node.right = deleteRecursively(node.right, data);
      } else {
        if (!node.left && !node.right) return null;
        if (!node.left || !node.right) return node.left || node.right;
        if (node.left && node.right) {
          const temp = findMin(node.right);
          node.value = temp.value;
          node.right = deleteRecursively(node.right, temp.value);
        }
      }
      return node;
    }

    return deleteRecursively(this._root, val);
  }

  // 검색
  findNode(val) {
    const cur = this._root;

    while (cur) {
      if (cur.value > val) cur = cur.left;
      else if (cur.value < val) cur = cur.right;
      else return true;
    }

    return false;
  }
}