Suchbaum iterativ absteigen?

[HansPeterLoft]

Hallo, ich habe hier einen Binärbaum aus Objekten mit Namen.
Nun steige ich aber für den linken oder rechten Nachfolger in addElement(...){...}
immer rekursiv ab, wie kann ich aber iterativ absteigen z.B mit einer while-Schleife?
Wenn ich einfach:

while(p.left != null) {
	p = p.left;
}

versuche, dann zeigt ja das Objekt p auf seinen linken Nacholger, beim rekursiven Abstieg
hingegen bleibt p gleich, aber z.B p.left.left.left wird hinzugefügt usw...
Wie mache ich das Iterativ? Gruss

public class Main {
	public static void main(String [] args) {
		List list = new List("Hans");
		list.addElement("Peter", list);
		list.addElement("Kurt",list);
		
		list.out(list);
	}
}

class List {
	String name;
	List left,right;
	List(String n) {
		name = n;
		left = null;
		right = null;
	}
	
	void addElement(String n, List p) {
		if(n.compareTo(p.name) < 0) {
			if(p.left != null)
				addElement(n,p.left);
			else p.left = new List(n);
		} else {
			if(p.right != null)
				addElement(n,p.right);
			else p.right = new List(n);
		}
			
	}
	
	void out(List p) {
		if(p != null) {
			out(p.left);
			System.out.println(p.name);
			out(p.right);
		}
	}
}

 

[SlaterB]

du kannst das Objekt, auf das p vor der Schleife zeigt, eben vor dieser Schleife in einer anderen Variablen merken,
brauchst du alle Objekte auf dem Weg, kannst du sie in eine Liste einfügen,
oder was immer nötig erscheint

wenn du die out-Methode meinst.., nun da wäre viel zu merken, dann doch eher wieder von jedem Objekt auf dem Vorgänger verweisen,
ein Durchlauf indem bei jedem Objekt ein Marker 'warIchSchonDa' auf true/ false gesetzt wird,
bzw. doch in separater Datenstruktur merken, welche Knoten schon besucht

kennst du
Dijkstra-Algorithmus ? Wikipedia
Liste noch zu besuchender Nachbarknoten?
so in der Art, nur Reihenfolge wichtig,
Stack-Gedanke kommt ins Spiel

 

[HansPeterLoft]

Ok, ich möchte das nur bei addElement(){} versuchen.

Den Dijkstra kannte ich noch nicht, werde mir den mal anschauen, danke.

 

[SlaterB]

bei addElement() kann dir der Zustand von p egal sein, brauchst du nicht weiter,
Variablen beim Aufrufer der Methode werden nicht beeinträchtigt

dass man von außen
> list.addElement("Peter", list);
aufrufen muss ist generell unschön,

> list.addElement("Peter");
sollte reichen, diese Methode ohne Parameter könnte ja zunächst die andere mit this, sich selber, als Parameter aufrufen
das aber nur in der rekursiven Variante

bei iterativ kann und sollte der Parameter in jedem Fall wegfallen,
beginne auch hier mit
> List p = this;

edit:
auch in der Rekursion könnte der Parameter immer wegfallen, eine Methode reicht immer:

 if(n.compareTo(this.name) < 0) {
            if(this.left != null)
                this.left.addElement(nt);
            else this.left = new List(n)

usw.

das wäre eine saubere Rekursion, jedes List-Objekt kommt auch tatsächlich dran statt nur mehrere Aufrufe beim ersten List-Objekt,
aber je nach Geschmack alles denkbar