Vier Funktionen · ein Rekursionsgerüst

Suchbaum
unter der Lupe

12 / 17

Mission

Du steuerst den Baum selbst. Finde erst den größten Wert, dann den schwersten Wurzel-Blatt-Pfad und seine Länge. Zum Schluss schneidest du den Baum auf eine Höhe zurück.

Knoten = eine Box. Wurzel = oberste Box. Blatt = Box ohne Kinder. Höhe und Pfadlänge zählen hier Knoten.

struct sb_node {
    sb_node* left;      // linkes Kind
    unsigned int val;  // positiver Wert
    sb_node* right;     // rechtes Kind
};
struct suchbaum { sb_node* root; };

// vorhanden und benutzbar:
void sb_clear(sb_node* n);

Direkte Manipulation

Klicke deinen Weg

Start: Wo liegt im Suchbaum das maximale Element?

Dein Trace: —

Maximum im Suchbaum

Klicke oben im Baum den Weg von der Wurzel zum maximalen Element.

Suchbaum-Regel in Alltagssprache: kleinere Werte links, größere rechts.

Solange ein rechtes Kind existiert, gehst du rechts. Stoppe auf dem letzten Knoten, nicht erst hinter ihm.

Maximale Pfadsumme

Jetzt zählen vollständige Pfade von der Wurzel bis zu einem Blatt. Welcher Ast gewinnt?

Rechne jeden Wurzel-Blatt-Pfad als Summe. Ein innerer Knoten ist noch kein fertiger Pfad.

Die Rekursion fragt links und rechts dieselbe Frage und nimmt dann max(links, rechts).

Länge des schwersten Pfads

Die Hilfsfunktion muss Summe und Länge nach oben tragen. Ergänze den Rückgabewert für einen leeren Teilbaum.

if (n == nullptr) return paar{,};

Ein leerer Teilbaum trägt weder Wert noch Knoten bei.

first speichert die Summe, second die Anzahl der Knoten. Beide neutralen Werte sind 0.

Trim auf Höhe 2

Klicke im Baum alle Knoten an, die entfernt werden müssen, damit nur zwei Ebenen bleiben.

Die Wurzel hat Höhe 1. Ihre Kinder liegen auf Höhe 2 und bleiben.

Bei Resthöhe 1 werden beide Unterbäume mit sb_clear gelöscht und beide Zeiger auf nullptr gesetzt.

Prüfungsabschluss: kompletter Code

Erst nach allen vier Werkstatt-Schritten wird die vollständige Musterlösung freigegeben.

unsigned int sb_maxval(suchbaum* sb) {
    if (sb->root == nullptr) throw runtime_error("Suchbaum ist leer");
    sb_node* n = sb->root;
    while (n->right != nullptr) n = n->right;
    return n->val;
}

unsigned int sb_maxpath(sb_node* n) {
    if (n == nullptr) return 0;
    return n->val + max(sb_maxpath(n->left), sb_maxpath(n->right));
}
unsigned int sb_maxpath(suchbaum* sb) { return sb_maxpath(sb->root); }

struct paar { unsigned int first; int second; };
paar sb_maxpathlen(sb_node* n) {
    if (n == nullptr) return paar{0, 0};
    paar l = sb_maxpathlen(n->left);
    paar r = sb_maxpathlen(n->right);
    if (l.first > r.first) return paar{l.first+n->val, l.second+1};
    return paar{r.first+n->val, r.second+1};
}
unsigned int sb_maxpathlen(suchbaum* sb) {
    return sb_maxpathlen(sb->root).second;
}

void sb_trim(sb_node* n, int height) {
    if (n == nullptr) return;
    if (height == 1) {
        sb_clear(n->right); sb_clear(n->left);
        n->right = nullptr; n->left = nullptr;
        return;
    }
    sb_trim(n->right, height-1);
    sb_trim(n->left, height-1);
}
void sb_trim(suchbaum* sb, int height) {
    if (height <= 0) {
        sb_clear(sb->root); sb->root = nullptr; return;
    }
    sb_trim(sb->root, height);
}

Wie sitzt Aufgabe 12?

Noch nicht markiert.

Mission

Klicke deinen Weg

Maximum im Suchbaum

Maximale Pfadsumme

Länge des schwersten Pfads

Trim auf Höhe 2

Prüfungsabschluss: kompletter Code

Was du mechanisch auf Papier schreibst

Wie sitzt Aufgabe 12?