Binär-Baum durchwandern ohne Rekursion oder einen Stack zu benutzen

[SportIstMord]

Hallo,

habe einen Binär-Baum dessen Struktur folgendermaßen aussieht:

struct bintree {
    int val;
    struct bintree *left, *right;
};

Gibt es eine Möglichkeit den Baum zu durchwandern und alle Werte zusammenzuzählen ohne Rekursion oder einen Stack zu benutzen? Habe überleget die Pointer irgendwie zu modifizieren um den Baum anders darzustellen und ihn dann zu durchwandern, bin aber irgendwie nicht weitergekommen.

[milan1612]

http://vadmyst.blogspot.com/2007/09/non-recursive-binary-tree-traversal.html

[SportIstMord]

Mhhh aber da muss ich ein visited Flag hinzufuegen.

[naja]

irgendwo musst du dir merken, was du schon gesehen hast, entweder auf nem stack, im baum oder sonst wo

[volkard]

Und warum magst Du keinen Stack verwenden? Das visited-Flag ist doch viel häßlicher.

[volkard]

SportIstMord schrieb:

Habe überleget die Pointer irgendwie zu modifizieren um den Baum anders darzustellen und ihn dann zu durchwandern, bin aber irgendwie nicht weitergekommen.

Fädeln. Manchmal sieht man Bäume, da hat jeder Knoten auch noch einen Zeiger auf den Knoten, der bei In-Order-Traversierung ihm folgen würde. Und andersrum dazu, sonst wirds schwierig. Aber das wäre hier übertrieben.
Was dir vollkommen reicht, ist, wenn jeder Knoten noch einen Zeiger auf seinen Papa hat.
Und natürlich nicht zu vergessen, die Summe einfach mitführen und aktuell zu halten. Dürfte das Billigste sein.

[rapso]

wenn ein binearbaum eine saubere ordnung hat (damit meine ich keine ueberlappenden nodes), kann man immer wieder von anfang losgehen und beim durchgehen des baumes anhand der ordnung dafuer sorgen, dass man nur nodes besucht > letzter ordnung.

[rapso]

volkard schrieb:

Und warum magst Du keinen Stack verwenden? Das visited-Flag ist doch viel häßlicher.

weil man manchmal keinen stack hat.

[Bashar]

Wenn man sich pro Knoten 1 Flag spart, hat man den Platz für den Stack.

[Bashar++]

Alternativ macht man pro Verzweigung einen neuen Thread auf.

[ipsec]

Bashar++ schrieb:

Alternativ macht man pro Verzweigung einen neuen Thread auf.

Und das ist keine Rekursion, weil ...?

[ipsec++]

ipsec schrieb:

Bashar++ schrieb:

Alternativ macht man pro Verzweigung einen neuen Thread auf.</Sarkasmus>

Und das ist keine Rekursion, weil ...?

... weil das kein Stack ist:

Bashar schrieb:

Wenn man sich pro Knoten 1 Flag spart, hat man den Platz für den Stack.

Gibt es eine Möglichkeit ... ohne Rekursion oder einen Stack zu benutzen

[ipsec]

Pseudocode:

bearbeite_baum(baum)
{
    bearbeite_wert(baum);
    starte_thread(bearbeite_baum(baum.links));   // Hoppla, Rekursion
    starte_thread(bearbeite_baum(baum.rechts));  // nochmal
}

[Peinlich?]

Rechthaberischsein macht einen manchmal blind.