Iteratives InOrder

[ModellbahnerTT]

Hallo zusammen,

habe hier einen schönen Binärbaum, der auch vollständig funktioniert.
Rekusrives InOrder geht auch einwandfrei.

Nun soll die InOrderausgabe jedoch iterativ gelößt werden.

Gar nicht so einfach... das schöne an der Rekursion ist ja, dass ich mich bis unten hin hangel und dann von unten nach oben aufarbeite.
Geht ja leider mit einer iterativen Lösung nicht.
Ich weiß jedoch, dass ich jede Rekursion zu einer Whileschleife umwandeln kann.

Meine Idee ist, dass es eine ineinander verschachtelte While-Schleife mit insgesamt 3 whiles sein muss.
Also wenn ich nach ganz unten links will, kein Problem. Wäre über Lösungshinweise oder gleich die ganze Lösung sehr dankbar.

Hier mein Code: (Hinweis, wer sich nur den relevanten Teil anschauen möchte, sollte von unten beginnen zu lesen. Die letzten beiden Methoden sind die relevanten.)

class BinTree{

private Integer item; // In Aufgabe: wert
private BinTree left, right; // links, rechts
    
    BinTree search(Integer item){
    BinTree iter = this;

    while (iter.item != null){
        if (iter.item < item)
            iter = iter.right;
        else if (iter.item > item)
            iter = iter.left;
        else // Hier gilt: iter.item == item
            return iter; // Knoten gefunden
    }
    return iter; // Einfuegestelle gefunden
    }

void insert(Integer item){
    // Finde Einfuegeposition
    BinTree node = search(item);
    if (node.item != null)
        return; // Wert bereits enthalten

    // Forderung aus Aufgabenstellung
    node.item = item;
    node.left = new BinTree();
    node.right = new BinTree();
}

private void remove1(){
    // Hier gilt: Knoten hat Wert und zwei BinTrees
    // Hoechstens einer der beiden hat einen Wert.
    // Waehle einen Sohn, der Wert besitzt
    // oder egal welchen Sohn wenn keiner einen hat.
    BinTree son = right;
    if (left.item != null)    
    son = left; // Hochschieben des Sohns
    this.item = son.item;
    this.left = son.left;
    this.right = son.right;
}

private void remove2(){
    // Hier gilt: Knoten hat Wert und zwei BinTrees
    // Beide haben einen Wert
    // Finde linkesten Knoten im rechten BinTree    
    BinTree leftest = right;
    while (leftest.left.item != null)
         leftest = leftest.left;

    // Hier gilt: leftest hat keinen linken Nachbarn
    item = leftest.item;
    leftest.remove1();
}

void remove(Integer item){
    BinTree node = search(item);
    if (node.item == null)
        return; // Wert nicht enthalten

    // Hier gilt: node hat Wert und zwei BinTrees
    // Pruefe ob Knoten zwei oder weniger Nachfolger hat
    if (node.left.item != null && node.right.item != null)
    node.remove2(); // zwei Nachfolger
    else
    node.remove1(); // weniger
}

//InOrder Ausgabe
void inOrderRek(){
    if (left != null)
        left.inOrderRek();
    if (item != null)   
    System.out.print(item+" ");
    if (right != null)
    right.inOrderRek();
}

void inOrderIter(){
    BinTree iter = this;
    while (iter.left.left!=null){
        iter=iter.left;
        System.out.print(iter.item+" ");}
    }
}

Aller besten Dank und Gruß schon mal

 

[SlaterB]

in der Rekursion merkst du dir im Stack der verschachtelten Aufrufe bestimmte noch zu bearbeitende Knoten,
in der Iteration muss das genauso passieren, dort kannst du eine Liste/ einen Stack verwenden,
eine einzelne Schleife reicht dann

soviel als erster Hinweis mit guter Hoffnung, dass du es hauptsächlich noch alleine machen willst

 

[ModellbahnerTT]

Hey SlaterB,

besten Dank für die Tipps.
Eine Frage bzgl. der Schleife, du sagst ja, man benötige nur eine Schleife.
Schließt das aus, dass in dieser Schleife noch weitere Schleifen (verkettet) vorkommen?

Nachtrag: Kann es sein, dass ich unbedingt einen Elternzeiger brauche?

 

[SlaterB]

was sind verkettete Schleifen?
aber sagen wir mal so: in dem Algorithmus muss nur einmal die Buchstabenkombination 'while' auftauchen,
und kein 'for',
Zeiger brachst du auch keine, sondern eine Liste, die Reihenfolge darin entspricht dem Rekursionsstand

während du dich bei inOrderRek() zum allerlinkesten Blatt vorarbeitest, hast du x offene Rekursionsstufen mit den jeweils höheren Knoten,
entsprechend sind bei der iterativen Variante genau dieselben Knoten in der Liste gemerkt

 

[ModellbahnerTT]

Hallo,

ist zwar nett gemeint aber es ist mir natürlich klar, dass ich mind. eine while-schleife verwenden muss...
Morgen ist Abgabe, werde jetzt nochmal eine Methode mit einem Parentknoten versuchen (um dann wieder rauf zu kommen).
Würde mich jetzt so langsam sehr auf Antworten freuen, die mich möglichst schnell ans Ziel bringen.

Momentan kommt mir das eher wie ein Rätzel hier vor. Ist zwar gut gemeint und wenn ich noch endlos Zeit hätte, würde ich ja noch was weiter knobbeln aber so langsam rennt mir die Zeit davon.

Besten Gruß und Dank

 

[SlaterB]

du hast ja nun keinen Rechtsanspruch darauf,
wenn du es nicht entwickeln kannst, nichtmal mit diesen Hinweisen, dann nicht,
schau dir danach die Musterlösung an

ich meinte das zu 50% auch an andere Poster, die meist gleich ganzen Code hinschreiben,
wenn es noch jemand macht, kann ich das natürlich nicht aufhalten

noch ein letzter Tipp: bei google müsste man sowas auch finden

edit:
Parentknoten ist auch nicht schlecht, von Knoten zu Knoten springen, wenn Blatt dann ausgeben, wenn linker Nachfolger, dann dahin,
wenn bereits von links kommend auf Weg nach oben (merken vom vorherigen Verarbeitungsschritt), dann auch rechte Knoten betrachten

 

[ModellbahnerTT]

Versteh mich nicht falsch, hatte das Gefühl, dass du die Lösung schon hättest mir aber Tipps geben wolltest, damit ich da auch hinkomme. Ist ja auch richtig so aber wie gesagt morgen abgabe.

Wenn es darauf keine Punkte geben würde, würde ich mir tatsächlich die Musterlösung anschauen..
Gegooglet habe ich auch schon.

So also bin jetzt am Parentknoten dran.
Meine Idee war das zuerst in die Suche zu implementieren, dann kam mir jedoch die idee, das wie inorder zu gestalten. Die sucht ja auch alles ab.

Nur irgendwie werden leider nur die ersten beiden Knoten von der Wurzel aus bearbeitet.
Der Rest läuft zwar durch (sehe ja die Ausgabe) aber es wird nichts gesetzt.

[Java]
void setzeElternRek(){
if (left != null)
this.left.parent=this;
left.inOrderRek();

if (item != null)
System.out.print(item+" ");

if (right != null)
this.right.parent=this;
right.inOrderRek();
}
[/code]

Jemand einen Tipp?

 

[SlaterB]

- mal verwendest du left, mal this.left,

- die Einrückung läßt vermuten, dass zwei Zeilen zu einem if gehören, es fehlen aber Klammern,
Java schert sich nicht um Einrückung

- wieso sind die Rekursionsaufrufe inOrderRek(); und nicht wieder setzeElternRek()?

- wieso die Ausgabe System.out.print() in setzeElternRek(), es sollte doch anscheinend erstmal nur um das Setzen des Parents gehen

 

[ModellbahnerTT]

- mal verwendest du left, mal this.left,
- wieso sind die Rekursionsaufrufe inOrderRek(); und nicht wieder setzeElternRek()?

Oh mann!!! War ein dummer Flüchtigkeitsfehler von mir, wegen copy & paste...
Bin auch grad drauf gekommen.

Jetzt geht’s auf jeden Fall

void setzeElternRek(){
    if (left != null){
        left.parent=this;
        left.setzeElternRek();}
        
    if (item != null)   
        System.out.print(item+" ");
    
    if (right != null){
        this.right.parent=this;
        right.setzeElternRek();}
}

Besten Dank