Binärbaum
-
Kann mir bitte mal jemand diesen Code erklären. Ich komm mit der Rekursion einfach nicht klar. Wann wird der rechte Zweig durchlaufen ?
struct node { int data; node *left; node *right; }; void inorder(node *tree) { if(tree!=NULL) { inorder(tree->left); cout<<tree->data; inorder(tree->right); getch(); } }
-
Ok, Code Tags. Nächste mal dann bitte C/C++ Code Tags.
Ich gehe mal davon aus das es um diese drei Zeilen geht, der Rest dürfte klar sein oder?
inorder(tree->left); cout<<tree->data; inorder(tree->right);Der Durchlauf des rechten Zweigs wird begonnen sobald es auf auf der linken Seite keine Elemente mehr gibt. Also im Normalfall am unteren Ende des Baumes.
Mal dir doch mal auf einen Zellulosedatenträger einen Binary Tree auf und versuch das nachzuverfolgen. Leg dir einfach im Programm einen Tree mit ein paar Verzweigungen an und probier ein bisschen herum.#edit: Zugegebenermaßen, diese Rekursion ist nicht unbedingt die einfachste. Bist du dir sicher das du eine "normale" Rekursion verstanden hast? Also z.B. sowas:
class Node { public: Node *next; int data; }; Node *node; void displayList() { std::cout << node->data << std::endl; if(node->next != NULL) { displayList(); } }
-
inorder(tree->left); cout<<tree->data; //Warum hier Ausgabe der Daten, inorder(tree->right); // aber beim Durchlauf des rechten Zweigs nicht ???
-
blurry333 schrieb:
inorder(tree->left); cout<<tree->data; //Warum hier Ausgabe der Daten, inorder(tree->right); // aber beim Durchlauf des rechten Zweigs nicht ???Der Punkt ist, du rufst für den rechten Zweig ebenfalls inorder() auf.
inorder(tree->right);Entsprechend werden auch für diesen die Daten ausgegeben.
Jeder Knoten hat ja wiederum zwei Verzweigungen, eine links und eine rechts.
Node | -------------- | | Links RechtsZuerst wird praktisch der letzte Knoten der am weitesten Links ist ausgegeben, danach kommt der rechte "daneben". Der Baum wird praktisch von unten nach oben ausgegeben.
-
Danke für dein Bemühen .
Wieso steht denn der tree->left Zeiger gleich ganz unten ?
wenn ich den root node übergebe würde er doch ganz oben stehn.Steig noch nicht ganz dahinter.
Danke
-
inorder(tree->left); cout<<tree->data; inorder(tree->right);cout wird ja zum ersten mal erst dann aufgerufen wenn du ganz am Ende bist. Mal angenommen wir sind am dem Punkt wo das if(tree != NULL) zuschlägt.
void inorder(node *tree) { if(tree!=NULL) { inorder(tree->left); cout<<tree->data; // <= hier inorder(tree->right); getch(); } }Dann bist du ja praktisch "ganz links unten" im Baum und die Funktion kommt zum ersten mal zurück, also bist du dort wo ich es Code markiert habe. Dann werden die Daten also zum ersten mal ausgegeben und er prüft ob auf der rechten Seite evtl. noch etwas ist. Wenn nein kommt auch diese Funktion zurück und du kommst an den zweiten Node von links unten gesehen und hast wieder genau die gleiche Prozedur: er gibt die Daten des Nodes aus und prüft dann ob nicht rechts noch etwas da ist. Sinnvoller wäre die Funktion wohl so:
void inorder(node *tree) { if(tree!=NULL) { cout<<tree->data; inorder(tree->left); inorder(tree->right); getch(); } }Dann würde der Baum von oben nach unten ausgegeben (zugegebenermaßen, erst die linke Seite :S).
-
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
-
@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 nuntree == NULList, dann wird die x'te Funktion verlassen und die (x-1)'te Funktion geht weiter und ruft nuninorder(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); } }
-
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.
-
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.
-
Die Funktion kehrt zurück, sobald sie komplett durchlaufen ist. Wie jede andere Funktion auch.
-
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 !
