[JavaScript/section 8] 03 - 이진트리 순회

📌 03 - 이진트리 순회(깊이우선탐색)

이진트리 순회를 연습해보는 문제이다. 처음 나온 개념이기에 먼저 개념 정리를 할 필요가 있다.

이진트리에 대해서 먼저 알아보자❗
나무를 뒤집어 놓은 모양과 같으며 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 다음 그림과 같다.

이진트리를 순회하는 방법에는 전위순회(preorder), 중위순회(inorder), 후위순회(postorder)의 3가지가 있는데, 이는 부모 노드를 기준으로 하고 있다.

전위순회(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)할 수 있으나 사용하지 않는 공간이 존재할 경우 기억 공간의 낭비가 심하다는 단점이 있기 때문이다.

📝 풀이 방법

다음 코드를 보면 answer += v + ' ' 식의 위치에 따라 순회하는 방법이 달라지는 것을 확인할 수 있다. 그대로 외우는 것도 방법일 수 있겠지만 스택 프레임을 직접 써보면서 과정을 살펴보면 이해하는데 많은 도움이 된다.

• 왼쪽 자식 노드는 부모 노드의 * 2에 해당하고, 오른쪽 자식 노드는 부모 노드의 * 2 + 1에 해당한다.

function solution(n) {
  let answer = '';
  function DFS(v) {
    if (v > 7) return;
    else {
      // 전위순회
      answer += v + ' ';
      DFS(v * 2);
      // 중위순회
      // answer += v + ' ';
      DFS(v * 2 + 1);
      // 후위순회
      // answer += v + ' ';
    }
  }
  DFS(n);
  return answer;
}

console.log(solution(1));

💻 참고한 사이트

https://ywtechit.tistory.com/m/309

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