Penelusuran Berdasarkan Urutan Level
Pelajaran 15 dari 16 dalam kursus Pohon AVL, Seri Struktur Data #10 di Coddy.
Penelusuran level-order (juga disebut breadth-first) mengunjungi pohon baris demi baris: pertama root, lalu kedua anaknya, kemudian keempat cucunya, dan seterusnya, bukan menelusuri sampai ke dalam terlebih dahulu seperti yang dilakukan in-order atau pre-order.
Untuk melakukannya, cara standar adalah menggunakan antrean: mulai dengan root di dalamnya, lalu berulang kali hapus node paling depan, catat nilainya, dan masukkan anak-anaknya (kiri sebelum kanan) ke bagian belakang antrean.
Tantangan
MudahTulis fungsi levelOrder(tree) yang mengembalikan list berisi setiap nilai dalam tree, tingkat demi tingkat, dari kiri ke kanan pada setiap tingkat.
Coba sendiri
#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;
}
Semua pelajaran di Pohon AVL, Seri Struktur Data #10
3Tantangan Latihan
Elemen Terkecil ke-KJumlah RentangLeluhur Bersama TerendahPenelusuran Berdasarkan Urutan LevelPenerus Suatu NilaiLatihan sendiri: Compiler C online