[자료구조] BT level order traversal 문제 풀이 (Queue 사용)

 

 

 

문제

 

그림과 같은 binary tree에 대하여 level order traversal 결과를 화면에 출력하는 코드를 작성하기.

 

 

---

WHAT IS LEVEL ORDER TRAVERSAL

 

 

이진트리 (binary tree) 순회 방법으로는 전위 / 중위 / 후위 뿐만 아니라, 트리의 레벨 순서대로 순회하는 level order traversal이 있다. 루트 노드 -> 루트 노드의 left child -> 루트 노드의 right child 의 순서이다.

 

위 그림으로 예를 들자면 level order 순회에 따른 순서는 4 3 6 2 5 8 이 될 것이다. 

 

---

 

 

* 우리는 이 level order traversal을 자료구조 큐(Queue)를 이용하여 구현해 볼 것이다.

 

---

 

큐(Queue)를 구현하기 위해 필요한 기본적인 요소 4가지

 

1. 맨 앞 빈자리를 가리키는 변수 front

2. 맨 뒷 요소를 가리키는 변수 rear

3. 큐에 데이터를 삽입하는 함수 (add_q)

4. 큐에 데이터를 삭제하는 함수 (delete_q)      

 

---

 

풀이 결과를 스포해 보자면,

 

1. 루트 노드를 queue에 넣는다.

2. dequeue로 반환해 출력한다.

3. 반환한노드의 자식 노드들을 큐에 차례대로 넣는다.

4. dequeue로 다음 노드 둘 반환해 출력한다.

5. 반환했던 노드의 자식 노드들을 큐에 넣는다.

...

의 반복이 될 것이다.   

 

 

이제 코드와 함께 살펴보자. 

 

 

 

---

 

INTRODUCTION

 

#define MAX_QUEUE_SIZE 100

typedef struct node *treePointer;

int front = 0;
int rear = 0;
treePointer queue[MAX_QUEUE_SIZE];

typedef struct node
{
    int data;
    treePointer leftChild;
    treePointer rightChild;
} node;

 

 

각 노드를 표현할 구조체, queue, front, rear 등을 선언해 주었다.

 

 

 

위에서 봤던 그림 트리는 우선은 아래의 하드 코딩을 통해 제작해두었다.

treePointer create_BT()
{
    treePointer root = create_node(4);
    root->leftChild = create_node(3);
    root->rightChild = create_node(6);
    root->leftChild->leftChild = create_node(2);
    root->leftChild->rightChild = create_node(5);
    root->rightChild->rightChild = create_node(8);

    return root;
}

  

 

---

 

 

QUEUE FUNCTION

 

 

void addq(treePointer a)
{
    rear = (rear + 1) % MAX_QUEUE_SIZE;
    queue[rear] = a;
}

treePointer delete_q(treePointer a)
{
    front = (front + 1) % MAX_QUEUE_SIZE;
    return queue[front];
}

 

 

addq 함수에서는 queue의 맨 뒷자리에 새로운 요소를 추가해준다. 따라서 마지막 요소를 가리키는 rear 변수를 한 칸 뒤로옮겨준 후 해당 자리에 새로운 요소를 삽입한다.   

deleteq 함수에서는, queue의 맨 앞자리 요소를 삭제한다. 변수 front는 원래 맨 앞 요소의 바로 앞 빈 공간을 가리키는 변수이므로, ++ 해 준 후 삭제할 해당 맨 앞 요소를 반환해준다.     

 

 

 

---

 

 

LEVEL ORDER FUNCTION

 

 

void level_order(treePointer root)
{
    addq(root);
    while (root)
    {
        root = delete_q(root);
        if (root)
        {
            printf("%d ", root->data);
        }

        if (root->leftChild)
        {
            addq(root->leftChild);
        }

        if (root->rightChild)
        {
            addq(root->rightChild);
        }
    }
}

 

앞서 잠시 스포했던 풀이 과정과 함수를 대조하며 보길 바란다.

 

1. 루트 노드를 queue에 넣는다.

2. dequeue로 반환해 출력한다.

3. 반환한노드의 자식 노드들을 큐에 차례대로 넣는다.

4. dequeue로 다음 노드 둘 반환해 출력한다.

5. 반환했던 노드의 자식 노드들을 큐에 넣는다.

...

 

 

 

이렇게 우리는 queue의 특성을 활용하여 binary tree를 올바르게 level order traversal 후 출력할 수 있게 되었다. 

 

 

전체 코드를 남기며 포스팅을 마친다.

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

#define MAX_QUEUE_SIZE 100

typedef struct node *treePointer;

int front = 0;
int rear = 0;
treePointer queue[MAX_QUEUE_SIZE];

typedef struct node
{
    int data;
    treePointer leftChild;
    treePointer rightChild;
} node;

treePointer create_node(int data)
{
    treePointer new = (treePointer)malloc(sizeof(node));
    new->data = data;
    new->leftChild = NULL;
    new->rightChild = NULL;
}

treePointer create_BT()
{
    treePointer root = create_node(4);
    root->leftChild = create_node(3);
    root->rightChild = create_node(6);
    root->leftChild->leftChild = create_node(2);
    root->leftChild->rightChild = create_node(5);
    root->rightChild->rightChild = create_node(8);

    return root;
}

void addq(treePointer a)
{
    rear = (rear + 1) % MAX_QUEUE_SIZE;
    queue[rear] = a;
}

treePointer delete_q(treePointer a)
{
    front = (front + 1) % MAX_QUEUE_SIZE;
    return queue[front];
}

void in_order(treePointer root)
{
    if (root)
    {
        in_order(root->leftChild);
        printf("%d ", root->data);
        in_order(root->rightChild);
    }
}

void level_order(treePointer root)
{
    addq(root);
    while (root)
    {
        root = delete_q(root);
        if (root)
        {
            printf("%d ", root->data);
        }

        if (root->leftChild)
        {
            addq(root->leftChild);
        }

        if (root->rightChild)
        {
            addq(root->rightChild);
        }
    }
}

int main()
{
    treePointer root = create_BT();
    create_BT();

    level_order(root);

    return 0;
}