[Data Structure] Level Order

 저번 포스트에 이어 Binary Tree 순회에 대해 이어나가도록 하자. 이번에 다룰 순회방법은 Level Order이다. Level은 이미 이야기했다시피 이진 트리에서 계층을 나타내는 숫자다. 그렇다면 레벨 순회란 무엇일까.

 레벨 순회란 말그대로 레벨 별로 순회를 한다는 의미다. Level 1은 Root 노드를 의미하고 Level 2는 그 다음 계층의 노드들을 의미한다. 이렇게 레벨 별로 노드를 탐색하는데 여기서 제일 왼쪽편에 있는 노드부터 차례대로 탐색하게 된다.

 이 순회는 'Queue'가 사용된다. 노드를 참조할 때 자식 노드가 존재하게 되면 그 노드들을 Queue에 넣는다. 그리고 다시 큐에서 꺼내었을 때 그 노드값을 참조하고 다시 그 노드의 자식들을 큐에 집어넣는다. 이렇게 되면 레벨 Ordering이 된다.

 말보다 코드가 백번 낫다. 코드를 보자.

#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 100

typedef int element;
typedef struct {
    element data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

typedef struct {
    TreeNode queue[MAX_QUEUE_SIZE];
    int front;
    int rear;
} QueueType;

void init(QueueType *q){
    q->front = q->rear = 0;
}

void error(char *message){
    fprintf(stderr,"%s\n",message);
    exit(1);
}

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, TreeNode *item){
    if (is_full(q)) {
        error("q is full");
    }
    q->rear = (q->rear+1) % MAX_QUEUE_SIZE;
    q->queue[q->rear] = *item;
}

TreeNode* dequeue(QueueType *q){
    if (is_empty(q)) {
        error("q is full");
    }
    q->front = (q->front+1) % MAX_QUEUE_SIZE;
    return &q->queue[q->front];
}

TreeNode* peek(QueueType *q){
    if (is_empty(q)) {
        error("q is empty");
    }
    return &q->queue[q->front];
}

void level_order(TreeNode *root){
    QueueType q;
    init(&q);
    TreeNode *tmp;
    enqueue(&q,root);
    while (tmp != NULL) {
        tmp = dequeue(&q);
        printf("%d ",tmp->data);
        
        if(tmp->left != NULL) enqueue(&q, (TreeNode*) tmp->left);
        if(tmp->right != NULL) enqueue(&q, (TreeNode*) tmp->right);
    }
}

int main(){
    TreeNode n1 = {1, NULL, NULL};
    TreeNode n2 = {4, (struct TreeNode*)&n1, NULL};
    TreeNode n3 = {16, NULL, NULL};
    TreeNode n4 = {25, NULL, NULL};
    TreeNode n5 = {20, (struct TreeNode*)&n3, (struct TreeNode*)&n4};
    TreeNode n6 = {15, (struct TreeNode*)&n2, (struct TreeNode*)&n5};
    TreeNode *root = &n6;
    level_order(root);
    
    return 0;
}

별로 어려운건 없다