Wie für Inorder Traversal Baumrückkehrfunktion in Rekursion

Question

Ich habe diesen Code unten verwenden:

void inOrder(struct node* r) 
{ 
    if (r==NULL) 
    return; 

    else 
    { 
     inOrder(r->left); 
     printf("%d ", r->value); 
     inOrder(r->right); 
    } 
} 

Ich habe diesen dummen Zweifel:

Wenn die unterste linke Kind Wird als root übergeben, es ist nicht null. In der nächsten Iteration wird root Null sein (als linkes unterstes unterstes unterstes Kind ist null) und es wird auf return stoßen.

Bricht diese Rückgabeanweisung das Steuerelement an die Hauptfunktion (oder wo auch immer es heißt), ohne etwas zu drucken?

Verhalten sich Rückkehr in Rekursion anders?

Answer 1

Diese return wird die Steuerung an die Position zurückgeben, an der die aktuelle "Schicht" der Funktion aufgerufen wird.

Funktionsaufrufe sind in einer Struktur namens Stack organisiert. Stellen Sie sich vor, dass in Ihrem Computer eine Box ist. Der Computer kann ein Element in die Box einfügen (oben auf die anderen Elemente in der Box), oder er kann das Element an der Oberseite der Box entfernen. Betrachten Sie den folgenden Code.

void f(int x) 
{ 
    if (x == 0) 
     return; 
    f(x - 1); 
} 

Wenn Sie f(2) in der Hauptfunktion aufrufen, setzt der Computer f(2) in die Box. Wenn f(2) ausgeführt wird, ruft es innerhalb der Funktion f(1) auf, so dass der Computer f(1) in das Feld (über f(2)) steckt. Als f(1) ruft auch f(0), der Computer setzt f(0) in die Box.

Wenn f(0) ausgeführt wird, wird nichts aufgerufen, und es entspricht der return Anweisung. So entfernt der Computer f(0) aus der Box, und f(1) ist jetzt oben auf der Box. Ihr Computer weiß also, dass es f(1) anstatt main ist, die f(0) aufruft, so wird es f(1) weiter ausführen. Es ist dasselbe, wenn f(1) zurückgegeben wird.

Answer 2

Wenn das unterste untergeordnete Kind als Root übergeben wird, ist es nicht null.

void inOrder(struct node* r) 
{ 
if (r==NULL) 
return; 

else{ 
inOrder(r->left); 
printf("%d ", r->value); 
inOrder(r->right); 
} 

} 

In Ihrem obigen Code, wenn Sie die unterste linke Kind als root passieren.

Sie führt zuerst diese Linie

if (r==NULL) return; 

als r nicht gerade null wird es diese Rückkehr überspringen. so, pausiert die aktuelle Ausführung für einen Moment und wieder aufnehmen, wenn dieser Aufruf zurückkehrt

Im anderen Teil würde es jetzt

else{ 
    inOrder(r->left); 

Hier ausführen, es ist die gleiche Funktion wieder aufrufen.

Nun inOrder(r->left); Anruf inOrder(struct node* r); wieder mit null als Parameter r auf diesen Aufruf. Da übergeben Sie r->left, die Null ist.

so, dieser Aufruf zu inorder treffen wird return

if (r==NULL) return; 

Wie es gibt wird es letzte Instanz inorder Anruf wieder aufnehmen, die bei inOrder(r->left); Anruf pausiert.

Dies ist möglich, weil, wenn Sie eine Funktion aufrufen innerhalb einer Funktion ist unterhält eine call stack.

Jetzt, nach der Wiederaufnahme wird die nächste Zeile

printf("%d ", r->value);

auszuführen, die Druckt den Wert in Ihrem linken unteren Knoten.

schließlich nennt es die letzte Zeile

inOrder(r->right); die wiederum die Ausführung der aktuellen Funktion werden angehalten und nach dem aktuellen Status der Funktion in Call-Stack Spar es wird die inorder mit null wieder r->right rufen die wieder zurückkehren von

if (r==NULL) return;

und schließlich wird es zur ursprünglichen Ausführung inorder zurückkommen und wieder aufnehmen und da es keine Anweisung links ist es diezurückMethode, wenn Sie von dort aufgerufen und fortsetzen, was in main übrig blieb.

Also, Ihre Antwort ist es wird nur den Wert in der untersten linken Knoten gedruckt.

Answer 3

könnte Ein klassisches Beispiel für Rekursion veranschaulicht das Problem besser

int factorial(int n) 
{ 
    if(n == 0) 
     return 1; 
    return n * factorial(n - 1); 
} 

Wenn wir factorial(3) nennen waren, den Ablauf zu der rekursiv, n == 0, an welchem ​​Punkt factorial bis zum Basisfall rufen wird zurückkehren Punkt, wo es hieß, ist factorial(1) und nicht main.

Also, nein, Ihre Return-Anweisung geht zurück zum Parent-Knoten, wo die Funktion aufgerufen wurde.