Niedrigster gemeinsamer Vorfahre

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

Der niedrigste gemeinsame Vorfahre (lowest common ancestor) zweier Werte ist der tiefste Knoten, der beide Werte irgendwo in seinem Teilbaum hat. In einem binären Suchbaum können Sie ihn finden, ohne jemals Teilbäume direkt zu vergleichen: Ausgehend von der Wurzel gilt: Wenn beide Werte kleiner als der aktuelle Knoten sind, liegt die Antwort irgendwo im linken Teilbaum; wenn beide größer sind, liegt sie im rechten Teilbaum.

In dem Moment, in dem die beiden Werte auf verschiedene Seiten fallen (oder einer von ihnen dem aktuellen Knoten entspricht), haben Sie den Verzweigungspunkt gefunden: Dieser Knoten ist der niedrigste gemeinsame Vorfahre.

Aufgabe

Einfach

Schreiben Sie eine Funktion lca(tree, p, q), die den Wert des niedrigsten gemeinsamen Vorfahren (Lowest Common Ancestor) von p und q zurückgibt. Sie können davon ausgehen, dass beide Werte im Baum existieren.

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 p1 = atoi(strtok(NULL, " \n"));
    int result = lca(tree, p0, p1);
    printf("%d\n", result);
    return 0;
}