[C 자료구조] Tree - Level Order Traversal

0) 제목

• Hackerrank 의 Linked Lists 부분의 Reverse a linked list 문제입니다.

• C언어를 이용하여 풀었습니다.

1) 문제 설명 

• Tree의 Root Node의 Pointer가 Level Order 함수의 파라미터로 주어지고, 

• 주어진 트리의 Level별로 data를 순서대로 출력하는 문제입니다.

2) 풀이 과정 

• BFS(넓이 우선 탐색)라고 생각하여서 Queue를 이용해서 풀었습니다. 

• 또한, 문제에서 주어진 Tree의 Node의 갯수가 최대 500 이어서, 

• 동적할당을 이용한 Linked lists로 Queue를 구현하는 방식으로 풀었습니다.

3) 코드

/*
typedef struct _node
{
    int data;
    struct _node * left;
    struct _node * right;
} node*/
//BFS식. (queue 이용)
 
///////////////////////////////////Queue 구현////////////////////////////////
 
typedef node * Data;
 
typedef struct _qnode{
    Data data;
    struct _qnode *next;
} QNode;
typedef struct _queue{
    QNode * front;
    QNode * rear;
} Queue;
 
void QueueInit(Queue * pq){
    pq->front = NULL;
    pq->rear = NULL;
}
void enqueue(Queue * pq, Data data){
    QNode * newNode = (QNode *)malloc(sizeof(QNode));
    newNode->data = data;
    newNode->next = NULL;
    
    if(pq->front == NULL){
        pq->front = newNode;
        pq->rear = newNode;
    }else{
        pq->rear->next = newNode;
        pq->rear = newNode;
    }
}
Data dequeue(Queue * pq){
    if(pq->front == NULL){
        return NULL;
    }
    QNode * delNode = pq->front;
    Data data = delNode->data;
    pq->front = pq->front->next;
    
    free(delNode);
    return data;
}
 
//////////////////////////////////Level Order 함수////////////////////////////////////
 
void levelOrder(node * root) {
    if(root == NULL) return;
    Data data;
    Queue q;
    QueueInit(&q);
    enqueue(&q, root);
    while(1){
        data = dequeue(&q);
        if(data == NULL) break;
        printf("%d ", data->data);
 
        if(data->left != NULL){
            enqueue(&q, data->left);
        }
        if(data->right != NULL){
            enqueue(&q, data->right);
        }    
    }
}

주석 내부에 있는 부분은 C언어 문법에 맞게 고쳤습니다.

(Hackerrank 에서는 C++ 문법으로 지원)

경로 : Dashboard>Data Structures>Tree>Level Order Traversal

출처 : [HackerRank] https://www.hackerrank.com/challenges/tree-level-order-traversal/problem

많이 부족합니다. 좋은 지적 부탁드립니다.