[크래프톤 정글] 트리의 순회 방법

트리 예시

우선, 다음과 같은 간단한 이진 트리를 가정하자:

      1
     / \
    2   3
   / \
  4   5

위의 트리에서 노드 1이 루트 노드이고, 2와 3이 각각 루트의 왼쪽과 오른쪽 자식 노드이며, 4와 5는 2의 자식 노드다.

1. 전위 순회 (Preorder Traversal)

전위 순회에서는 루트 -> 왼쪽 -> 오른쪽 순으로 노드를 방문한다.

1. 루트(1)를 먼저 방문
2. 왼쪽 서브트리로 이동하여 2를 방문
3. 다시 왼쪽 서브트리로 이동하여 4를 방문
4. 4의 부모 노드인 2로 돌아가 오른쪽 자식인 5를 방문
5. 루트 노드의 오른쪽 서브트리로 이동하여 3을 방문

방문 순서: 1 → 2 → 4 → 5 → 3

2. 중위 순회 (Inorder Traversal)

중위 순회에서는 왼쪽 -> 루트 -> 오른쪽 순으로 노드를 방문한다.

1. 가장 왼쪽 노드(4)까지 내려가 4를 방문
2. 4의 부모 노드인 2로 올라가 2를 방문
3. 2의 오른쪽 자식인 5를 방문
4. 루트 노드(1)로 올라가 1을 방문
5. 오른쪽 서브트리로 이동하여 3을 방문

방문 순서: 4 → 2 → 5 → 1 → 3

3. 후위 순회 (Postorder Traversal)

후위 순회에서는 왼쪽 -> 오른쪽 -> 루트 순으로 노드를 방문한다.

1. 가장 왼쪽 노드(4)까지 내려가 4를 방문
2. 4의 부모 노드인 2로 돌아와 오른쪽 자식인 5를 방문
3. 2를 방문
4. 루트 노드의 오른쪽 서브트리로 이동하여 3을 방문
5. 마지막으로 루트 노드(1)를 방문

방문 순서: 4 → 5 → 2 → 3 → 1

4. 레벨 순회 (Level Order Traversal)

레벨 순회에서는 트리의 깊이(depth)에 따라 위에서 아래로, 왼쪽에서 오른쪽으로 노드를 방문한다.

1. 루트 노드(1)를 방문
2. 루트 노드의 왼쪽 자식(2)을 방문하고, 그 다음 오른쪽 자식(3)을 방문
3. 2의 자식인 4와 5를 순서대로 방문

방문 순서: 1 → 2 → 3 → 4 → 5

요약

각 순회 방법의 노드 방문 순서

• 전위 순회: 1 → 2 → 4 → 5 → 3
• 중위 순회: 4 → 2 → 5 → 1 → 3
• 후위 순회: 4 → 5 → 2 → 3 → 1
• 레벨 순회: 1 → 2 → 3 → 4 → 5