트리
계층적인 자료를 표현하는데 적합한 자료구조
구성요소들은 노드(node)라고 표현
맨 위는 루트 바로 아래는 서브트리 라고 한다.
맨 위 루트는 부모로드라고도 하고 아래는 형제노드 또 아래는 자손노드라고 한다.
레벨은 위에서부터 아래로 1,2,3...이라고 한다. 층이라고 생각하자
차수는 자식 노드의 개수이다.
전체 트리의 차수는 가장 큰 차수의 기준으로 간다.
이진트리
모든 노드는 차수가 2 이하이다. 즉 자식 노드의 개수가 2 이하이다. 반면 일반 트리는 자식 노드의 개수에 제한이 없다.
높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지며 최대 2h승-1개의 노드를 가진다. 그 이유는 한 레벨에는 적어도 하나의 노드는 존재해야 하므로 높이가 h인 이진트리는 적어도 h개의 노드를 가진다.
이진트리의 분류
포화 이진 트리(full binary tree)
완전 이진 트리(complete binary tree)
기타 이진 트리
이진트리의 표현
노드 i의 부모 노드 인덱스 = i/2
노드 i의 왼쪽 자식 노드 인덱스 = 2i
노드 i의 오른쪽 자식 노드 인덱스 = 2i+1
링크법으로 생성된 이진트리
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
} TreeNode;
// n1
// / |
// n2 n3
int main(void)
{
TreeNode *n1, *n2, *n3;
n1 = (TreeNode *)malloc(sizeof(TreeNode));
n2 = (TreeNode *)malloc(sizeof(TreeNode));
n3 = (TreeNode *)malloc(sizeof(TreeNode));
n1->data = 10; // 첫 번째 노드를 설정한다.
n1->left = n2;
n1->right = n3;
n2->data = 20; // 두 번째 노드를 설정한다.
n2->left = NULL;
n2->right = NULL;
n3->data = 30; // 세 번째 노드를 설정한다.
n3->left = NULL;
n3->right = NULL;
free(n1); free(n2); free(n3);
return 0;
}
이진트리의 순회
전위순회(preorder traversal) : VLR
중위순회(inorder traversal) : LVR
후위순회(postorder traversal) : LRV
전이순회
루트노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리
중위순회
왼쪽 서브트리 -> 루트노드 -> 오른쪽 서브트리
후위순회
왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트노드
링크법으로 생성된 이진트리
#include <stdio.h>
#include <stdlib.h>
#include <memory.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 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;
}
반복적인 중위 순회
#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;
}
레벨 순회
각 노드를 레벨 순으로 검사하는 순위 방법
#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;
}
트리의 응용: 수식 트리 처리
아래층일수록 우선순위 연산
| 수식 | a + b | a - (b * c) | (a < b) or (c < d) |
| 전위순휘 | + a b | - a * b c | or < a b < c d |
| 중위순휘 | a + b | a - (b * c) | (a < b) or (c < d) |
| 후위순휘 | a b + | a b c * - | a b < c d < or |
알고리즘 설명
1. 만약 수식 트리가 공백상태이면
2. 그냥 복귀한다.
3. 그렇지 않으면 왼쪽 서브 트리를 계산하기 위하여 evaluate를 다시 순환호출한다. 이때 매개변수는 왼쪽 자식 노드가 된다.
4. 똑같은 식으로 오른쪽 서브 트리를 계산한다.
5. 루트 노드의 데이터 필드에서 연산자를 추출한다.
6. 추출된 연산자를 가지고 연산을 수행해서 반환한다.
수식 트리 계산 프로그램
#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;
}
내용이 많아 이번 장은 2부작으로 진행하겠습니다.
관심이 있으신 분들에게 유용한 정보였길 바라며
다음은 8장 2부로 돌아오겠습니다.