レベル順走査

Coddyの「AVL Tree - データ構造シリーズ #10」コースのレッスン 15/16。

レベル順巡回（幅優先とも呼ばれます）は、通りがかり順（in-order）や行きがけ順（pre-order）のように深さ優先で探索するのではなく、まずルート、次にその両方の子、さらにその4つの孫というように、木を階層ごとに巡回します。

これを行う標準的な方法はキューを使用することです。まずルートをキューに入れ、次に先頭のノードを繰り返し取り出してその値を記録し、その子（右よりも左を先に）をキューの最後尾に追加します。

チャレンジ

簡単

ツリー内のすべての値を、レベルごとに、各レベル内では左から右の順で格納したリストを返す関数 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;
}