6 Teilaufgaben · 1 Skelett
Box. Stopp. Kinder.
11 / 17
Deine Mission
Du löst drei Baumfunktionen und entlarvst drei kaputte Einfügefunktionen. Du musst nicht „C++ können“: Bei jeder Box fragst du dieselben drei Dinge.
- Stopp? Bin ich hinter einem Blatt?
- Arbeit? Was mache ich mit dieser Box?
- Kinder? Einen Pfad oder beide Teilbäume?
Dein einziger Startzug: Der rekursive Avatar landet rechts von 7 auf nullptr. Was muss passieren?
Alle ungeraden Werte erhöhen
n->val heißt „Zahl in der aktuellen Box“. Klicke top-down alle Boxen, die baum_inc_odd1 verändern muss.
Verändert:
Ungerade erkennst du an
val % 2 == 1. Aber die Prüfung am aktuellen Knoten ersetzt nicht die Besuche seiner Kinder.Hier werden 7, 3, 5 und 13 erhöht. Das Rekursionsskelett braucht nach dem Basisfall Aufrufe für
left und right.Genau einen Paritätspfad laufen
Regel: ungerade → links, gerade → rechts. Klicke die besuchten Boxen in Reihenfolge. Der Start ist oben.
Pfad: · Länge:
Die Zahl entscheidet nur die Richtung. Sie wird trotzdem zur Pfadlänge gezählt.
7 ist ungerade: links zu 4. 4 ist gerade: rechts zu 5. 5 ist ungerade: links ist leer. Ergebnis: Länge 3.Zur gleichen Höhe vervollständigen
Zielhöhe ist 3. Ergänze fehlende Boxen von oben nach unten mit Wert 0. Klicke jede gestrichelte Position, die benötigt wird.
9
4
6
„Vollständig“ ist hier laut Musterlösung: Bis zur vorhandenen Höhe hat jeder innere Knoten zwei Kinder. Die Höhe darf nicht wachsen.
Es fehlen vier Nullen: links-links, rechts sowie dessen zwei Kinder. Bei
height <= 1 stoppst du, bevor neue Kinder entstehen.Drei kaputte Einfügefunktionen
Ordne jedem Code die Situation und den Defekt zu. *& ist eine Referenz auf den echten Zeiger; ein normaler *-Zeiger in n ist nur eine lokale Kopie.
bad1 ·
bad2 · baum_node* n
bad3 · {nullptr,val,b->root}
Frage bei jeder Zuweisung: Ändert sie den echten Baum, nur die lokale Variable oder erzeugt sie einen Rückweg?
Zuordnung: bad1 → root verloren; bad2 → keine Einfügung; bad3 → Zyklus bei nichtleerem Baum.
Prüfungsabschluss
Formuliere das gemeinsame Skelett in einem Satz. Nenne ausdrücklich Basisfall und ob ein Pfad oder beide Teilbäume verfolgt werden.
Erst nach einem eigenen Abschlussversuch verfügbar.
Quellennaher vollständiger Musterweg
void baum_inc_odd1(baum_node* n) {
if (n == nullptr) return;
baum_inc_odd1(n->left);
baum_inc_odd1(n->right);
if (n->val % 2 == 1) n->val += 1;
}
void baum_inc_odd1(baum* b) {
baum_inc_odd1(b->root);
}
int baum_len_odd_even(baum* b) {
baum_node* n = b->root;
int res = 0;
while (n != nullptr) {
res += 1;
if (n->val % 2 == 1) n = n->left;
else n = n->right;
}
return res;
}
void baum_complete(baum_node* n, size_t height) {
if (height <= 1) return;
if (n->left == nullptr)
n->left = new baum_node{nullptr, 0, nullptr};
if (n->right == nullptr)
n->right = new baum_node{nullptr, 0, nullptr};
baum_complete(n->left, height - 1);
baum_complete(n->right, height - 1);
}
void baum_complete(baum* b) {
baum_complete(b->root, baum_height(b));
}Warum die drei Versuche scheitern
- bad1:
nreferenziert zuerstb->root.n = n->leftverändert dadurch den echten Zeiger und zerstört beim Abstieg den Baum; am Ende bleibt nur der neue Knoten als Wurzel. - bad2: Der Abstieg verändert nur die lokale Zeigervariable. Die spätere Zuweisung hängt keinen Knoten in den Baum.
- bad3: Beim nichtleeren Baum zeigt
last->leftauf einen neuen Knoten, dessen rechter Zeiger zurück zur Wurzel zeigt. Der Zyklus lässtbaum_heightnicht terminieren (bis Stackoverflow).