Binärer Baum - wie durchlaufen?
-
Bei vielen Knoten im Baum hat die Rekursion speichertechnische Nachteile, das ist klar!
-
Nur bei entarteten Bäumen, sonst geht die Rekursion nicht besonders weltbewegend tief ...
-
Abhängig von der möglichen Rekursionstiefe und dem damit verbundenen Speicherbedarfs (wirkt sich bekanntlich auch auf die Laufzeit aus) ist manchmal eine iteratives durchlaufen von Bäumen vorteilhafter.
-
in sachen laufzeit ist in c++ meist iteration schneller. das liegt aber auch nur an den schwachen compilern. manche probleme, wie die türme von hanoi drängen einem die rekursion so stark auf, daß rekursive lösungen sogar ein wenig schneller als iterative sind. und manche probleme gehen nur rekursiv (ich zähle iteration mit nem künstlichen stack als rekursion).
bei den nicht entarteten bäumen dürfte es fast wie bei den türmen von hanoi liegen.