Wie genau funktioniert die Druckanweisung in diesen beiden Methoden?

Question

Dies ist gegenüber dem binären Suchbaum. Ich durchquere den Baum auf zwei Arten. 1) InOrder Traversal Ein Inorder-Traversal von Baum t ist ein rekursiver Algorithmus, der dem linken Teilbaum folgt; Sobald keine weiteren Teilbäume mehr zu verarbeiten sind, verarbeiten wir den rechten Teilbaum. Die Elemente werden in der Reihenfolge von links nach rechts verarbeitet. 2) PostOrder Traversal Ein Postorder-Traversal von Baum t ist ein rekursiver Algorithmus, der den linken und rechten Teilbäumen folgt, bevor das Wurzelelement verarbeitet wird. Die Elemente werden in der Reihenfolge Links-Rechts-Wurzel verarbeitet.

Ich bin verwirrt darüber, wie die Rekursionsmethoden und print-Anweisungen arbeiten. Könntest du mich bitte aufklären?

static void inOrder(Leaf root){ 
    if(root != null){ 
     inOrder(root.left); 
     System.out.print(root.value+" "); 
     inOrder(root.right); 
    } 
} 
static void postOrder(Leaf root){ 
    if(root != null){ 
     postOrder(root.left); 
     postOrder(root.right); 
     System.out.print(root.value+" "); 
    } 
} 

Answer 1

Wie jede Rekursionsmethode benötigt sie einen Basisfall, eine Bedingung, um die Rekursion zu stoppen. In diesem Fall ist es, wenn "root" null ist.

Beachten Sie, dass die Variable root beim ersten Aufruf in der Methode nur die tatsächliche Wurzel des Baums ist. Bei konsekutiven Aufrufen wird das Element auf der linken oder rechten Seite weitergeleitet.

Bei der Methode inOrder werden die Elemente gedruckt, die weiter unten im linken Zweig des Baums liegen. Also "geht es auf eine Ebene" auf dem Baum, bevor der Druck aufgerufen wird. Dies bedeutet, dass wenn das Element ein Blatt auf einem linken Zweig hat, es das Blatt drucken wird, bevor es zu dem rechten Zweig geht.

in der postOrder-Methode, es wird am weitesten unten auf der Baum gehen es gehen und dann drucken Sie die Elemente, so dass für beide Zweige (links und rechts). Dies bedeutet, dass die Blätter des Baumes zuerst gedruckt werden, während die tatsächliche Wurzel das letzte Element sein wird.

Wenn Sie Probleme bei der Visualisierung haben, schlage ich vor, dass Sie den Baum in einem Papier zeichnen und den Code mit einem kleinen Beispielbaum mit dem Debuggen auf Eclipse ausführen, so dass Sie Zeile für Zeile der Ausführung folgen können überquert den Baum.

Answer 2

Die Funktion funktioniert so, dass jede Funktion eine einzelne lange Zeile ausgibt, die alle Werte des Baums enthält. Wenn jeder der Algorithmen den Baum durchläuft, hängt er den aktuellen Wert des Knotens zusammen mit einem Leerzeichen an den Ausgang an. Zum Beispiel, wenn wir den folgenden Baum betrachten:

 
    2 
/\ 
1 3 

Der erste Algorithmus beginnt an der 2, dann rufen Sie sich auf der linken Kind, 1. Die Funktion wird dann rufen Sie sich auf der linken Kind, das null ist , so wird es sofort zurückkehren. Die Funktion druckt dann "1" auf die Konsole. Die Funktion ruft sich selbst auf dem rechten Kind auf, das null ist, so dass es sofort zurückkehrt. Die Funktion kehrt dann zu 2 zurück und "2" wird auf der Konsole ausgegeben. Die Funktion wird sich dann auf dem rechten Kind aufrufen, welches die 3. Die Funktion wird sich auf dem linken Kind aufrufen, das zurückgibt, dann "3" auf die Konsole drucken, und sich dann auf das rechte Kind, das zurückkommt, anrufen. Die Funktion kehrt dann zu 2 zurück und kehrt zu dem zurück, was sie aufgerufen hat. Die Konsole am Ende sagen:

1 2 3

Eine ähnliche Sache für den zweiten Algorithmus passieren würde, es sei denn die Funktion vor dem Drucken des Wurzelknoten der linken und rechten Kinder und drucken, 1 bzw. 3, gehen würde, 2, was in der folgenden Ausgabe:

1 3 2

Wenn Sie Schwierigkeiten zu verstehen, es haben, es sich selbst einen Baum ziehen profitieren würde und den Code Schritt für Schritt folgen, um zu sehen, was der Computer tut.