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

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.

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 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
}

Rechthaberischsein macht einen manchmal blind.