[알고리즘] 재귀 함수를 이용한 트리 순회 알고리즘

재귀 함수를 이용하는 트리 순회는 전위 순회, 중위 순회, 후위 순회가 있다. 

 

전위 순회

루트 노드를 방문하고, 왼쪽 서브 트리를 전위 순회한 뒤 오른쪽 서브 트리를 전위 순회하는 방식이다. 

        1
       / \
      /   \
     2     3
   /  \   /  \
  4    5 6    7

트리가 있다면 

1. 루트 노드 [ 1 ] 을 방문한다. 

2. [ 2 ]를 방문한다. 

3. [ 2 ]의 왼쪽 서브 트리로 이동한다. 

4. [ 4 ]를 방문한다. 

5. [ 4 ]의 왼쪽, 오른쪽 서브 트리가 없으므로 올라간다. 

6. [ 2 ]의 오른쪽 서브 트리로 이동한다. 

 

...

 

방식으로 [ 1, 2, 4, 5, 3, 6, 7 ] 순서대로 순회한다. 

preorder(tree) {
    방문(tree.root);
    
    preorder(tree.left);
    preorder(tree.right);
}

으로 표현할 수 있다. 

 

중위 순회

왼쪽 서브 트리를 먼저 중위 순회하고, 노드를 방문한 뒤 오른쪽 서브 트리를 중위 순회하는 방식이다. 

        1
       / \
      /   \
     2     3
   /  \   /  \
  4    5 6    7

트리가 있다면

1. [ 1 ]의 왼쪽 서브 트리로 이동한다. 

2. [ 2 ]의 왼쪽 서브 트리로 이동한다. 

3. [ 4 ]의 왼쪽 서브 트리가 없으므로 4를 방문한다. 

4. [ 4 ]의 오른쪽 서브 트리가 없으므로 올라간다. 

5. [ 2 ]를 방문한다. 

6. [ 2 ]의 오른쪽 서브 트리로 이동한다. 

7. [ 5 ]의 왼쪽 서브 트리가 없으므로 5를 방문한다. 

8. [ 5 ]의 오른쪽 서브 트리가 없으므로 올라간다. 

9. [ 1 ]을 방문한다. 

 

... 

 

방식으로 [ 4, 2, 5, 1, 3, 6, 7 ] 순서대로 순회한다. 

inorder(tree) {
    inorder(tree.left);
    방문(tree.root);
    inorder(tree.right);
}

으로 표현할 수 있다. 

 

후위 순회

왼쪽 서브 트리를 후위 순회한 뒤 오른쪽 서브 트리를 후위 순회하고 노드를 방문하는 방식이다. 

        1
       / \
      /   \
     2     3
   /  \   /  \
  4    5 6    7

1. [ 1 ]의 왼쪽 서브 트리로 이동한다.

2. [ 2 ]의 왼쪽 서브 트리로 이동한다. 

3. [ 4 ]는 왼쪽, 오른쪽 서브 트리가 없으므로 [ 4 ]를 방문한다. 

4. 올라간다.

5. [ 2 ]의 오른쪽 서브 트리로 이동한다. 

6. [ 5 ]는 왼쪽, 오른쪽 서브 트리가 없으므로 [ 5 ]를 방문한다. 

7. [ 2 ]를 방문한다. 

8. 올라간다.

9. [ 1 ]의 오른쪽 서브 트리로 이동한다. 

 

... 

 

방식으로 [ 4, 5, 2, 6, 7, 3, 1 ] 순서대로 순회한다. 

postorder(tree) {
  postorder(tree.left);
  postorder(tree.right);
  방문(tree.root);
}

으로 표현할 수 있다.