[자료구조] binary tree(이진트리)

 

1) concept

binary tree는 이진트리라고 하며,

tree의 속성에서 자식 노드를 최대 2개로 제한한 트리이다. (자식 노드가 0개여도, 이진트리이다.)

(+) 공집합도 이진트리인 이유

루트 노드를 중심으로 두 개의 서브 트리(큰 트리에 속하는 작은 트리)로 나뉘어 진다. 또한 나뉘어진 두 서브 트리도 모두 이진 트리어야 한다.

위는 이진트리를 재귀적 정의로 표현한 것인데, 공집합도 이진트리여야 이는 성립된다. 재귀적으로 조건을 확인해갔을 때, leaf node 에 다다랐을 때, 정의가 만족되기 때문이다. 자연스럽게 노드가 하나 뿐인 것도 이진 트리 정의에 만족하게 된다.

 

 

2) 이진트리의 종류

full binary tree(정이진 트리), complete binary tree(완전 이진트리), balanced binary tree(균형이진트리) 등

 

 

3) 이진트리를 코드 상에서 저장하는 방식

1. 리스트 : level 0 에서부터 차례대로 내려가면서 왼쪽부터 저장
2. 재귀 + 리스트
3. 노드 클래스

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;
  }
}

 

 

4) 이진트리의 순회 연산

(1) 전위순회

자기 자신 → 왼쪽 → 오른쪽

BinaryTree.prototype.traversePreOrder = function(){
    traversePreOrderHelper(this._root);
    function traversePreOrderHelper(node) {
        if(!node){ return; }
        console.log(node.value);
        // 루트값 접근 이후에 왼쪽, 오른쪽
        traversePreOrderHelper(node.left);
        traversePreOrderHelper(node.right)
    }
}

 

(2) 중위 순회

왼쪽 → 자기 자신 → 오른쪽

BinaryTree.prototype.traverseInOrder = function(){
    traverseInOrderHelper(this._root);
    function traverseInOrderHelper(noe){
        if(!node) return; // 종료조건
        traverseInOrderHelper(node.left);
        console.log(node.value);
        traverseInOrderHelper(node.right);
    }
}

 

(3) 후위 순위

왼쪽 → 오른쪽 → 자기 자신

BinaryTree.prototype.traversePostOrder = function(){
    traverseInOrderHelper(this._root);
    function traverseInOrderHelper(noe){
        if(!node) return; // 종료조건
        traverseInOrderHelper(node.left);
				traverseInOrderHelper(node.right);        
				console.log(node.value);
    }
}