Xeon hat geschrieben: ↑Mo Apr 08, 2019 2:00 pm
Hallo zusammen,
ich lerne Programmieren mit dem Buch: C von A bis Z von Jürgen Wolf. Beim Kapitel 22 geht es um Binäre Bäume, dort werden Rekursionen behandelt. Leider verstehe ich das Thema Rekursionen nicht ganz. Kennt jemand eine Quelle wo es ausführlich erklärt wird?
Die etwas gemeine Erklärung ist hier:
https://www.proggen.org/doku.php?id=glossary:recursion
Etwas ausführlicher findet man das ganze hier:
https://www.proggen.org/doku.php?id=c:t ... :recursion
https://www.proggen.org/doku.php?id=algo:recursion
Hier ist der Code den ich nicht verstehe:
Code: Alles auswählen
else //Was geschieht hier?
{
hlinks = hoehe(zeiger->links);
hrechts = hoehe(zeiger->rechts);
if(hlinks > hrechts)
{
return hlinks+1;
}
else
{
return hrechts+1;
}
}
}
Du stehst irgendwo am Baum und fragst ob links oder rechts ein Knoten ist. Wenn nicht: 0. Falls doch, fragt dieser Knoten wieder, ob da links und rechts etwas ist. Das unterste Blatt gibt 0 zurück. Jeder darüber liegende Knoten, der gefragt, addiert 1 auf diesen Wert. Also 30, 42 und 50 geben 1 zurück: da ist nichts (0) mehr drunter und da wird 1 aufaddiert. 45 bekommt also links und rechts 1 zurück, keins ist größer, also nimmt es die 1 und addiert 1 drauf. 45 gibt also 2 zurück. 40 erhält von 30 1 zurück und von 45 die 2. 2 ist größer als 1, also nimmt 40 die 2 von der 40 und addiert 1 drauf. Die 3 gibt es dann an die 10 zurück. Die 10 erhält rechts nun die 3 und links die 0. 3 ist größer als 0, also addiert es 1 auf die 3 und gibt 4 zurück.
Der Baum hat eine Höhe von vier Ebenen: 10, 40, 45, 50 oder 10, 40, 45, 42. Nach maximal vier Schritten ist man an einem Blatt.
Du läufst so jeden möglichen Weg im Baum nach unten und fängst immer bei einem Blatt an zu zählen, wie lange Du wieder hochlaufen musst. Den längeren Weg gibst Du weiter.
Du fragst erst den obersten Knoten und der fragt genauso seine Unterknoten. Das wiederholt sich solange, bis die Abbruchbedinungen erreicht, der sogenannte Rekursionsanker:
Hier wird jetzt kein Kind mehr gefragt und die Sache abgebrochen.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.