[자료구조/알고리즘] 자료구조 기초 : Binary Tree & Binary Search Tree

hosik kim·2021년 10월 6일
0

With CodeStates

목록 보기
10/45
post-thumbnail

💡Binary Tree

  • 번역하면 이진트리
  • 각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리구조
  • 자식 노드를 최대 2개만 가질 수 있으므로 두 자식 노드를 왼쪽 자식, 오른쪽 자식으로 구별해서 지칭한다.

📌종류

Full Binary Tree

  • 번역하면 정이진트리
  • 모든 노드가 2개 또는 0개의 자식을 갖는 이진트리

Complete Binary Tree

  • 번역하면 완전이진트리
  • 마지막 레벨을 제외한 모든 노드가 가득 차있으며, 마지막 레벨의 노드는 전부 차있지않더라도 왼쪽은 채워진 트리구조

Perfect Binary Tree

  • 번역하면 포화이진트리
  • 정이진트리이면서 완전이진트리인 경우로, 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져있는 트리구조

💡Binary Search Tree

  • 번역하면 이진탐색트리
  • 모든 왼쪽자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 트리구조

📌BST 구현

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.inert(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);
    }
    callback(this.value);
    if(this.right) {
      this.right.preorder(callback);
    }
  }
  // tree 를 후위 순회
  postorder(callback) {
    if(this.left) {
      this.left.postorder(callback);
    }
    if(this.right) {
      this.right.postorder(callback);
    }
    callback(this.value);
  }
}
profile
안되면 될 때까지👌

0개의 댓글