트리 순회란 무엇인가?
트리 순회(Tree Traversal)는 그래프 순회의 한 형태로, 트리에 속한 모든 노드를 정확히 한 번씩 방문하면서 확인하거나 출력하는 과정을 의미합니다. 그중에서도 이진 탐색 트리(Binary Search Tree)의 중위 순회(Inorder Traversal)는 (왼쪽 → 루트 → 오른쪽) 순서로 각 노드를 방문하는 방식입니다.
중위 순회의 대표적인 예시를 살펴보겠습니다. 다음과 같은 이진 트리가 주어졌다고 가정해 보겠습니다.
이 트리를 중위 순회하면 다음과 같은 결과가 나옵니다.
1 4 5 6 8
중위 재귀 순회 C++ 프로그램
아래는 이진 탐색 트리를 재귀 방식으로 중위 순회하는 전체 C++ 프로그램입니다.
예제 코드
#include<iostream>
using namespace std;
struct node {
int data;
struct node *left;
struct node *right;
};
struct node *createNode(int val) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
temp->left = temp->right = NULL;
return temp;
}
void inorder(struct node *root) {
if (root != NULL) {
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}
struct node* insertNode(struct node* node, int val) {
if (node == NULL) return createNode(val);
if (val < node->data)
node->left = insertNode(node->left, val);
else if (val > node->data)
node->right = insertNode(node->right, val);
return node;
}
int main() {
struct node *root = NULL;
root = insertNode(root, 4);
insertNode(root, 5);
insertNode(root, 2);
insertNode(root, 9);
insertNode(root, 1);
insertNode(root, 3);
cout<<"In-Order traversal of the Binary Search Tree is: ";
inorder(root);
return 0;
}실행 결과
In-Order traversal of the Binary Search Tree is: 1 2 3 4 5 9
코드 상세 설명
1. node 구조체 정의
위 프로그램에서 구조체 node는 트리의 노드를 생성하는 역할을 합니다. 이 구조체는 자기 자신(struct node) 타입의 포인터를 멤버로 포함하고 있으므로 자기 참조 구조체(self-referential structure)라고 부릅니다.
struct node {
int data;
struct node *left;
struct node *right;
};2. createNode() 함수
createNode() 함수는 새로운 노드 temp를 생성하고 malloc을 사용해 메모리를 할당합니다. 매개변수로 전달받은 값 val은 temp의 data 멤버에 저장되며, left와 right 포인터에는 NULL이 저장됩니다.
struct node *createNode(int val) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
temp->left = temp->right = NULL;
return temp;
}3. inorder() 함수
inorder() 함수는 이진 트리의 루트 노드를 인자로 받아 트리의 모든 요소를 중위 순서대로 출력하는 재귀 함수입니다. 먼저 왼쪽 서브트리를 순회한 뒤 현재 노드의 데이터를 출력하고, 마지막으로 오른쪽 서브트리를 순회합니다.
void inorder(struct node *root) {
if (root != NULL) {
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}4. insertNode() 함수
insertNode() 함수는 주어진 값을 이진 탐색 트리의 올바른 위치에 삽입하는 역할을 합니다. 노드가 NULL이면 createNode()를 호출해 새 노드를 생성하고, 그렇지 않으면 값을 비교하여 트리 내에서 적절한 위치를 찾아 삽입합니다.
struct node* insertNode(struct node* node, int val) {
if (node == NULL) return createNode(val);
if (val < node->data)
node->left = insertNode(node->left, val);
else if (val > node->data)
node->right = insertNode(node->right, val);
return node;
}5. main() 함수
main() 함수에서는 먼저 루트 노드를 NULL로 초기화한 뒤, 필요한 값들을 가진 노드들을 이진 탐색 트리에 차례로 삽입합니다.
struct node *root = NULL; root = insertNode(root, 4); insertNode(root, 5); insertNode(root, 2); insertNode(root, 9); insertNode(root, 1); insertNode(root, 3);
마지막으로 inorder() 함수를 루트 노드와 함께 호출하면 트리의 모든 값이 중위 순서대로 화면에 출력됩니다.
cout<<"In-Order traversal of the Binary Search Tree is: "; inorder(root);