K-esimo elemento più piccolo

Lezione 12 di 16 del corso Albero AVL - Serie sulle strutture dati #10 di Coddy.

Le prossime sfide usano la classe AVLTree completa che hai appena creato, fornita in un file bloccato. Ogni sfida include un nuovo file solution in cui scriverai una funzione che USA l’albero.

Una visita in ordine di qualsiasi albero binario di ricerca (le rotazioni non lo modificano) visita i valori in ordine crescente. Quindi il k-esimo valore più piccolo è semplicemente l’elemento all’indice k - 1 di quella visita.

Sfida

Facile

Scrivi una funzione kthSmallest(tree, k) che restituisca il k° valore più piccolo nell’albero (indicizzato a partire da 1). Puoi assumere che k sia valido.

Provalo tu

#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;
}