# Breitendurchlauf Baum. Vorgehen unklar.



## Chris1986 (13. Feb 2008)

Hallo, ich habe eine Frage zu dem Breitendurchlauf von einem Baum.
Ich verstehe die angefügte Methode bfs() nicht.
Es geht ab der Zeile

 while (!L.isEmpty()) {// Solange es noch zu besuchende Knoten gibt..
	        ZahlNode node = (ZahlNode)L.removeHead();

los.

Was bedeutet das Ausrufezeichen vor L.is Empty?
Was bewirkt die Zeile "ZahlNode node = (ZahlNode)L.removeHead();" ?
Da wird ein neuer Knoten mit dem Namen node erstellt und was bekommt er zugewiesen, diese Schreibweise kenne  ich nicht.
Danke !!









```
public class BinTree
{
	public ZahlNode root; // der Wurzelknoten
	public BinTree() { root = null; /* leerer Baum */ }
	
	public void bfs() {
	    ConsList L = new ConsList();
	    L.append(root); // Beginne bei Wurzelknoten
	    while (!L.isEmpty()) {// Solange es noch zu besuchende Knoten gibt..
	        ZahlNode node = (ZahlNode)L.removeHead();
	        do_something(node.z);         // besuche naechsten Knoten ..
	        if (node.left != null)     // und markiere seinen ..
	            L.append(node.left); // linken Kindknoten ..
	        if (node.right != null)     // und seinen ..
	            L.append(node.right);    // rechten Kindknoten
	    }}
	
	
	
	public void do_something(int z) {
		System.out.print(z + " ");
	}
}

public class ZahlNode {
	// das Objekt, welches dem Knoten zugeordnet ist
	public int z; 
	// die beiden Kindknoten
	public ZahlNode left;
    public ZahlNode right;
	public ZahlNode(int z) {
		this.z = z;
		left = right = null;
	}
}

public class ConsList
{
	private Cons head, foot; // Kopf und Fuss der Liste
	public ConsList() { head = foot = null; /* neue leere Liste */ }
	
	public void print() {
		System.out.print("Liste [");
		print(head); 				// rekursive Ausgabe der Cons-Zellen
		System.out.println("]");
	}
	protected void print(Cons cons) {
		if (cons == null) return ;  // letzte Zelle erreicht
		System.out.print(cons.obj); // Objekt ausgeben
		if (cons.next != null) {
			System.out.print(", ");
			print(cons.next);       // Rekursiv weiter 
		}
	
	public void append(Object obj) {
		Cons cons = new Cons(obj);	// neue Cons-Zelle
		if (foot == null) head = foot = cons; // genau eine Cons-Zelle
		else { // hinten anfuegen und Fuss anpassen
			foot.next = cons;
			foot = cons;
		}
	}
	
	public boolean isEmpty() { return head == null;	}
	public Object removeHead() {
		if (head == null) return null;
		Object res = head.obj;
		if (head == foot) head = foot = null;
		else head = head.next;
		return res;
	}
}

	public class Cons 
	{
		public Object obj; // das Objekt in dieser Zelle
		public Cons next;  // Verweis auf die naechste Zelle
		public Cons(Object obj) {
			this.obj = obj;
			next = null;
		}
	}
```


----------



## HeRaider (13. Feb 2008)

Das "!" steht für NOT also bedeutet die Zeile eigentlich nur "Während L nicht leer ist".
Wenn du mit nicht verstehen das hier meinst: "(ZahlNode)"
Das ist einfach ne Konvertierung. Die gerufene Methode gibt ein Object zurück und das muss erst in den Typ ZahlNode "umgewandelt" werden. 

Ich hoffe mal, dass das einigermaßen verständlich war.  :wink:


----------



## SlaterB (13. Feb 2008)

> Was bedeutet das Ausrufezeichen vor L.is Empty? 

Negation, "solange Liste nicht leer ist"

> und was bekommt er zugewiesen, diese Schreibweise kenne ich nicht. 

würdest du
ZahlNode node = (ZahlNode)L.getObjectInHead();

oder länger
Object o = L.getObjectInHead();
ZahlNode node = (ZahlNode) o;
verstehen?

ZahlNode node = (ZahlNode)L.removeHead(); 
macht das gleiche, nur dass zusätzlich Head in der Liste gelöscht wird


----------



## Chris1986 (13. Feb 2008)

SlaterB, vielen Dank, ich hab das jetzt verstanden, dank dir ;-)

Eine kleine Frage hab ich dann noch, und zwar versuche ich gerade den inorder Durchlauf mit Schleifen zu ersetzen:

Die rekusive Methode ist

public void inorder(ZahlNode node) {
		if (node == null) return ;
		inorder(node.left);
		do_something(node.z);
		inorder(node.right);
	}


Jedoch habe ich keine Idee, wie ich das machen könnte.
Ich habe mir zwar schon was überlegt, um die erste Zahl auszugeben, nämlich

while (node =! null)
node = node.left
do_something(node.obj


Jedoch weiß ich nicht, wie ich dann wieder hochspringen könnte. 
Kann man sowas mit Schema machen (eine rekursive Methode umschreiben) ?


----------



## Gast (13. Feb 2008)

HeRaider danke  , dass du mir geholfen hast war mir nach den beiden Postings klar


----------



## SlaterB (13. Feb 2008)

> und zwar versuche ich gerade den inorder Durchlauf mit Schleifen zu ersetzen

?!

du hast doch gerade bfs() erklärt bekommen
was so ziemlich genau ein 'inorder Durchlauf mit Schleife' ist


----------



## Gast (13. Feb 2008)

funktioniert das dann nur mit der Hilfe von Listen?


----------



## SlaterB (13. Feb 2008)

einen derartigen Durchlauf kenne ich nur als Umsetzung mit Listen, ja,
entspricht den xy Knoten, die sonst im Stack von xy Aufrufen hängen bleiben


----------



## Gast (13. Feb 2008)

Also bfs habe ich verstanden.
Beim Inorder Durchlauf muss ich erstmal nach ganz unten links, das macht bfs z.B. nicht. Wie müsste ich das denn verändern, damit es einem inorder entspricht?


----------



## Gast (13. Feb 2008)

Ich versteh das einfach nicht, wie man darauf kommt, mit welchen Überlegungen. Wenn ich das fertige sehen würde, würde ich es verstehn. Nur... wie kommt man da drauf?


----------



## SlaterB (13. Feb 2008)

hmm, interessant,

spontan überlegt:
jeder Knoten braucht eine Markierung, bzw. in die Liste kommen nicht (nur) die Knoten, sondern die Knoten + Markierung,

du nimmst wieder in jedem Schleifendurchlauf den obersten Knoten der Liste,
(1) wenn es markiert ist, dann einfach nur ausgeben,
ansonsten: Knoten markieren und in die Liste erst den rechten Nachfolger, dann den Knoten selber, und dann den linken Nachfolger einfügen

so dass bei keinen weiteren Kindern im nächsten Schritt
erst der linke Nachfolger, dann der Knoten (markiert) und dann der rechte Nachfolger erscheint und wegen (1) in dieser Reihenfolge ausgegeben werden,

in der Art muss man sowas durchdenken, 
genauer werde ich es nicht erklären, können auch noch Fehler drin sein,
falls zu schwer für dich, dann eben nicht, will nicht deine Hausaufgaben komplett machen 

> Ich versteh das einfach nicht, wie man darauf kommt, mit welchen Überlegungen. 

wenn denken alleine nicht geht, dann hilft auch ausprobieren,
schau dir z.B. die original-bfs()-Operation an und vertausche L.append(node.left); sowie L.append(node.right); 

gut, das bewirkt nicht soviel,
der Trick, den Originalknoten nochmal in die Liste zu schreiben (aber markiert, sonst Endlosschleife) ist ein ganz anderer,
wie man darauf kommen kann, kann ich auch nicht sagen


----------



## Gast (13. Feb 2008)

Erstmal danke für die Hilfe.
Das sind keine Hausaufgaben, das mache ich nur für mich zu Übungszwecken.
Leider komme ich nicht weiter.
Was für + Markierungen meinst du?


----------



## SlaterB (13. Feb 2008)

wie gesagt kann ich persönlich dir nicht weiterhelfen, ich bin kein Programmierkurs


----------



## Gast (13. Feb 2008)

es wäre sehr freundlich, wenn du mir das erklärst, da mir das nicht ganz klar ist. Da würde ich mich shr drüber freuen.

Dazu ist das Forum doch da?!


----------



## Gast (13. Feb 2008)

sonst schreib mir doch bitte die Zeilen hin, wie es funktioniert


----------



## maki (13. Feb 2008)

Mit Fragen wie "Erklär mir mal Java" bist du hier falsch, musst auch selbst ein bisschen was tun.

zB lesen 

http://www.galileocomputing.de/openbook/javainsel7/


----------



## Gast (13. Feb 2008)

dann würd ich sofort erkennen, wie das  funktioniert


----------



## Gast (13. Feb 2008)

also ich find, das ist schon etwas spezielles. Wie ge4sagt, ich würde mich sehr freuen, wenn jmd. die entsprechenden zeilen schreiben würde, dann könnte ich direkt sehen, wie das funktioniert.

Ist ja nicht so, dass ich jetzt den Syntax von einem Befehl nachfrage. Nur, ich weiß eben nicht, wo ich genau DAS nachlesen kann...


----------



## Gast (13. Feb 2008)

??


----------



## SlaterB (13. Feb 2008)

hartnäckig 

was du haben willst ist kein Standardproblem sondern eine individuelle Programmierung,
sowas gibts für x00 Euro bei MyHammer.de oder so


----------



## Gast (13. Feb 2008)

also es wäre schön, wenn du mir das sagst.

Deswegen, um anderen zu helfen, gibt es das Forum doch, dachte ich.
Es wäre wirklich sehr nett


----------



## Gast (13. Feb 2008)

also es wäre schön, wenn du mir das sagst.


Was spricht denn dagegen? Wenn ich die Zeilen hätte, würd ichs sofort verstehen. Ich komm selber nicht drauf, und fänd es schade, wenn ich jetzt beim nächsten Thema weitermachen müsste, ohne diese Lücke zu schließen.

Deswegen, um anderen zu helfen, gibt es das Forum doch, dachte ich..gerade, wenn es kein Standartproblem ist, was man überall nachlesen kann.


----------



## SlaterB (13. Feb 2008)

nun, wenn du das weiter diskutieren willst..

natürlich kann man auch bei Nicht-Standardproblemen weiterhelfen,
bei vielen Punkten macht es Sinn, 
z.B. wenn du ein respektabler User mit 500 Postings wärst, der auch anderen hilft,
oder wenn du mitarbeitest und kleine Winke helfen, dass jeweils größere Schritte weiterkommst,
auch wäre es hilfreich, wenn du dein Eindruck machten würdest, als hättest du irgendeine Ahnung, worum es hier geht, 

aber so passiert gar nix, so kannst du genausogut dein wöchentliches Arbeitsblatt von der Uni posten und sagen 
'bis Montag 9.00 bitte für mich fertig programmieren, danke'
(dass es deiner Meinung nach keine Hausaufgabe ist, ist nicht entscheidend  )

ich weiß die Lösung nicht per Handschlag, das ist ein individuelles Thema, was ich auch erst programmieren müsste,
was bringt es mir, diese Zeit zu investieren?
schlimmstenfalls kommst du beim nächsten Problem wieder angerannt, na danke


----------



## Gast (13. Feb 2008)

jetzt hast du ein posting mehr.


----------

