In-Order Tree Traversal

[DKKA]

Hallo,

Irgendwie verstehe ich nicht, warum folgende Methode keine In-Order Tree Traversal in einer Liste zurück gibt:

Code: Alles auswählen

    def in_order_traversal(self, list=[]):
        if not self.root_value:
            return None
        if self.left:
            self.left.in_order_traversal(list)
        list.append(self.root_value)
        if self.right:
            self.right.in_order_traversal(list)
        return list

Wo liegt hier der Fehler? Vielen Dank

[BlackJack]

@DKKA: Was gibt es denn zurück? Also beim *ersten* Aufruf. Bei allen weiteren hast Du das Problem das es nur *eine* Liste gibt, weil Default-Werte nicht bei jedem Aufruf ausgewertet werden, sondern nur einmal wenn die ``def``-Anweisung für die Methode ausgeführt wird.

[DKKA]

@DKKA: Was gibt es denn zurück? Also beim *ersten* Aufruf. Bei allen weiteren hast Du das Problem das es nur *eine* Liste gibt, weil Default-Werte nicht bei jedem Aufruf ausgewertet werden, sondern nur einmal wenn die ``def``-Anweisung für die Methode ausgeführt wird.

Bei folgender Struktur:

Code: Alles auswählen

      6
  2      7
1   3
  4   5

gibt es diese liste zurück:
[1,2,4,3,5,6,7]

Hm ich dachte mir, ich könnte das innerhalb nur einer Methode lösen...

[EyDu]

Und was erwartest du für ein Ergebnis? Die Liste sieht doch vollkommen korrekt aus. Hast du im Baum vielleicht die drei und die vier vertauscht?

[DKKA]

Und was erwartest du für ein Ergebnis? Die Liste sieht doch vollkommen korrekt aus. Hast du im Baum vielleicht die drei und die vier vertauscht?

Tatsächlich.....
Problem ist nun gelöst. Gibt es jedoch noch einen Trick, wie ich die Liste wieder entleeren könnte beim letzten aufruf? So dass ich halt eben nur eine Liste und eine Methode verwende?

[BlackJack]

@DKKA: Der ”Trick” ist nicht die Liste leeren zu wollen, sondern immer eine neue zu nehmen, dann stellt sich das Problem gar nicht erst. Üblicherweise setzt man als Default-Wert dazu `None` und testet darauf als erstes in der Funktion oder Methode und wenn das Argument `None` ist, dann bindet man eine leere Liste an den Namen.

Code: Alles auswählen

    def in_order_traversal(self, result=None):
        if result is None:
            result = list()

Hier sieht man auch ganz gut warum es eine blöde Idee ist Namen von eingebauten Funktionen für etwas anderes zu verwenden. Wenn ich das nicht zu `result` umbenannt hätte, würde die letzte Zeile von dem Quelltextschnippsel nicht funktionieren.

Wenn Du schon die Ergebnisliste als Akkumulator durch die ganzen Aufrufe mitschleppst, könntest Du übrigens auch gleich den rekursiven Aufruf eliminieren und das ganze damit auch für tiefe Bäume nutzbar machen ohne dass Du an das Rekursionslimit stösst weil der Aufrufstapel zu voll wird.

Edit: Mit Deinem ersten Test auf einen Wert hast Du übrigens ein Problem mit Werten die „falsch” sind. Du kannst also keine 0, kein leeres Tupel, keine Leerzeichenkette, oder irgend einen anderen Wert die bei `bool()` das Ergebnis `False` liefert, in dem Baum speichern.

[DKKA]

@DKKA: Der ”Trick” ist nicht die Liste leeren zu wollen, sondern immer eine neue zu nehmen, dann stellt sich das Problem gar nicht erst. Üblicherweise setzt man als Default-Wert dazu `None` und testet darauf als erstes in der Funktion oder Methode und wenn das Argument `None` ist, dann bindet man eine leere Liste an den Namen.

Code: Alles auswählen

    def in_order_traversal(self, result=None):
        if result is None:
            result = list()

Hier sieht man auch ganz gut warum es eine blöde Idee ist Namen von eingebauten Funktionen für etwas anderes zu verwenden. Wenn ich das nicht zu `result` umbenannt hätte, würde die letzte Zeile von dem Quelltextschnippsel nicht funktionieren.

Wenn Du schon die Ergebnisliste als Akkumulator durch die ganzen Aufrufe mitschleppst, könntest Du übrigens auch gleich den rekursiven Aufruf eliminieren und das ganze damit auch für tiefe Bäume nutzbar machen ohne dass Du an das Rekursionslimit stösst weil der Aufrufstapel zu voll wird.

Edit: Mit Deinem ersten Test auf einen Wert hast Du übrigens ein Problem mit Werten die „falsch” sind. Du kannst also keine 0, kein leeres Tupel, keine Leerzeichenkette, oder irgend einen anderen Wert die bei `bool()` das Ergebnis `False` liefert, in dem Baum speichern.

Danke, an das Handling von falschen Werten habe ich gar nicht gedacht.
Warum stösst es auf das Rekursionslimit? Kannst du das erläutern? Ich verstehe das nicht, es ist doch jeweils die selbe Liste die weitergegeben wird....?
Und einen anderen Weg als der Rekursion die Liste mitzugeben, gibt es wohl nicht, ausser man teilt es auf zwei Methoden auf oder macht es halt iterativ?

[BlackJack]

@DKKA: Man kann nicht beliebig oft rekursive Aufrufe verschachteln. Das Programm bricht dann irgendwann mit einem ``RuntimeError: maximum recursion depth exceeded`` ab. Es ist nicht die Liste das Problem, sondern die Anzahl der gleichzeitig aktiven Funktionsaufrufe.