Binärbaum

Ok danke das hab ich jetzt verstanden. Er gibt tatsächlich den knoten ganz links zuerst aus. Dann dann rechten Teil des Knoten. Was ich noch nicht versteh warum er dann überhaupt weiter macht. Ist der rechte Knoten NULL dann bricht er doch komplett ab. Es kommt im Code doch nichts mehr.

Danke

Ergänzung:

Die if Sequenz prüft ob tree!= NULL;

ist der rechte Knoten NULL dann geht er doch gar nicht mehr in den Block rein.
Das ist mein Problem.

Danke

Dravere

@blurry333,
Die Funktion ruft sich intern immer wieder selbst auf, was ja auch der Sinn der Rekursion ist. Wenn du nun ganz links unten angekommen bist, hast du x Funktionen aufgerufen. Wenn nun tree == NULL ist, dann wird die x'te Funktion verlassen und die (x-1)'te Funktion geht weiter und ruft nun inorder(tree->right) auf. usw. usf.

Am besten schnappst du dir mal ein Bleistift und ein Block und skizzierst dir den Callstack nach, dann sollte es dir klar werden. Oder dann fehlt dir irgendwelches Grundwissen über Funktionen

Grüssli

hmm. Aber die Abruchbedingung ist doch tree!=NULL.
Kommt er jetzt im rechten Knoten auf einen Zeiger der auf Null zeigt also noch
keine Kinder hat. Dann bricht er doch ab.

um mein Problem mal deutlich zu machen , habe ich eine kurze Rekursion
geschrieben.

void rekur(int x)
{

if(x>0)              //Hier bricht doch auch die Rekursion ab, wieso aber nicht 
{                    // bei tree!= NULL
cout<<x<<" "; x--;
rekur(x);
}

}

jencas

Die Rekursion bricht dort ab, wo sich die Funktion innerhalb der Funktion nicht mehr selbst aufruft. Und bei Dir ist das der Fall, wenn tree == NULL ist.

Dravere

Ganz korrekt ist die Rekursion erst fertig, wenn der erste Funktionsaufruf vollständig durchgelaufen ist. Ist das wirklich so schwer zu verstehen?

Ich skizziere mal das Nodebeispiel:

call inorder("value")                           ---> erster Aufruf

if "value" valid? -> yes
call inorder("left of value")                   ---> zweiter Aufruf
  if "left of value" valid? -> yes
  call inorder("left of left of value")         ---> dritter Aufruf
    if "left of left of value" valid? -> no
    return                                      ---> dritter Aufruf beendet
                                                     zurück zum Zweiten
  call inorder("right of left of value")        ---> vierter Aufruf
    if "right of left o value" valid? -> no
    return                                      ---> vierter Aufruf beendet
                                                     zurück zum Zweiten
  return                                        ---> zweiter Aufruf beendet
                                                     zurück zum Ersten
call inorder("right of value")                  ---> fünfter Aufruf
  if "right of value" valid? -> yes
  call inorder("left of right of value")        ---> sechster Aufruf
    if "left of right of value" valid? -> no
    return                                      ---> sechster Aufruf beendet
                                                     zurück zum Fünften
  call inorder("right of right of value")       ---> siebter Aufruf
    if "right of right of value" valid? -> no
    return                                      ---> siebter Aufruf beendet
                                                     zurück zum Fünften
  return                                        ---> fünfter Aufruf beendet
                                                     zurück zum Ersten
return                                          ---> erster Aufruf beendet

- Rekursions Ende -

Also damit sollte es nun echt klar werden. Ansonsten muss ich wohl aufgeben ...

Grüssli

Danke für deinen Erklärungsversuch.
Mein Problem ist weiterhin dass ich in meinem Code keine return Anweisung habe.
Wie komme ich also zu dem parent Knoten zurück.

SG1

Die Funktion kehrt zurück, sobald sie komplett durchlaufen ist. Wie jede andere Funktion auch.

Dravere

blurry333 schrieb:

Wie komme ich also zu dem parent Knoten zurück.

void foo()
{
}

// Ist das gleiche wie:

void foo()
{
  return;
}

Wenn die Funktion am Ende ankommt oder zu einem return gelangt, wird sie beendet und kehrt in die Aufruferfunktion zurück. Die Aufruferfunktion macht dann dort weiter, wo sie die Funktion aufgerufen hat.

Also kurz an zwei unterschiedlichen Funktionen erläutert:

void bar()
{
  // bar wird ausgeführt.
}

void foo()
{
  // Der Prozess/Thread kommt in dies Funktion foo.

  bar(); // bar wird aufgerufen.
  // bar wurde ausgeführt.

  bar(); // bar wird aufgerufen.
  // bar wurde ausgeführt.
}

Lass es dir an einer einfachen Rekursion von einem Programm zeigen

#include <iostream>

int recTest(int x)
{
  std::cout << "Funktion Nr. " << x << " startet." << std::endl;

  if(x < 5)
  {
    recTest(x + 1);

    std::cout << "Zurueck in Funktion Nr. " << x << std::endl;
  }
  else
  {
    std::cout << "x >= 5" << std::endl;
  }

  std::cout << "Funktion Nr. " << x << " endet." << std::endl;
}

int main()
{
  recTest(0);

  return 0;
}

Grüssli

Herzlichen Dank .
Dein letztes Code Beispiel hat mir die Augen geöffnet.
Ich hatte die Funktionsweise des Stack außer Acht gelassen.

Vielen herzlichen Dank !