트리 순회(전위, 중위, 후위)
1. 이진 트리 순회
트리 순회에는 전위 순회(preoder), 중위 순회(inorder), 후위 순회(postorder)가 있다.
- 전위 순회는 [루트 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회한다.
- 중위 순회는 [왼쪽 자식 - 루트 - 오른쪽 자식] 순으로 순회한다.
- 후위 순회는 [왼쪽 자식 - 오른쪽 자식 - 루트] 순으로 순회한다.
2. 전위 순회
일단 전위 순회이다. 루트 - 왼쪽 - 오른쪽 순으로 순회한다면 결과는 위 그림과 같다.
모든 노드에 왼쪽 자식과 오른쪽 자식을 임의로 그려놓고 탐색한다면 위 그림의 결과는 “C-B-A-1-2-3-E-D-4-5-F-6-G-7-8”이 된다,
3. 중위 순회
그 다음은 중위 순회 이다. 왼쪽 - 루트 - 오른쪽 순으로 순회한다면 결과는 위와 같다.
마찬가지로 모든 노드에 왼쪽 자식과 오른쪽 자식이 있다고 생각하고 중위 순회를 한다면
“1-A-2-B-3-C-4-D-5-E-6-F-7-G-8” 이 된다.
4. 후위 순회
그 다음은 후위 순회이다. 왼쪽 - 오른쪽 - 루트 순으로 순회한다면 결과는 위와 같다.
이 또한 모든 노드에 왼쪽 자식과 오른쪽 자식이 있다고 생각하고 후위 순회를 한다면
“1-2-A-3-B-4-5-D-6-7-8-G-F-E-C”가 된다.