K-tes kleinstes Element

Lektion 12 von 16 im Kurs AVL-Baum - Datenstrukturen-Serie #10 von Coddy.

Die nächsten Herausforderungen verwenden die fertige AVLTree-Klasse, die Sie gerade erstellt haben und die Ihnen als gesperrte Datei zur Verfügung gestellt wird. Jede Herausforderung enthält eine neue solution-Datei, in der Sie eine Funktion schreiben, die den Baum VERWENDET.

Eine In-Order-Traversierung eines beliebigen binären Suchbaums (Rotationen ändern dies nicht) besucht die Werte in sortierter Reihenfolge. Der k-te kleinste Wert ist also einfach das Element am Index k - 1 dieser Traversierung.

Aufgabe

Einfach

Schreiben Sie eine Funktion kthSmallest(tree, k), die den k-t kleinsten Wert im Baum zurückgibt (1-basiert). Sie können davon ausgehen, dass k gültig ist.

Probier es selbst

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