Nachfolger eines Wertes

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

Der In-Order-Nachfolger eines Wertes ist der kleinste Wert im Baum, der strikt größer als dieser ist, also der Wert, der in einer sortierten Liste direkt danach käme. Wenn der Wert das Maximum im Baum ist, hat er keinen Nachfolger.

Sie können ihn in einem Durchgang finden, ohne jemals etwas zu sortieren: Gehen Sie von der Wurzel abwärts, und jedes Mal, wenn Sie an einem zu kleinen Wert rechts vorbeigehen, merken Sie sich den letzten Knoten, von dem aus Sie nach links gegangen sind, als Ihren bisher besten Kandidaten.

Aufgabe

Einfach

Schreibe eine Funktion successor(tree, value), die den kleinsten Wert im Baum zurückgibt, der strikt größer ist als value, oder -1, falls keiner existiert.

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