Tree Traversal4 - Level order Traversal (Breadth-First Traversal)

모든 노드를 낮은 레벨부터 차례대로 순회한다.

레벨 순서 순회는 너비 우선 순회(breadth-first traversal)라고도 한다.

1. 큐에 Root 노드를 put 한다.

2. 큐가 비어있지 않으면,

    2.1 큐에서 get() 하여, t 노드를 방문한다.

    2.2 t 노드의 왼쪽 자식이 있으면, 그것을 큐에 put 한다.

    2.3 t 노드의 오른쪽 자식이 있으면, 그것을 큐에 put 한다.

#include <stdio.h>
#include <malloc.h>

#define MAX 7

int tree[MAX];
int queue[MAX];

int front, rear;

int put(int data) {
    if (rear < MAX) {
        queue[rear++] = data;
        return data;
    }
    printf("Queue overflow\n");
    return -1;
}

int get() {
    if (front < MAX) {
        if (front < rear) {
            return queue[front++];
        }
        printf("There is no data in Queue\n");
    }
    else {
        printf("Queue overflow\n");
    }
    return -1;
}

void initTree() {
    for (int i = 0; i < MAX; ++i) {
        tree[i] = i + 'A';
    }
}

void visit(int idx) {
    printf("node %c \n", tree[idx]);
}

void levelorder_traversal(int idx) {
   
    put(idx);

    while (front != rear) {
        int t = get();
        visit(t);

        int left = t * 2 + 1;
        int right = t * 2 + 2;

        if (left < MAX) {
            put(left);
        }

        if (right < MAX) {
            put(right);
        }
    }
}
   
int main()
{
    //init Queue
    front = rear = 0;

    initTree();
    levelorder_traversal(0);

    return 0;
}

* Output

A → B → C → D → E → F → G