이진 트리의 순회
순회(Traversal)란 어떠한 목적을 위해 트리의 노드들을 체계적으로 방문하는 것입니다. 순회의 방법에는 여러가지가 있으며 목적에 따라 어떤 순회를 선택할 것인지를 결정하게 됩니다.
전위 순회 (preorder traversal) : VLR
전위 순회는 루트 이진 트리->왼쪽 이진 트리->오른쪽 이진 트리 순으로 방문하는 방식입니다.
중위 순회 (inorder traversal) : LVR
중위 순회는 왼쪽 이진 트리->루트 이진 트리->오른쪽 이진 트리 순으로 방문하는 방식입니다.
후위 순회 (postorder traversal) : LRV
후위 순회는 왼쪽 이진 트리->오른쪽 이진 트리->루트 이진 트리 순으로 방문하는 방식입니다.
알고리즘 (inorder, preorder, postorder의 재귀 호출 수는 모두 동일)
#include <stdio.h>
typedef struct TreeNode {
int data;
struct TreeNode* left, * right;
} TreeNode;
/*
15
4 20
1 16 25
*/
TreeNode n1 = { 1, NULL, NULL };
TreeNode n2 = { 4, &n1, NULL };
TreeNode n3 = { 16, NULL, NULL };
TreeNode n4 = { 25, NULL, NULL };
TreeNode n5 = { 20, &n3, &n4 };
TreeNode n6 = { 15, &n2, &n5 };
TreeNode* root = &n6;
// 전위 순회
void preorder(TreeNode* root) {
if (root) {
printf("%d-", root->data);
preorder(root->left);
preorder(root->right);
}
}
// 중위 순회
void inorder(TreeNode* root) {
if (root) {
inorder(root->left);
printf("%d-", root->data);
inorder(root->right);
}
}
// 후위 순회
void postorder(TreeNode* root) {
if (root) {
postorder(root->left);
postorder(root->right);
printf("%d-", root->data);
}
}
// 메인
int main(void)
{
printf("중위 순회 : ");
inorder(root);
printf("\n");
printf("전위 순회 : ");
preorder(root);
printf("\n");
printf("후위 순회 : ");
postorder(root);
printf("\n");
return 0;
}
/*
중위 순회 : 1-4-15-16-20-25-
전위 순회 : 15-4-1-20-16-25-
후위 순회 : 1-4-16-25-20-15-
*/
이진 트리의 반복적 순회 프로그램
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef struct TreeNode {
int data;
struct TreeNode* left, * right;
} TreeNode;
#define SIZE 100
int top = -1;
TreeNode* stack[SIZE];
void push(TreeNode* p) {
if (top < SIZE - 1)
stack[++top] = p;
}
TreeNode* pop() {
TreeNode* p = NULL;
if (top >= 0)
p = stack[top--];
return p;
}
void inorder_iter(TreeNode* root) {
while (1) {
for (; root; root = root->left)
push(root);
root = pop();
if (!root) break;
printf("[%d] ", root->data);
root = root->right;
}
}
/* 15
4 20
1 16 25
*/
TreeNode n1 = { 1, NULL, NULL };
TreeNode n2 = { 4, &n1, NULL };
TreeNode n3 = { 16, NULL, NULL };
TreeNode n4 = { 25, NULL, NULL };
TreeNode n5 = { 20, &n3, &n4 };
TreeNode n6 = { 15, &n2, &n5 };
TreeNode* root = &n6;
// 메인
int main(void) {
printf("반복적 중위 순회 : ");
inorder_iter(root);
printf("\n");
return 0;
}
/*
반복적 중위 순회 : [1] [4] [15] [16] [20] [25]
*/
함수 inorder_iter() 는 반복적 중위 순회를 수행합니다.
15 n6
4 20 n2 n5
1 16 25 n1 n3 n4
트리의 값과 이름이 위와 같을 때 트리의 포인터로 root라는 이름의 변수를 생성하고 n6 트리의 주소를 저장합니다.
함수로 root가 보내지면 반복문 안에서 push함수로 &n6의 값이 들어있는 root를 보내서 스택에 저장합니다. root가 null일 때까지 root를 root의 왼쪽 트리로 이동해가며 반복하므로 n6, n2, n1의 주소를 스택에 저장합니다.
현재 스택의 상태는 n6 - n2 - n1 이고 top의 위치는 n1입니다. pop() 함수를 실행하여 함수 안에서 트리 포인터 p를 생성하고 스택의 top에 위치에 있는 n1의 주소를 저장하고 반환하여 반환값을 root에 저장합니다. 출력 함수에서 root의 data를 출력하고 root의 오른쪽 트리로 이동합니다.
이와 같은 방식으로 전체 트리들을 반복적 중위 순회로 방문할 수 있습니다.
연습문제
함수의 호출이 다음과 같을 때 출력 결과와 반복문 while의 진입 횟수를 쓰시오.
inorder_iter(&n2); // (a)
inorder_iter(&n5); // (b)
15 n6
4 20 n2 n5
1 16 25 n1 n3 n4
더보기
(a) 출력 결과 : [1] [4] / 진입 횟수 : 3
{b} 출력 결괴 : [16] [20] [25] / 진입 횟수 : 4