9. 트리 순회는 처리하는 시점이 다르다
해설글
작성 · 2분 읽기 · 조회수 —수정
기초 개념과 예제를 보강하고 시리즈 흐름을 연결
갈라지는 구조의 모든 노드를 방문하는 문제
회사 조직도나 폴더 구조처럼 한 시작점에서 아래로 갈라지는 관계를 트리로 표현할 수 있다. 트리의 저장 단위는 노드, 가장 위의 시작 노드는 root, 어떤 노드 아래에 직접 연결된 노드는 자식이다. root를 제외한 각 노드는 부모가 하나이고, 연결을 아래로 따라가다가 같은 노드로 돌아오는 순환은 없다. 한 노드와 그 아래의 모든 후손을 묶은 작은 트리를 subtree라고 한다.
이진트리는 노드마다 왼쪽과 오른쪽 자식을 최대 하나씩 갖는다. 입력으로 이미 만들어진 이진트리의 모든 값을 한 번씩 출력하되, 어떤 문제는 부모를 먼저, 어떤 문제는 자식을 먼저 처리해야 한다. 노드를 빠짐없이 방문하는 절차가 순회다.
전위·중위·후위 순회는 왼쪽 subtree와 오른쪽 subtree를 방문하는 순서는 같고, 현재 root를 언제 처리하는지만 다르다. 작은 트리에서 출력 순서를 직접 적으면 세 이름을 따로 외울 필요가 없다.
세 순서를 하나의 코드로 보기
트리 순회 노트에는 전위, 중위, 후위 순서가 나란히 적혀 있다.
preorder : root → left → right
inorder : left → root → right
postorder : left → right → root
세 함수를 따로 외우기보다 같은 재귀 코드에서 root 처리 줄만 옮겨 보면 차이가 작아진다.
void traverse(Node *root) {
if (root == NULL) return;
/* preorder: 여기서 처리 */
traverse(root->left);
/* inorder: 여기서 처리 */
traverse(root->right);
/* postorder: 여기서 처리 */
}
저장소 구현도 정확히 이 세 위치에 printf를 둔다. findid는 현재 노드를 보고 왼쪽에서 찾은 결과가 있으면 즉시 반환한 뒤 오른쪽으로 간다. 전위 순회와 같은 탐색 순서다.
작은 트리에서 처리 시점 표시하기
다음 트리를 사용했다.
1
/ \
2 3
/ \
4 5
이번에 만든 순회 검증 코드의 출력은 다음과 같다.
pre 12453
in 42513
post 45231
sum 15
전위 순회는 자식으로 내려가기 전에 1을 처리하므로 root가 처음이다. 중위 순회는 왼쪽 subtree를 마친 뒤 1을 처리한다. 후위 순회는 양쪽 자식을 모두 마친 뒤 1을 처리하므로 root가 마지막이다.
노트가 후위 순회를 다음처럼 정리한 이유도 여기서 보인다.
한 노드를 처리하려면 그 자식 전체가 정리된 뒤여야 한다
subtree 합은 왼쪽 합과 오른쪽 합을 먼저 구해야 현재 노드 값을 더할 수 있다.
return sum(root->left) + sum(root->right) + root->data;
subtree 합 코드는 후위 처리의 또 다른 형태다. 동적으로 만든 트리를 해제할 때도 자식을 먼저 free한 뒤 root를 free해야 하므로 후위 순회가 맞는다.
중위 순회가 정렬인 조건
이진트리 구현 노트에는 “이진트리의 정렬은? 그건 알고리즘에서!”라는 질문이 있다. 모든 이진트리의 중위 순회가 정렬 결과를 만드는 것은 아니다. 각 노드에서 왼쪽 값은 더 작고 오른쪽 값은 더 크다는 이진 탐색 트리의 규칙이 있을 때만 중위 순서가 오름차순이다.
위 예제는 값 4와 5가 노드 2의 자식이므로 BST가 아니다. 실제 중위 결과 4,2,5,1,3도 정렬되어 있지 않다. 순회 순서와 트리가 만족하는 값의 규칙을 구분해야 한다.
재귀 깊이는 트리 높이 h만큼 필요하다. 균형 잡힌 트리라면 $O(\log n)$ 깊이지만 한쪽으로 기울면 $O(n)$이 되어 호출 스택이 커진다. 방문 시간은 모양과 관계없이 모든 노드를 한 번씩 처리하므로 $O(n)$이다.
재귀에서 확인한 “돌아온 뒤 남은 문장”을 트리에 적용하면, 그 문장을 왼쪽 호출 전, 두 호출 사이, 오른쪽 호출 뒤 어디에 두는지가 처리 순서를 결정한다.