Menu
CoddyTech

Duyệt theo thứ tự từng mức

Bài học 15 trên 16 trong khóa học Cây AVL, chuỗi cấu trúc dữ liệu #10 của Coddy.

Phép duyệt theo thứ tự từng tầng (còn gọi là duyệt theo chiều rộng) đi qua cây lần lượt từng hàng: bắt đầu từ nút gốc, rồi đến hai nút con, tiếp theo là cả bốn nút cháu, cứ thế tiếp tục. Cách này không đi sâu xuống trước như phép duyệt trung thứ tự hoặc tiền thứ tự.

Cách làm chuẩn là dùng hàng đợi: bắt đầu bằng cách đưa nút gốc vào hàng đợi, sau đó liên tục lấy nút đầu hàng đợi ra, ghi lại giá trị của nút đó và đưa các nút con của nó (nút trái trước nút phải) vào cuối hàng đợi.

challenge icon

Thử thách

Dễ

Viết một hàm (function) levelOrder(tree) trả về danh sách mọi giá trị trong cây, theo từng tầng, từ trái sang phải trong mỗi tầng.

Tự làm thử

#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;
}

Tất cả bài học trong Cây AVL, chuỗi cấu trúc dữ liệu #10

Tự luyện tập: Trình biên dịch C online