레벨 순회

Coddy의 AVL 트리 - 자료구조 시리즈 #10 코스 레슨 — 16개 중 15번째.

레벨 순서 순회(너비 우선 순회라고도 함)는 중위 순회나 전위 순회처럼 깊이 우선으로 탐색하는 대신, 루트를 먼저 방문하고 그 다음 두 자식, 그 다음 네 손자 노드 순으로 트리를 층별로 방문합니다.

이를 수행하는 표준적인 방법은 큐(queue)를 사용하는 것입니다. 루트를 큐에 넣는 것으로 시작하여, 반복적으로 맨 앞의 노드를 꺼내 그 값을 기록하고, 해당 노드의 자식 노드들(오른쪽보다 왼쪽을 먼저)을 큐의 뒤쪽에 추가합니다.

챌린지

쉬움

트리의 모든 값을 레벨별로, 각 레벨 내에서는 왼쪽에서 오른쪽 순서로 담은 리스트를 반환하는 함수 levelOrder(tree)를 작성하세요.

직접 해보기

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "avltree.h"
#include "solution.h"

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line1[4096];
    fgets(line1, sizeof(line1), stdin);
    char* tok = strtok(line1, " \n");
    while (tok != NULL) {
        AVLTree_insert(tree, atoi(tok));
        tok = strtok(NULL, " \n");
    }
        int result[1024];
    int resultCount = levelOrder(tree, result);
    for (int i = 0; i < resultCount; i++) {
        if (i > 0) printf(" ");
        printf("%d", result[i]);
    }
    printf("\n");
    return 0;
}