1. 이진 트리의 순회
순회는 트리의 노드들을 체계적으로 방문하는 것이다.
이진트리를 순회하는 방법은 다음 세가지가 있다.
전위순회(preorder traversal): VLR
중위순회(inorder traversal): LVR
후위순회(postorder traversal): LRV
- 전위순회(preorder traversal)
루트->왼쪽 서브트리->오른쪽 서브트리 순으로 노드를 방문한다.
구조화된 문서출력에 쓰인다.
다음은 전위순회를 코드로 구현한다.
void preorder(TreeNode *root){
if(root != NULL){
printf("[%d] ", root->data); //노드 방문
preorder(root->left); //왼쪽 서브트리 방문
preorder(root->right); //오른쪽 서브트리 방문
}
}- 중위순회(inorder traversal)
왼쪽 서브트리->루트->오른쪽 서브트리 순으로 노드를 방문한다.
수식트리에 쓰인다.
다음은 전위순회를 코드로 구현한다.
void inorder(TreeNode *root){
if(root != NULL){
inorder(root->left); //왼쪽 서브트리 방문
printf("[%d] ", root->data); //노드 방문
inorder(root->right); //오른쪽 서브트리 방문
}
}- 후위순회(postorder traversal)
왼쪽 서브트리->오른쪽 서브트리->루트 순으로 노드를 방문한다.
디렉토리 용량 계산에 쓰인다.
void postorder(TreeNode *root){
if(root != NULL){
postorder(root->left); //왼쪽 서브트리 방문
postorder(root->right); //오른쪽 서브트리 방문
printf("[%d] ", root->data); //노드 방문
}
}전체 프로그램은 다음과 같다. 이 코드는 노드를 전역변수로 정의하여 이진트리가 정적으로 만들어졌다.
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef sturct 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};
//중위 순회
void inorder(TreeNode *root){
if(root != NULL){
inorder(root->left); //왼쪽 서브트리 방문
printf("[%d] ", root->data); //노드 방문
inorder(root->right); //오른쪽 서브트리 방문
}
}
//전위 순회
void preorder(TreeNode *root){
if(root != NULL){
printf("[%d] ", root->data); //노드 방문
preorder(root->left); //왼쪽 서브트리 방문
preorder(root->right); //오른쪽 서브트리 방문
}
}
//후위 순회
void postorder(TreeNode *root){
if(root != NULL){
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;
}- 반복적 순회
스택을 이용하여 반복적으로 트리를 순회한다. 이진 트리의 왼쪽 노드들은 NULL노드에 도달할 때까지 스택에 추가되었다가 NULL노드에 도달하면 스택에서 하나씩 삭제된다. 이 삭제된 노드를 방문한 후에 노드의 오른쪽 노드로 이동한다. 다시 이 노드의 왼쪽 노드들을 NULL노드에 도달할 때까지 스택에 추가한다. 이 과정을 공백스택이 될 때까지 되풀이하면 이진 트리를 중위 순회할 수 있다.
#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};
int main(void)
{
printf("중위 순회=");
inorder_iter(root);
printf("\n");
return 0;
}3. 레벨 순회
각 노드를 레벨 순으로 검사하는 수회 방법이다. 레벨 순회는 스택이 아닌 큐를 사용하는 순회법이다.
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef struct TreeNode{
int data;
struct TreeNode *left, *right;
} TreeNode
// 원형큐 코드 시작
#define MAX_QUEUE_SIZE 100
typedef TreeNode * element;
typedef struct{ //큐 타입
element data[MAX_QUEUE_SIZE];
int front, rear;
} QueueType;
//오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
//공백 상태 검출 함수
void init_queue(QueueType *q)
{
q->front = q->rear = 0;
}
// 공백 상태 검출 함수
int is_empty(QueueType *q)
{
return (q->front == q->rear);
}
// 포화 상태 검출 함수
int is_full(QueueType *q)
{
return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
// 삽입 함수
void enqueue(QueueType *q, element item)
{
if(is_full(q))
error("큐가 포화상태입니다");
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
q->data[q->rear] = item;
}
//삭제 함수
element dequeue(QueueType *q)
{
if(is_empty(q))
error("큐가 공백상태입니다");
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return q->data[q->front];
}
void level_order(TreeNode *ptr)
{
QueueType q;
init_queue(&q); //큐 초기화
if(ptr == NULL) return;
enqueue(&q, ptr);
while(!is_empty(&q)){
ptr = dequeue(&q);
printf(" [%d] ", ptr->data);
if(ptr->left)
enqueue(&q, ptr->left);
if(ptr->right)
enqueue(&q, ptr->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("레벨 순회=");
level_order(root);
printF("\n");
return 0;
}4. 트리의 응용: 수식 트리 처리
수식 트리에서 피연산자 = 단말노드, 연산자 = 비단말 노드이다. 따라서 계산을 할 때 자식노드들을 먼저 방문해야 하므로 '후위 순회'를 이용한다.
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode{
int data;
struct TreeNode *left, *right;
} TreeNode;
// +
// + +
// 1 4 16 25
TreeNode n1 = {1, NULL, NULL};
TreeNode n2 = {4, NULL, NULL};
TreeNode n3 = {'*', n1, n2};
TreeNode n4 = {16, NULL, NULL};
TreeNode n5 = {25, NULL, NULL};
TreeNode n6 = {'+', &n4, &n5};
TreeNode n7 = {'+', &n3, &n6};
TreeNode *exp = &n7;
//수식 계산 함수
int evaluate(TreeNode *root)
{
if(root == NULL)
return 0;
if(root->left == NULL && root->right == NULL)
return root->data;
else{
int op1 = evaluate(root->left);
int op2 = evaluate(root->right);
printf("%d %c %d을 계산합니다.\n", op1, root->data, op2);
switch(root->data){
case '+':
return op1 + op2;
case '-':
return op1 - op2;
case '*':
return op1 * op2;
case '/':
return op1 / op2;
}
}
return 0;
}
int main(void)
{
printf("수식의 값은 %d입니다. \n", evaluate(exp));
return 0;
}5. 트리의 응용: 디렉토리 용량 계산
서브 디렉토리의 용량을 모두 계산한 다음 루트 디렉토리의 용량을 계산해야 하므로 '후위 순회'를 사용한다.
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode{
int data;
struct TreeNode *left, *right;
} TreeNode;
int calc_dir_size(TreeNode *root)
{
int left_size, right_size;
if(root == NULL) return 0;
left_size = calc_dir_size(root->left);
right_size = calc_dir_size(root->right);
return (root->data + left_size + right_size);
}
int main(void)
{
TreeNode n4 = {500, NULL, NULL};
TreeNode n5 = {200, NULL, NULL};
TreeNode n3 = {100, &n4, &n5};
TreeNode n2 = {50, NULL, NULL};
TreeNode n1 = {0, &n2, &n3};
printf("디렉토리의 크기=%d\n", calc_dir_size(&n1));
}5. 이진 트리의 추가 연산
- 노드의 개수
트리를 전체 순회해야 한다. 각각의 서브트리에 대하여 순환 호출한 다음, 반환되는 값에 1을 더하여 반환하면 된다.
int get_node_count(TreeNode *node)
{
int count = 0;
if(node != NULL)
count = 1 + get_node_count(node->left) + get_node_count(node->right);
return count;
}- 단말 노드 개수 구하기
트리안의 노드들을 순회하면서 만약 왼쪽자식과 오른쪽자식이 동이세 0이 되면 단말노드이므로 1을 반환한다. 만약 그렇지 않으면 비단말 노드이므로 각각의 서브트리에 대하여 순환 호출한 다음, 반환되는 값을 서로 더하면 된다.
int get_leaf_count(TreeNode *node)
{
int count = 0;
if(node != NULL){
if(node->left == NULL && node-<right == NULL)
return 1;
else
count = get_leaf_count(node->left) + get_leaf_count(node->right);
}
return count;
}- 높이 구하기
트리의 높이를 구하는 알고리즘이 가장 까다롭다. 먼저 각 서브 트리에 대하여 순환호출을 한다. 반환된 트리의 높이 중 최대값을 구하여 반환해야 한다.
int get_height(TreeNode *node)
{
int height = 0;
if(node != NULL)
height = 1 + max(get_height(node->left), get_height(node->right);
return height;
}6. 스레드 이진 트리
이진트리의 NULL 링크를 이용하여 순환 호출 없이도 트리의 노드들을 순회한다.
NULL 링크에 중위 순회시에 후속 노드인 중위 후속자(해당 노드 다음에 오는 노드)를 저장시켜 놓은 트리가 스레드 이진 트리이다.
스레드 이진 트리의 노드 구조는 다음과 같다.
typedef sturct TreeNode{
int data;
struct TreeNode *left, *right;
int is_thread; //만약 오른쪽 링크가 스레드이면 TRUE
} TreeNode;중위 후속자를 반환하는 함수 find_successor()는 다음과 같다. 만약 p의 is_thread == TRUE이면 오른쪽 자식이 중위 후속자이므로 오른쪽 자식을 반환한다. 그렇지 않으면 후속자가 없다는 뜻이므로 NULL을 반환한다. 그리고 서브 트리의 가장 왼쪽 노드로 가서 왼쪽 자식이 NULL이 될 때까지 왼쪽 링크를 타고 이동한다.
TreeNode * find_successor(TreeNode *p)
{
//q는 p의 오른쪽 포인터
TreeNode * q = p->right;
//만약 오른쪽 포인터가 NULL이거나 스레드이면 오른쪽 포인터를 반환
if(q == NULL || p->is_thread == TRUE)
return q;
//만약 오른쪽 자식이면 다시 가장 왼쪽 노드로 이동
while(q->left != NULL) q = q->left;
return q;
}스레드 이진트리에서 중위 순회를 하는 함수 thread_inorder()는 왼쪽 자식이 NULL이 될 때까지 왼쪽 링크를 타고 이동한다. 후속자가 NULL이 될때까지 루프를 반복한다.
void thread_inorder(TreeNode * t)
{
TreeNode * q;
q = t;
while(q->left) q = q->left; //가장 왼쪽노드로 감
do{
printf("%c -> ", q->data); //데이터를 출력
q = find_successor(q); //후속자 함수 호출
}while (q);
}다음은 전체 프로그램은 다음과 같다.
#include <stdio.h>
#define TRUE 1
#define FALSE 0
typedef struct TreeNode{
int data;
struct TreeNode *left, *right;
int is_thread; // 스레드이면 TRUE
} TreeNode
// G
// C F
// A B D E
TreeNode n1 = {'A', NULL, NULL};
TreeNode n2 = {'B', NULL, NULL};
TreeNode n3 = {'C', &n1, &n2, 0};
TreeNode n4 = {'D', NULL, NULL, 1};
TreeNode n5 = {'E', NULL, NULL, 0};
TreeNode n6 = {'F', &n4, &n5, 0};
TreeNode n7 = {'G', &n3, &n6, 0};
TreeNode * exp = &n7;
TreeNode * find_successor(TreeNode * p)
{
//q는 p의 오른쪽 포인터
TreeNode * q = p->right;
//만약 오른쪽 포인터가 NULL이거나 스레드이면 오른쪽 포인터를 반환
if(q == NULL || p->is_thread == TRUE)
return q;
//만약 오른쪽 자식이면 다시 가장 왼쪽 노드로 이동
while (q->left != NULL) q = q->left;
return q;
}
void thread_inorder(TreeNode * t)
{
TreeNode * q;
q = t;
while(q->left) q = q->left;
do{
printf("%c -> ", q->data); //데이터 출력
q = find_successor(q); //후속자 함수 호출
}while(q); //NULL이 아니면
}
int main(void)
{
//스레드 설정
n1.right = &n3;
n2.right = &n7;
n4.right = &n6;
//중위순회
thread_inorder(exp);
printf("\n");
return 0;
}
피넛버터