트리(Tree)의 순회 (전위/중위/후위 순회)

트리의 순회

 

트리의 순회는 중위(inorder) 순회, 전위(preorder) 순회, 후위 순회(postorder) 순회가 있다. 

※ 여기서 설명할 때 L은 Left, V는 Visit, R은 Right를 의미한다. 즉, 왼쪽 서브 트리, 노드 방문, 오른쪽 서브 트리를 의미한다. 

 

 

 

중위 순회(inorder traversal)

 

중위 순회는 LVR 탐색이 이루어진다. 즉, 왼쪽 서브 트리-루트 노드-오른쪽 서브 트리 탐색이 재귀적으로 이루어진다.

 

 

 

가장 먼저 루트 노드를 기준으로 왼쪽 서브 트리로의 탐색이 시작된다. 즉, 왼쪽 서브 트리에서 또다시 중위 순회가 재귀적으로 이루어진다. 

 

 

 

B노드가 루트 노드인 것처럼 되고, 왼쪽 서브 트리인 A노드로의 중위 탐색이 진행된다. 이후 A노드는 왼쪽 서브 트리(Left)가 없으므로 해당 노드를 방문(Visit) 하게 된다. 

 

출력 : A

 

B가 루트 노드인 것처럼 될 때 , 왼쪽 서브 트리의 탐색을 마쳤으니, 루트 노드인 B의 방문(Visit)이 진행된다.

 

출력 : A B

 

이후 B의 오른쪽 서브 트리로의 중위 탐색이 다시 진행된다. 이때는 D노드가 마치 루트 노드인 것처럼 된다.

 

 

D가 루트 노드일 때, 왼쪽 서브 트리인 C노드로의 중위 탐색이 진행된다. 이후 C노드는 왼쪽 서브 트리(Left)가 없으므로 해당 노드를 방문(Visit) 하게 된다. 

 

출력 : A B C

 

 

이후 루트 노드인 D노드를 방문하게 된다.

 

출력 : A B C D

 

 

D 노드가 루트 노드 일 때 , 오른쪽 서브 트리인 E노드로의 중위 탐색이 진행되고, 왼쪽 서브 트리가 없으므로 바로 E노드를 방문한다.

 

출력 : A B C D E

 

 

F 노드가 루트 노드일 때 왼쪽 서브 트리의 탐색이 모두 완료되었으니, 루트 노드인 F를 방문한다.

 

출력 : A B C D E F

 

 

이후 오른쪽 서브 트리에서 중위 탐색이 진행된다. 이때 G노드가 루트 노드처럼 된다. G노드가 루트노드 일 때, 왼쪽 서브 트리가 없으므로 루트 노드인 G노드를 방문한다.

출력 : A B C D E F G

 

이후 오른쪽 서브 트리로 다시 중위 탐색이 진행된다. 이때 I 노드가 루트 노드인 것처럼 된다.

왼쪽 서브 트리인 H노드로의 중위 탐색이 진행되고 왼쪽 서브 트리가 없으므로 H노드를 방문하게 된다.

출력 : A B C D E F G H

 

이후 루트 노드인 I노드의 방문이 진행되고 오른쪽 서브 트리가 없으므로 탐색이 종료된다.

출력 : A B C D E F G H I

 

 

 

중위 순회(inorder traversal)

 

전위 순회는 VLR 탐색이 이루어진다. 즉, 루트 노드-왼쪽 서브 트리-오른쪽 서브 트리 순으로 탐색이 재귀적으로 진행된다.

 

1. 루트 노드인 F를 방문

2. F의 왼쪽 서브 트리의 루트 노드 B 방문

3. B의 왼쪽 서브 트리의 루트 노드 A 방문

4. B의 오른쪽 서브 트리의 루트 노드 D 방문

5. D의 왼쪽 서브 트리의 루트 노드 C 방문

6. D의 오른쪽 서브 트리의 루트 노드 E 방문

7. F의 오른쪽 서브 트리의 루트 노드 G 방문

8. G의 오른쪽 서브 트리의 루트 노드 I 방문

9. I의 왼쪽 서브 트리의 루트 노드 H 방문

 

출력 : F B A D C E G I H

 

 

 

후위 순회(Postorder Traversal)

 

후위 순회는 LRV 탐색이 이루어진다. 즉 왼쪽 서브 트리-오른쪽 서브 트리-루트 노드 순으로 탐색이 재귀적으로 진행된다.

 

 

 

1. F의 왼쪽 서브트리 탐색

2. B의 왼쪽 서브트리 탐색

3. A노드 방문

4. B의 오른쪽 서브트리 탐색

5. D의 왼쪽 서브트리 탐색

6. C노드 방문

7. D의 오른쪽 서브트리 탐색

8. E노드 방문

9. D노드 방문

10. B노드 방문

11. F의 오른쪽 서브트리 탐색

12. G의 오른쪽 서브트리 탐색

13. I의 왼쪽 서브트리 탐색

14. H노드 방문

15. I노드 방문

16. G노드 방문

17. F노드 방문

 

출력 : A C E D B H I G F