Wie Baumdurchquerungen funktionieren?

Question

Dies ist der Code für Vorordnungsdurchquerung -

void preOrder(node *root) 
{  
    if(root!=NULL) 
    { 
     cout<<root->data<<" "; 
     preOrder(root->left); 
     preOrder(root->right); 
    }   
} 

Wenn wir den letzten Knoten auf der linken Seite erreicht haben, wie es auf der rechten Seite Knoten gehen wird? Ich meine, es gibt keine Verbindung zwischen linkem und rechtem Knoten, obwohl beide das gleiche Elternteil haben, aber nach dem Erreichen des letzten Knotens, wie geht es zurück zu seinem Elternteil?

Answer 1

Ja! Es gibt keine direct Verbindung zwischen zwei Kindern eines Knotens.

Jetzt, um Ihnen mit dem oben genannten Rekursionscode zu helfen, sehen Sie sich das folgende Bild von Geeksforgeeks an.

Springen direkt in die am weitesten links stehende Knoten , wie Sie wissen, wie Sie es erreichen, wollen wir jetzt verstehen, wie es zurück an ihre Mutter bewegt, und so weiter und so fort.

Wenn Sie aus der folgenden Zeile kommen, die Sie definitiv wegen if(root!=NULL) als das linke Kind und das rechte Kind von 4 wird Null, immer noch nicht bekommen? Keine Sorge, siehe folgende Erklärung.

Nun sind Sie an dem am weitesten links stehenden Knoten, die 4 in diesem Fall ist die Linie, die für das Erreichen dieses Knoten verantwortlich ist:

preOrder(root->left) und Sie haben nicht gesehen, was bisher unter dieser Linie ist

dh Sie haben nie die folgende Zeile gesehen:

preOrder(root->right);.

Links Kind 4 ist null, wegen denen die Rekursion Bedingung Pausen und Sie schließlich preOrder(root->right); .Dieses sehen, ist nicht irgendeine Art von Zauberei, das ist, was Rekursion ist. Jetzt, wenn Sie das richtige Kind von 4 sehen, das ist wieder null.

gut, was ist der Wert von root jetzt?

Der Wert von Wurzel ist 2 weil 2 der einzige Wert ist, die Sie an erster Stelle auf die 4 nahm. Rekursion ist wie Level innerhalb eines Levels, und wenn das letzte Level beendet ist, geht der Aufruf zurück auf das Level darüber, welches 2 für 4 ist. Und schließlich bringt die folgende Linie es zum rechten Kind von 2, das 5 ist.

preOrder(root->right);

Take away:

1) Jedes Mal, wenn Sie cout<<root->data<<" "; sehen drucken Sie den Wert des aktuellen Root.

2) Immer wenn Sie preOrder(root->left); sehen, gehen Sie zum linken Kind der Wurzel.

3) Immer wenn Sie preOrder(root->right); sehen, gehen Sie zum richtigen Kind von root.

4) Wenn der Wert von root NULL ist, tun Sie nichts und Sie werden zurück in die aufrufende Zeile, die entweder preOrder(root->left); oder preOrder(root->right); sein wird.

Wenn wir folgen, was ich oben gesagt Sie die Vorordnungsdurchquerung für den gegebenen binären Baum erraten kann, die sein wird:

1 2 4 5 3

Nun, rate ich Ihnen Rekursion zu lesen und zu lernen und nähern sich dann die oben Problem wieder.

Answer 2

Sie rufen die Funktion rekursiv auf. Jeder Aufruf an preOrder erstellt, was wir einen Rahmen auf dem Ausführungsstapel des Threads nennen. Diese Rahmen folgen jedem Pfad im Baum. Wenn Sie return von der Funktion verwenden, wird sein Aufrufrahmen aus dem Stapel entfernt (oder "aufgepufft") und das Steuerelement kehrt zum vorherigen Bild zurück.

Deshalb, wenn Sie ein Blatt erreichen, "Back-Track" zum übergeordneten und dann zum Geschwister-Teilbaum (über den zweiten Anruf an preOrder). Der "Link", von dem Sie sprechen, wird tatsächlich auf dem Ausführungsstapel erstellt.