היורש של ערך
שיעור 16 מתוך 16 בקורס עץ AVL – סדרת מבני נתונים מס' 10 של Coddy.
היורש לפי סדר־מעבר של ערך הוא הערך הקטן ביותר בעץ שגדול ממנו ממש, הערך שהיה מופיע מיד אחריו ברשימה ממוינת. אם הערך הוא הגדול ביותר בעץ, אין לו יורש.
אפשר למצוא אותו במעבר יחיד בלי למיין דבר: יורדים מהשורש, ובכל פעם שממשיכים ימינה מעבר לערך קטן מדי, זוכרים את הצומת האחרון שממנו פניתם שמאלה בתור המועמד הטוב ביותר עד כה.
אתגר
קלכתבו פונקציה successor(tree, value) שמחזירה את הערך הקטן ביותר בעץ שגדול ממש מ־value, או -1 אם אין ערך כזה.
נסו בעצמכם
#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");
}
char line2[256];
fgets(line2, sizeof(line2), stdin);
int p0 = atoi(strtok(line2, " \n"));
int result = successor(tree, p0);
printf("%d\n", result);
return 0;
}
כל השיעורים ביחידה עץ AVL – סדרת מבני נתונים מס' 10
תרגלו בעצמכם: קומפיילר C אונליין