Menu
Coddy logo textTech

האיבר הקטן ביותר במקום ה־K

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

באתגרים הבאים תשתמשו במחלקה המוגמרת AVLTree שבניתם זה עתה, והיא מסופקת לכם כקובץ נעול. עם כל אתגר מגיע קובץ solution חדש, שבו תכתבו פונקציה שמשתמשת בעץ.

מעבר בסדר תוכי של כל עץ חיפוש בינארי (סיבובים לא משנים זאת) מבקר בערכים בסדר ממוין. לכן הערך הקטן ביותר ה־k הוא פשוט האיבר באינדקס k - 1 של המעבר הזה.

challenge icon

אתגר

קל

כתוב פונקציה kthSmallest(tree, k) שמחזירה את הערך ה-k הקטן ביותר בעץ (האינדקס מתחיל ב-1). אפשר להניח ש-k תקין.

נסו בעצמכם

#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 = kthSmallest(tree, p0);
    printf("%d\n", result);
    return 0;
}

כל השיעורים ביחידה עץ AVL – סדרת מבני נתונים מס' 10

תרגלו בעצמכם: קומפיילר C אונליין