Verständnis der Logik der Inorder-Traversal von BST, Python

Question

Ich studiere für Codierung Interviews und arbeiten mit vielen verschiedenen Datenstrukturen.

Ich bin relativ neu zu Tree Probleme und habe täglich Probleme zu üben.

Es ist eine Sache, Formeln zur Erinnerung zu haben, und eine andere, um sie wirklich zu verstehen. Wenn ich etwas verstehe, ist es leicht, dieses Verständnis auf schwierigere Probleme anzuwenden.

Rekursive Lösungen sind für mich etwas schwieriger zu visualisieren und während sie intuitiv Sinn ergeben, versuche ich ein tiefes Verständnis davon zu bekommen, was auf dem Stack passiert.

Ich habe einen Baum und möchte in der Reihenfolge Traversal tun. Kein Problem.

data = [] 

def checkBST(root): 
    if root: 
     checkBST(root.left) 
     data.append(root.data) 
     checkBST(root.right) 
    print(data) 

I geschaffen, um die Datenvariable out zu drucken, was auf jedem durch die Methode übergeben gespeichert wird.

Es gedruckt

[] 
[1] 
[1] 
[1, 2] 
[1, 2, 3] 
[1, 2, 3] 
[1, 2, 3] 
[1, 2, 3, 4] 
[1, 2, 3, 4, 5] 
[1, 2, 3, 4, 5] 
[1, 2, 3, 4, 5, 6] 
[1, 2, 3, 4, 5, 6, 7] 
[1, 2, 3, 4, 5, 6, 7] 
[1, 2, 3, 4, 5, 6, 7] 
[1, 2, 3, 4, 5, 6, 7] 

ich logisch bin versucht zu schauen, was geschieht, und wollen wissen, ob meine Logik korrekt ist.

Es gibt 15 gedruckte Ergebnisse und 7 Knoten. Wir kommen jedoch zu 15, weil es 8 Orte gibt, die auf Knoten überprüft wurden, wo der Knoten None ist. Das passiert auf den Knoten 1, 3, 5, 7.

Wir prüfen die linke Hälfte des Baumes vor der rechten.

[] 
#nothing stored because we move onto Node 2 as we don't hit the base case. 
[1] 
#1 stored because Node 1 doesn't have a left value. So we move onto the append call. 
[1] 
#1 returned because Node 1 doesn't have a right value. 
[1, 2] 
#2 stored because because we finished checking the left side and moved onto append data. 
[1, 2, 3] 
#3 is stored because we are calling the in order traversal on the right side of two now. 
[1, 2, 3] 
#3 is returned again because it doesn't have a root.left 
[1, 2, 3] 
#3 is returned again because it doesn't have a root.right 
[1, 2, 3, 4] 
# we hit the append method for 4, now we move onto the in order traversal on the right 
[1, 2, 3, 4, 5] 
[1, 2, 3, 4, 5] 
[1, 2, 3, 4, 5, 6] 
[1, 2, 3, 4, 5, 6, 7] 
[1, 2, 3, 4, 5, 6, 7] 
[1, 2, 3, 4, 5, 6, 7] 
[1, 2, 3, 4, 5, 6, 7] 

Die rechte Seite wird wie links überprüft werden, so dass ich meine Logik nicht schreiben, wie es überflüssig sein würde.

Ich möchte nur klären, wenn ich dieses Problem im richtigen Format ansehe.

Danke für jede Hilfe, um dies zu verstehen!

Answer 1

Die Kommentare in der Ausgabe sind nicht immer korrekt.

Die erste Ausgabe() passiert, wenn ein Funktionsaufruf das Ende erreicht. Der erste Aufruf, bei dem dies geschieht, ist, wenn root Knoten 1 ist und von dort der erste rekursive Aufruf erfolgt. Dieser Aufruf hat None als Argument, und so ist es das erste Mal, dass ein Anruf die print-Anweisung erreicht.

So haben wir diese laufenden Anrufe:

checkBST(4) 
    checkBST(2) # left child of 4 
     checkBST(1) # left child of 2 
      checkBST(None) # left child of 1 
       print # --> [] 

Wenn diese tiefste Anruf beendet, wird die Funktion mit dem Knoten 1 1 an die Datenliste anhängen, und dann den rekursiven Aufruf für das rechte Kind machen, die auch ist None und [1] ist gedruckt.

Hier ist eine Visualisierung des Prozesses. Die Spalten stellen die Tiefe der Rekursion dar, und die Zeilen repräsentieren die Abfolge der Ereignisse im Laufe der Zeit (nach unten). Die letzte Spalte ist reserviert für den aktuellen Wert von data.Wenn es einen gelben Hintergrund hat, bedeutet es, dass es gedruckt wird.

Hellblau bedeutet, dass der Code bei dieser Rekursionstiefe ausgeführt wird. Dunkles Blau bedeutet, dass der entsprechende Funktionsaufruf (auf dem Stapel) ausstehend ist und darauf wartet, dass der verschachtelte rekursive Aufruf zurückgegeben wird.

Von diesem Bild können Sie auch die gleiche Leistung, warum manchmal wiederholt wird: es wird bei verschiedenen Rekursionsebenen gedruckt, wie der Algorithmus Rückzieher wird.