이 글에서는 연결 리스트(Linked List)를 이용해 이진 탐색 트리(Binary Search Tree, BST)를 구현하는 C++ 프로그램을 다룹니다. 노드 삽입부터 전위(preorder), 중위(inorder), 후위(postorder) 순회까지 전체 과정을 알고리즘, 예제 코드, 실행 결과 순으로 살펴보겠습니다.
이진 탐색 트리란?
이진 탐색 트리는 각 노드가 최대 두 개의 자식 노드를 가지며, 다음 규칙을 만족하는 자료구조입니다.
- 왼쪽 서브트리의 모든 값은 부모 노드보다 작다
- 오른쪽 서브트리의 모든 값은 부모 노드보다 크다
이러한 특성 덕분에 탐색, 삽입, 삭제가 평균적으로 O(log n)의 시간 복잡도로 수행됩니다.
주요 함수와 의사 코드(Pseudocode)
프로그램은 크게 네 부분으로 구성됩니다.
- create(): 사용자 입력값을 받아 트리에 노드를 삽입
- inorder(): 중위 순회 (왼쪽 → 루트 → 오른쪽)
- preorder(): 전위 순회 (루트 → 왼쪽 → 오른쪽)
- postorder(): 후위 순회 (왼쪽 → 오른쪽 → 루트)
알고리즘
시작
트리에 삽입할 노드 값을 입력받는다.
데이터 d, 왼쪽 포인터 l, 오른쪽 포인터 r을 갖는 구조체 nod를 정의한다.
create() 함수로 노드를 트리에 삽입한다:
노드 개수를 나타내는 c = 0으로 초기화한다.
c < 6이 참인 동안 반복한다:
루트 노드 값을 입력받는다.
새 노드의 값을 입력받아, 루트보다 크면 오른쪽에,
작으면 왼쪽에 배치한다.
inorder() 함수로 중위 순회를 수행한다:
왼쪽 – 루트 – 오른쪽
preorder() 함수로 전위 순회를 수행한다:
루트 – 왼쪽 – 오른쪽
postorder() 함수로 후위 순회를 수행한다:
왼쪽 – 오른쪽 – 루트
main()에서 각 함수를 호출하고 결과를 출력한다.
끝예제 코드
#include <iostream>
using namespace std;
struct nod {
nod *l, *r;
int d;
}*r = NULL, *p = NULL, *np = NULL, *q;
void create() {
int v,c = 0;
while (c < 6) {
if (r == NULL) {
r = new nod;
cout<<"enter value of root node\n";
cin>>r->d;
r->r = NULL;
r->l = NULL;
} else {
p = r;
cout<<"enter value of node\n";
cin>>v;
while(true) {
if (v< p->d) {
if (p->l == NULL) {
p->l = new nod;
p = p->l;
p->d = v;
p->l = NULL;
p->r = NULL;
cout<<"value entered in left\n";
break;
} else if (p->l != NULL) {
p = p->l;
}
} else if (v >p->d) {
if (p->r == NULL) {
p->r = new nod;
p = p->r;
p->d = v;
p->l = NULL;
p->r = NULL;
cout<<"value entered in right\n";
break;
} else if (p->r != NULL) {
p = p->r;
}
}
}
}
c++;
}
}
void inorder(nod *p) {
if (p != NULL) {
inorder(p->l);
cout<<p->d<<endl;
inorder(p->r);
}
}
void preorder(nod *p) {
if (p != NULL) {
cout<<p->d<<endl;
preorder(p->l);
preorder(p->r);
}
}
void postorder(nod *p) {
if (p != NULL) {
postorder(p->l);
postorder(p->r);
cout<<p->d<<endl;
}
}
int main() {
create();
cout<<" traversal in inorder\n";
inorder(r);
cout<<" traversal in preorder\n";
preorder(r);
cout<<" traversal in postorder\n";
postorder(r);
}코드 동작 방식
create() 함수는 루트가 비어 있으면 첫 번째 입력값으로 루트 노드를 생성합니다. 이후 입력된 값은 루트부터 비교를 시작해, 현재 노드보다 작으면 왼쪽 자식 방향으로, 크면 오른쪽 자식 방향으로 이동하며 빈 자리를 찾을 때까지 내려갑니다. 빈 위치를 발견하면 새 노드를 생성하고 좌우 포인터를 NULL로 초기화한 뒤 반복문을 종료합니다.
순회 함수들은 모두 재귀 호출 방식으로 작성되어 있습니다.
- 중위 순회(inorder): 왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순서로 방문하므로, 결과가 항상 오름차순으로 정렬되어 출력됩니다.
- 전위 순회(preorder): 루트를 먼저 출력하므로 트리를 복제하거나 구조를 파악할 때 유용합니다.
- 후위 순회(postorder): 자식 노드를 먼저 처리하므로 트리 삭제 연산에 활용됩니다.
실행 결과
enter value of root node 7 enter value of node 6 value entered in left enter value of node 4 value entered in left enter value of node 3 value entered in left enter value of node 2 value entered in left enter value of node 1 value entered in left traversal in inorder 1 2 3 4 6 7 traversal in preorder 7 6 4 3 2 1 traversal in postorder 1 2 3 4 6 7
결과 분석
이 실행 예제에서는 7을 루트로 지정한 뒤 6, 4, 3, 2, 1을 차례대로 입력했습니다. 모든 값이 루트보다 작기 때문에 노드들이 계속 왼쪽으로만 연결되어, 트리가 한쪽으로 치우친 편향 트리(skewed tree) 형태가 되었습니다.
- 중위 순회 결과인 1, 2, 3, 4, 6, 7은 오름차순으로 정렬되어 BST의 핵심 성질을 잘 보여줍니다.
- 전위 순회 결과인 7, 6, 4, 3, 2, 1은 루트부터 왼쪽 경로를 따라 내려간 순서와 일치합니다.
- 후위 순회 결과인 1, 2, 3, 4, 6, 7은 가장 깊은 노드부터 역순으로 올라오는 순서입니다.
참고로 편향 트리는 탐색 성능이 O(n)까지 저하될 수 있으므로, 실무에서는 AVL 트리나 레드-블랙 트리 같은 자가 균형(self-balancing) 트리를 함께 고려하는 것이 좋습니다.