Binary Search Tree 구현 : pre-order / in-order / post-order

📌  Binary Search Tree

 

class BinarySearchTree {
  constructor(value){
    this.value = value;
    this.left = null;
    this.right = null;
  }
  
  insert(value) {
    
    if(value < this.value){
      if(this.left === null){
        this.left = new BinarySearchTree(value);
      }
      else{
        this.left.insert(value);
      }
    }
    else if(value > this.value){
      if(this.right === null){
        this.right = new BinarySearchTree(value);
      }
      else{
        this.right.insert(value);
      }
    }
    
  }
  
  contains(value) {
  
  	if(value === this.value){
      return true;
    }
    else if(this.left === null || this.right === null){
      return false;
    }
    
    if(value < this.value){
      return (this.left && this.left.contains(value));
    }
    if(value > this.value){
      return (this.right && this.right.contains(value));
    }
    
  }
  
  preorder(callback) {
  
    callback(this.value);
    if(this.left){
      this.left.preorder(callback);
    }
    if(this.right){
      this.right.preorder(callback);
    }
    
  }
  
  inorder(callback) {
    
    if(this.left){
      this.left.inorder(callback);
    }
    callback(this.value);
    if(this.right){
      this.right.inorder(callback);
    }
    
  }
  
  postorder(callback) {
  
    if(this.left){
      this.left.postorder(callback);
    }
    if(this.right){
      this.right.postorder(callback);
    }
    callback(this.value);
    
  }
}

let arr = [];
let callback = function (value) {
  arr.push(value);
};

const rootNode = new BinarySearchTree(10);
rootNode.insert(8);
rootNode.insert(3);
rootNode.insert(7);
rootNode.insert(5);
rootNode.insert(15);
rootNode.insert(16);
rootNode.insert(11);
rootNode.insert(14);

rootNode.postorder(callback);

 

 

📌  Tree

 

 

 

📍  Tree Traversal : preorder  

 

[10, 8, 3, 7, 5, 15, 11, 14, 16]

왼쪽부터 검사하되, (루트 노드에서 시작해서) 만나는 노드 족족 검사 수행 후 오른쪽으로 넘어가는 형태

 

 

📍  Tree Traversal : inorder  

 

inorder 동작 과정

[3, 5, 7, 8, 10, 11, 14, 15, 16]

제일 작은 왼쪽 노드부터 제일 큰 오른쪽 노드까지 나열하는 형태

 

 

📍  Tree Traversal : postorder  

 

[5, 7, 3, 8, 14, 11, 16, 15, 10]

왼쪽부터 검사하되, (가장 말단 노드에서 시작해서) 만나는 노드 족족 검사 수행 후 오른쪽으로 넘어가는 형태

preorder와 다른 점은, 루트 노드를 가장 마지막에 검사한다는 점이다. (중간에 거치지 않음)