Tree

//! 1진트리
class Tree {
  //tree의 constructor를 생성 : tree의 자식 노드들을 엘리먼트로 담을 children 배열로 선언
  constructor(value) {
    this.value = value
    this.children = []
  }

  // 자식 노드 생성 메소드 구현 : new 키워드로 자식 노드를 생성 한 후, children 배열에 push
  insertNode(value) {
    const childNode = new Tree(value)
    this.children.push(childNode)
  }

  // tree에서 value값을 탐색하기 위한 메소드 구현
  contains(value) {
    // 현재 노드의 value 값이 찾는 값과 일치한다면 true 반환
    if (this.value === value) {
      return true
    }

    // 자식 노드에서 value값을 탐색하기 위해 반복문과 재귀패턴 사용
    for (let childNode of this.children) {
      if (childNode.contains(value)) {
        return true
      }
    }
    // 조건에 해당하지 않으면 false 반환
    return false
  }
}

//! 작으면 왼쪽 크면 오른쪽으로 가는 이진 트리
class BinarySearchTree {
  //BST의 constructor를 구현합니다.
  constructor(value) {
    this.value = value
    this.left = null
    this.right = null
  }
  // tree에 value를 추가합니다.
  insert(value) {
    // 인자의 value가 this.value보다 작을 경우, 왼쪽 노드에서 진행합니다.
    if (value < this.value) {
      // this.left에 아무것도 없을 경우, 새로운 자식 노드를 추가합니다.
      if (this.left === null) {
        this.left = new BinarySearchTree(value)
      }
      // this.left의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀를 사용합니다.
      else {
        this.left.insert(value)
      }
    }
    // 인자의 value가 this.value보다 클 경우, 오른쪽 노드에서 진행합니다.
    else if (value > this.value) {
      // this.right에 아무것도 없을 경우, 새로운 자식 노드를 추가합니다.
      if (this.right === null) {
        this.right = new BinarySearchTree(value)
      }
      // this.left의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀를 사용합니다.
      else {
        this.right.insert(value)
      }
    } else {
      // 이미 value값을 포함하고 있습니다.
    }
  }
  // tree의 value값을 탐색합니다.
  contains(value) {
    // 찾는 value값이 노드의 value와 일치한다면, true를 리턴합니다.
    if (value === this.value) {
      return true
    }
    // 찾는 value값이 노드의 value 보다 작다면, 왼쪽에서 contains의 재귀를 진행합니다.
    if (value < this.value) {
      return !!(this.left && this.left.contains(value))
    }
    // 찾는 value값이 노드의 value 보다 크다면, 오른쪽에서 contains의 재귀를 진행합니다.
    if (value > this.value) {
      return !!(this.right && this.right.contains(value))
    }
  }
  //tree를 전위 순회 합니다.
  preorder(callback) {
    callback(this.value)
    if (this.left) {
      this.left.preorder(callback)
    }
    if (this.right) {
      this.right.preorder(callback)
    }
  }
  // tree를 중위 순회 합니다
  inorder(callback) {
    if (this.left) {
      this.left.inorder(callback)
    }
    callback(this.value)
    if (this.right) {
      this.right.inorder(callback)
    }
  }
  //tree를 후위 순회 합니다
  postorder(callback) {
    if (this.left) {
      this.left.postorder(callback)
    }
    if (this.right) {
      this.right.postorder(callback)
    }
    callback(this.value)
  }
}

class Tree2 {
  constructor(value, level = 0) {
    this.value = value
    this.left = null
    this.right = null
    this.level = level
  }
  insert(value, parent = {}, completedLevel) {
    function findCurrentLevel(value) {
      let result = 0
      while (value > 1) {
        result++
        value = ~~(value / 2)
      }
      return result
    }
    let node = this
    if (node.left === null) node.left = new Tree2(value, this.level + 1)
    else if (node.right === null) node.right = new Tree2(value, this.level + 1)
    else {
      const now = this
      if (Object.keys(parent).length > 0) {
        if (node.right === null) this.insert(value, now)
        else if (parent.right.right === null) parent.right.insert(value, parent)
        else node.left.insert(value, now)
      } else node.left.insert(value, now)
    }
  }
}
let tree2 = new Tree2(1)
tree2.insert(2)
tree2.insert(3)
tree2.insert(4)
tree2.insert(5)
tree2.insert(6)
tree2.insert(7)
tree2.insert(8)
tree2.insert(9)
tree2.insert(10)
tree2.insert(11)
tree2.insert(12)
// 위에서부터 가로 순서대로 1,2,3... 들어가는 트리를 만들어보려고 했는데 너무 복잡하다
// 현재 코드로는 11까지만 정상적으로 들어가는데
// 보안하려면 현재 값이 어느레벨인지, 해당 레벨의 뿌리를 2개씩 나눴을때 몇번째 덩어리에 속했는지를 파악해서
// 어느 부모까지 올라가야하는지 확인해야할것같다
// -> 부모가 왼쪽인지 오른쪽인지를 확인하면서 가면 될것같았는데 부모의 부모를 참조 못함
// -> 물론 노드에 부모 정보를 다 넣어주면 되지만 그러면 노드하나하나가 너무 무거워짐