מעבר לפי רמות
שיעור 15 מתוך 16 בקורס עץ AVL – סדרת מבני נתונים מס' 10 של Coddy.
מעבר בסדר רמות (נקרא גם מעבר לרוחב) מבקר בעץ שורה אחר שורה: קודם בשורש, אחר כך בשני ילדיו, לאחר מכן בכל ארבעת נכדיו וכן הלאה, במקום לצלול לעומק כמו במעבר בסדר תוכי או בסדר תחילי.
הדרך המקובלת לעשות זאת היא באמצעות תור: מתחילים כשהשורש נמצא בו, ואז שוב ושוב מוציאים את הצומת הקדמי, מתעדים את ערכו ומכניסים את ילדיו (השמאלי לפני הימני) לסוף התור.
אתגר
קלכתבו פונקציה 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;
}
כל השיעורים ביחידה עץ AVL – סדרת מבני נתונים מס' 10
תרגלו בעצמכם: קומפיילר C אונליין