Menu
Coddy logo textTech

היורש של ערך

שיעור 16 מתוך 16 בקורס עץ AVL – סדרת מבני נתונים מס' 10 של Coddy.

היורש לפי סדר־מעבר של ערך הוא הערך הקטן ביותר בעץ שגדול ממנו ממש, הערך שהיה מופיע מיד אחריו ברשימה ממוינת. אם הערך הוא הגדול ביותר בעץ, אין לו יורש.

אפשר למצוא אותו במעבר יחיד בלי למיין דבר: יורדים מהשורש, ובכל פעם שממשיכים ימינה מעבר לערך קטן מדי, זוכרים את הצומת האחרון שממנו פניתם שמאלה בתור המועמד הטוב ביותר עד כה.

challenge icon

אתגר

קל

כתבו פונקציה 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 אונליין