[ 자바스크립트(JavaScript) ] section08 - 3 - 이진트리 순회(깊이우선탐색)

📍 section08 - 3 - 이진트리 순회(깊이우선탐색)

이진트리 순회가 무엇인지 모르는 사람은 어려울 수 있는 문제다. 여기서 이진트리란 나무를 뒤집어 놓은 모양으로 한 개의 부모 노드와 2개의 자식 노드를 갖고 있는 트리구조를 일컫는다.

 

 

이진트리를 순회할 때는 3가지 방법이 있다. 전위순회(preOrder), 중위순회(inOrder), 후위순회(postOrder)가 있는데 어떻게 순회하는지 간략하게 알아보자.

 

첫 번째로 전위순회(preOrder)는 부모 → 왼쪽 자식 → 오른쪽 자식 순으로 탐색한다. 위 사진의 순회 결과는 1-2-4-5-3-6-7가 된다.

 

두 번째로 중위순회(inOrder)는 왼쪽 자식 → 부모 → 오른쪽 자식 순으로 탐색한다. 이때 주의할 점은 더 이상 자식이 없을 때까지 내려간 다음 왼쪽 자식을 탐색하는 것이다. 위 사진의 순회 결과는 4-2-5-1-6-3-7가 된다.

 

마지막으로 후위순회(postOrder)는 왼쪽 자식 → 오른쪽 자식 → 부모 순으로 탐색하는데 중위 순회와 마찬가지로 더 이상 자식이 없을 때까지 내려간 다음 오른쪽 자식을 탐색한다. 위 사진의 순회 결과는 4-5-2-6-7-3-1가 된다.

 

사실 이렇게 이론으로 어떻게 순회하는지 배워도 막상 코드로 구현하려니까 손이 잘 움직이지 않았다. 이진트리를 배열로 구현하지 않고 DFS로 구현하는 이유는 간단했는데, 노드의 위치를 쉽게 접근(indexing)할 수 있으나 기억 공간의 낭비가 심하다는 단점이 있다고 말씀하셨다. 만약, 4개의 data를 배열로 이진트리처럼 표현하면 사용하지 않는 11개의 공간이 낭비된다고 하셨다.

 

 

이 문제를 풀 때 왼쪽 자식은 현재 L(level)의 2배이고, 오른쪽 자식은 현재 L(level)의 2배+1이라는 성질을 이용해서 풀어보라고 하셨다. 결론적으로 코드는 다음과 같았는데, 신기한 점은 console.log 코드의 위치만 위아래로 달라졌을 뿐인데 결과가 다르게 나온 것이다.

 

 

728x90

 

// 전위순회(preOrder)
function solution1(v){
  function preOrder(v){
    if(v>7) return;
    else{
      console.log(v);
      preOrder(v*2);
      preOrder(v*2+1);
    }
  }
  preOrder(v);
}

solution1(1)
👉🏽 1 2 4 5 3 6 7

// 중위순회(inOrder)
function solution2(v){
  function inOrder(v){
    if(v>7) return;
    else{
      inOrder(v*2);
      console.log(v);
      inOrder(v*2+1);
    }
  }
  inOrder(v);
}

solution2(1)
👉🏽 4 2 5 1 6 3 7

// 후위순회(postOrder)
function solution3(v){
  function postOrder(v){
    if(v>7) return;
    else{
      postOrder(v*2);
      console.log(v);
      postOrder(v*2+1);
    }
  }
  postOrder(v);
}

solution3(1)
👉🏽 4 5 2 6 7 3 1