-
이진트리의 순회
이진트리에 존재하는 모든 노드를 한 번씩 방문하여 데이터를 처리하는 과정을 순회라고 한다. 데이터를 처리하는 순서에 따라 다음과 같이 구분한다.
- 전위 순회 데이터를 처리한 뒤 왼쪽 노드, 오른쪽 노드 순서로 이동한다.
- 중위 순회 왼쪽 노드로 이동한 뒤 데이터 처리를 하고 오른쪽 노드로 이동한다.
- 후위 순회 왼쪽 노드로 이동한 뒤 오른쪽 노드로 이동하고 데이터 처리를 한다.
위와 같이 A를 루트로 하는 트리를 순회할 때 각각의 순회 방법은 다음과 같다.
- 전위 순회 A - B - D - E - C
- 중위 순회 D - B - E - A - C
- 후위 순회 D - E - B - C - A