이진 트리를 중위 순회(Inorder Traversal)하면 왼쪽 서브트리를 먼저 방문하고, 그다음 루트 노드, 마지막으로 오른쪽 서브트리를 방문합니다. 이 순서로 탐색하면 키 값이 오름차순으로 출력되는 특징이 있습니다.
일반적으로 중위 순회는 재귀 함수로 간단하게 구현할 수 있지만, 이번 글에서는 스택(Stack) 자료구조를 활용하여 재귀 호출 없이 반복문만으로 중위 순회를 수행하는 C++ 프로그램을 살펴보겠습니다. 재귀를 사용하지 않으면 함수 호출 오버헤드가 줄어들고, 깊이가 매우 큰 트리에서 스택 오버플로우 위험도 낮출 수 있습니다.
알고리즘
시작
구조체 n을 선언한다.
정수형 변수 d를 선언한다.
구조체 n을 가리키는 포인터 l을 선언한다.
구조체 n을 가리키는 포인터 r을 선언한다.
구조체 n의 생성자를 선언한다.
정수 변수 d를 매개변수로 전달받는다.
this->d = d
l = r = NULL
inOrder(struct n *root) 함수를 선언한다.
스택 s를 선언한다.
구조체 n을 가리키는 포인터 current를 선언하고 root로 초기화한다.
while (current != NULL || s.empty() == false)
while (current != NULL)
s.push(current) // 현재 노드를 스택에 저장
current = current->l // 왼쪽 자식으로 이동
current = s.top() // 스택 최상단 노드를 꺼내기 위해 확인
s.pop() // 스택에서 제거
current->d 출력
current = current->r // 오른쪽 자식으로 이동
트리의 각 노드에 값을 삽입한다.
inOrder(root) 함수를 호출하여 트리를 순회한다.
끝.
예제 코드
#include<bits/stdc++.h>
using namespace std;
struct n {
int d;
struct n* l;
struct n* r;
n (int d) {
this->d = d;
l = r = NULL;
}
};
void inOrder(struct n *root) {
stack<n *> s;
n *current = root;
while (current != NULL || s.empty() == false) {
while (current != NULL) {
s.push(current);
current = current->l;
}
current = s.top();
s.pop();
cout << current->d << " ";
current = current->r;
}
}
int main() {
struct n* root = new n(6);
root->l = new n(4);
root->r= new n(7);
root->l->l = new n(8);
root->l->r= new n(5);
root->r->l = new n(9);
root->r->r = new n(10);
inOrder(root);
return 0;
}동작 원리
위 코드의 핵심 로직은 다음과 같습니다.
1. 현재 노드(current)가 NULL이 아닌 동안 계속 왼쪽 자식으로 이동하면서 지나온 노드들을 스택에 push합니다.
2. 더 이상 왼쪽으로 갈 수 없으면 스택에서 노드를 pop하여 그 값을 출력합니다.
3. 출력한 노드의 오른쪽 자식으로 이동한 뒤 같은 과정을 반복합니다.
4. current가 NULL이고 스택이 비어 있으면 모든 노드의 방문이 끝난 것이므로 순회를 종료합니다.
실행 결과
8 4 5 6 9 7 10
출력 결과를 보면 키 값이 오름차순으로 정렬되어 나타나는 것을 확인할 수 있습니다. 이는 중위 순회가 이진 탐색 트리(BST)에서 노드를 정렬된 순서로 방문한다는 성질을 보여주는 좋은 예입니다.