큐를 이용한 트리의 레벨순회

순환을 이용한 트리의 순회방법에는 3가지(전위,중위,후위) 순회 기법이있었습니다.

이런 표준적인 순회방법 외에도 레벨 순회가 많이 사용되는데, 레벨순회는 각 노드를 레벨순으로 검사하는 순회방법입니다.

위에서 부터 아래로 내려가면서 동일한 레벨의 경우 좌에서 우로 방문하며 순회를 진행합니다.

저번에 살펴본 순회기법들은 순환기법, 즉 스택구조를 이용했습니다.(순환호출==간접적인 스택의사용)

이번에 알아볼 레벨순회기법들은 큐를 이용합니다. 이 방식은 나중에 배울 그래프 파트의 BFS탐색과 거의 동일한 기법입니다.

즉 First-in First-out 속성을 이용하여 먼저 들어온 데이터를 먼저 출력하게끔 하기위해 큐를 사용합니다.

먼저, 큐에 있는 노드를 꺼내어 방문하고 그 노드의 자식노드를 큐에 삽입하는 작업을 큐에 더 이상의 노드가 없을 때 까지 반복합니다.

루트노드 큐에 삽입-> 큐가 empty하지 않을 때 까지 꺼내고 출력하고 자식노드를 큐에 삽입하는 연산 반복

결국, while(is_empty(&q)) 함수를 빠져나오게되면 최종적인 레벨순회가 끝나게됩니다.

구현을 위해 원형큐를 사용했고, 큐에 담겨지는 데이터는 트리노드이므로 큐의 데이터 타입을 treeNode*로 지정해야합니다.

결국 큐에 삽입되는 것은 트리노드가 되고 큐에담겨진 트리의 정보를 이용하여 순회를 진행합니다. 

아래의 수식트리를 이용하여 레벨순회를 구현해보았습니다.

코드

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX_QSIZE 10
typedef struct treeNode
{
    char data;
    struct treeNode* left, * right;
}treeNode;
typedef treeNode* element;
typedef struct QType
{
    element queue[MAX_QSIZE];
    int front, rear;
}QType;
treeNode n1 = { 'A',NULL,NULL };
treeNode n2 = { 'B',NULL,NULL };
treeNode n3 = { 'C',NULL,NULL };
treeNode n4 = { 'D',NULL,NULL };
treeNode n5 = { '*',&n1,&n2 };
treeNode n6 = { '/',&n3,&n4 };
treeNode n7 = { '+',&n5,&n6 };
treeNode* root = &n7;
 
 
void init(QType* q)
{
    q->front = 0, q->rear = 0;
}
int is_empty(QType* q)
{
    return q->front == q->rear;
}
int is_full(QType* q)
{
    return (q->rear + 1) % MAX_QSIZE == q->front;
}
void enqueue(QType* q, element item)
{
    if (is_full(q))
    {
        printf("요소가 꽉 찼습니다.\n");
        return;
    }
    q->rear = (q->rear + 1) % MAX_QSIZE;
    q->queue[q->rear] = item;
}
treeNode* dequeue(QType* q)
{
    if (is_empty(q))
    {
        printf("요소가 비었습니다.\n");
        exit(1);
    }
    else
    {
        q->front = (q->front + 1) % MAX_QSIZE;
        return q->queue[q->front];
    }
}
void level_order(treeNode* root)
{
    QType q;
    init(&q);
    if (root == NULL)return;
    enqueue(&q, root);
    while (!is_empty(&q))
    {
        root = dequeue(&q);
        printf("%c ", root->data);
        if (root->left)//왼쪽 자식이 존재하면
            enqueue(&q, root->left);
        if (root->right)//오른쪽 자식이 존재하면
            enqueue(&q, root->right);
    }puts(" ");
}
int main()
{
    level_order(root);
}

결과