하루5분코딩"Binary Search Tree"

Binary Search Tree : Tree의 종류중 하나, 이진탐색트리는 최대 2개의 자식만 갖는다.

• 이방법은 노드의 값이 정렬방법에 따라 순서가 존재하는데, 노드 왼쪽 서브트리에는 노드값보다 작은 값이, 오른쪽에는 노드값 보다 큰 값이 온다.

순회

그래프의 경우 비선형 구조이기 때문에 모든 노드를 탐색하기 위해 특별한 방법을 사용한다. 탐색 순서를 정하는 방법에 따라 DFS(Depth First Search), BFS(Breadth Firts Search)의 두 가지 방법이 있다. 트리또한 그래프의 일종이기 때문에 두가지 방법을 사용할수 있다.

탐색 방법

• 전위 순회(Preorder Traversal) : 부모 -> 좌 -> 우
• 중위 순회(Inorder Traversal): 좌 -> 부모 -> 우
• 후위 순회(Postorder Traversal): 좌 -> 우 -> 부모

순회결과

• 전위 순회 : 6 4 2 5 9 8 11 10 13
• 중위 순회 : 2 4 5 6 8 9 10 11 13
• 후위 순회 : 2 5 4 8 10 13 11 9 6

Method

• insert(value) - 이진 탐색 트리에 노드를 추가합니다.
• contains(value) - 이진 탐색 트리에 해당 노드가 존재하는지 여부를 반환합니다.
• inorder(callback) - 이진 탐색 트리를 중위순회 합니다.

  insert(value) {
    let newnode = new BinarySearchTreeNode(value);
      if(this.value > value){
        if(this.left === null){
          this.left = newnode
        }else{
          return this.left.insert(value)
        }
      }
      else if(this.value < value){
        if(this.right === null){
          this.right = newnode
        }else{
          return this.right.insert(value)
        }
    }
  }

  contains(value) {
  if(this.value === value){
    return true;
  }else if(this.value < value){
    if(this.right === null){
      return false;
    }else if(this.right.contains(value)){
      return true;
    }
  }else if(this.value > value){
    if(this.left === null){
      return false;
    }else if(this.left.contains(value)){
      return true;
    }
  }
  return false;
}

inorder(callback) {//중위순회 왼 루트 오른쪽 
 if(this.left !== null){
   this.left.inorder(callback)
 }
 callback(this.value)
 if(this.right !== null){
   this.right.inorder(callback)
 }
}