inorder Traversierung

void print_inorder(tree_node *p) {
    if (p != NULL) {
        print_inorder(p->left);  // print left subtree
        cout << p->data << endl; // print this node
        print_inorder(p->right); // print right subtree
    }
}

Meine Frage wenn der Zeiger tree_node *p übergeben wird, auf welchen
Knoten zeigt denn dieser gerade. Kann ja irgendeiner sein oder?

Sollte es z.B. der root Knoten sein, dann würde er ja bei dessen linken Nachfolger beginnen und die DAten von diesem ausgeben.

Aber eigentlich sollte er doch den ganz unteren linken Knoten zuerst ausgeben.
Muss ich mir den vorher erst suchen ?

Danke !!

Fencer

print_inorder wird rekursiv aufgerufen. D.h. Wenn du als parameter den root knoten übergibst werden zuerst alle Knoten des Linken teilbaums ausgegeben. Die Reihenfolge ist dabei wiederum inorder bsp

R
/ \
L RR
/ \
ll rr

hier wird zuerst print_inorder(R) aufgerufen. diese ruft dann print_inorder(L) auf usw also ist die ausgabereihenfolge

ll L rr R RR

Aber wie kommt er denn zu dem "ll" runter.

Wenn er den root übergibt müßte er doch dessen left ausgeben

Obwohl es liegt ja ganz unten im Stack

Th69

Lies dir mal den Artikel http://de.wikipedia.org/wiki/Rekursive_Programmierung durch, dann sollte es klarer sein...

pumuckl

blurry33 schrieb:

Aber wie kommt er denn zu dem "ll" runter.

Wenn er den root übergibt müßte er doch dessen left ausgeben

Und in der Ausgabe von dessen left kommt vor der Ausgabe der Daten wieder der rekursive Aufruf für den left vom left - und immer so weiter, bis der left irgendwann null ist.