이번 포스팅은 "트리와 이진 트리"에 대한 전반적인 이해도를 필요로 합니다. 트리와 이진 트리에 대해 잘 알지 못한다면 공부하고 그 후에 이 포스팅을 읽어주세요 여기에서 트리와 이진 트리에 대해서 공부할 수 있습니다.
이진 트리의 순회(Traversal)
이진 트리 또한 데이터를 저장하기 위한 자료구조입니다. 이진 트리를 순회한다는 것은 이진 트리에 있는 모든 노드를 방문하며 노드의 데이터를 목적에 맞게 처리하는 것을 의미합니다. 스택이나 큐, 연결 리스트 같은 선형 자료구조들은 데이터를 순차적으로 순회하는 방법은 하나뿐입니다. 그러나 계층적 구조를 가진 트리의 경우는 여러 가지 순서로 노드가 가진 데이터에 접근할 수 있습니다. 이진 트리를 순회하는 대표적인 방법으로는 "전위 순회", "중위 순회", "후위 순회" 이 3가지의 방법이 있습니다.
- 전위 순회: 루트를 먼저 방문하고, 그 후 왼쪽 서브트리를 방문하고 마지막으로 오른쪽 서브트리를 방문하는 방식으로 이루어집니다.
- 중위 순회: 먼저 왼쪽 서브트리를 방문하고 그 후 루트를 방문하고 마지막으로 오른쪽 서브트리를 방문하는 방식으로 이루어집니다.
- 후위 순회: 먼저 왼쪽 서브트리를 방문하고 그 후 오른쪽 서브트리를 방문하고 마지막으로 루트를 방문하는 방식으로 이루어집니다.
이진 트리 순회 구현
이진 트리의 3가지 순회 방법(전위, 중위, 후위)을 "순환 알고리즘"을 이용하여 C언어로 구현하면 다음과 같습니다.
#include <stdio.h>
#include <stdlib.h>
#include <string.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 != NULL) {
printf("[%d] ", root->data); // 노드 방문
preorder(root->left); // 왼쪽 서브트리 순회
preorder(root->right); // 오른쪽 서브트리 순회
}
}
// 중위 순회
void inorder(TreeNode *root) {
if (root != NULL) {
inorder(root->left); // 왼쪽 서브트리 순회
printf("[%d] ", root->data); // 노드 방문
inorder(root->right); // 오른쪽 서브트리 순회
}
}
// 후위 순회
void postorder(TreeNode *root) {
if (root != NULL) {
postorder(root->left); // 왼쪽 서브트리 순회
postorder(root->right); // 오른쪽 서브트리 순회
printf("[%d] ", root->data); // 노드 방문
}
}
int main() {
printf("전위 순회 = ");
preorder(root);
printf("\n");
printf("중위 순회 = ");
inorder(root);
printf("\n");
printf("후위 순회 = ");
postorder(root);
printf("\n");
return 0;
}이진 트리 레벨 순회 (Level Traversal)
레벨 순회는 각 노드를 레벨 순으로 검사하는 순회 방법입니다. 트리의 레벨은 루트 노드가 1이고 아래로 내려갈수록 증가합니다. 동일한 레벨의 경우 왼쪽 노드를 먼저 방문하고 그 후 오른쪽 노드를 방문합니다.
이진 트리 레벨 순회 구현
이진 트리의 레벨 순회를 C언어로 구현하면 다음과 같습니다.
#include <stdio.h>
#include <stdlib.h>
#include <string.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() {
printf("레벨 순회 =");
level_order(root);
printf("\n");
return 0;
}반응형
