이진트리 순회(Binary Tree traversal)

이진트리 순회가 개념적으로 머리에 딱 박히지 않고 자꾸 눈에 맞고 튕겨나가서 고민하다가
결국 직접 알고리즘을 짜 보고서야 "아 씨 이거였구나...!!!" 싶었다.
낑낑대던 허들을 넘어선 상쾌한 정복감이 사라지기 전에 얼른 정리해본다.

1. 이진트리의 순회

트리구조 순회에는 대표적으로 3가지 방법이 있다.

1. 중위 순회(Inorder traversal) : Left ⇨ Root ⇨ Right

2. 전위 순회(Preorder traversal) : Root ⇨ Left ⇨ Right

3. 후위 순회(Postorder traversal) : Left ⇨ Right ⇨ Root

예를 들어 중위 순회를 통해 위 이진트리를 순회하면 1 ⇨ 3 ⇨ 4 ⇨ 6 ⇨ 7 ⇨ 8 ⇨ 10 ⇨ 13 ⇨ 14 순서대로 노드를 들르게 된다는 것이다.

난 이게 이해가 안 되었다. 왼쪽 -> 나 -> 오른쪽 순서라며. 어떻게 적용되길래 저 순서가 나와??
하여간 믿을 놈 하나도 없다. 안되겠다 직접 짜보자.

2. 중위 순회의 로직

간단한 수도코드를 통해 중위 순회의 작동원리를 나타내자면 아래와 같다.

function inorder(루트) {

  if(왼쪽에 자식노드가 있으면) {
    inorder(왼쪽자식노드)
  }
  
  console.log(루트)
  
  if(오른쪽에 자식노드가 있으면) {
    inorder(오른쪽자식노드)
  }
  
}

이렇게 재귀함수를 활용하면 Stack의 맨 위에 놓인 함수부터 착착 풀리면서
1 ⇨ 3 ⇨ 4 ⇨ 6 ⇨ 7 ⇨ 8 ⇨ 10 ⇨ 13 ⇨ 14 순으로 콘솔에 찍히게 된다.

이렇게 해놓고 보면 Left -> Root -> Right 가 무슨 의미였던건지 알긴 하겠는데...
저것만 덜렁 써놓고 순회원리를 이해하라는건 너무 추상화한거 아냐...??

아무튼 이케이케 해서 중위 순회의 로직이 이해되었다면 전위, 후위 순회는 자동문이다.
함수 작동의 순서만 바꾸면 되니까.
허들을 뛰어 넘자.