K-ième plus petit élément

Leçon 12 sur 16 du cours Arbre AVL - Série Structures de données n°10 de Coddy.

Les prochains défis utilisent la classe AVLTree que vous venez de construire, fournie sous forme de fichier verrouillé. Chaque défi propose un nouveau fichier solution dans lequel vous écrivez une fonction qui UTILISE l'arbre.

Un parcours infixe (in-order) de n'importe quel arbre binaire de recherche (les rotations ne changent pas cela) visite les valeurs dans l'ordre trié. Ainsi, la k-ième plus petite valeur est simplement l'élément à l'index k - 1 de ce parcours.

Défi

Facile

Écrivez une fonction kthSmallest(tree, k) qui retourne la k-ième plus petite valeur dans l'arbre (indexée à partir de 1). Vous pouvez supposer que k est valide.

Essayez vous-même

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