Breitendurchlauf Baum. Vorgehen unklar.

Status
Nicht offen für weitere Antworten.
C

Chris1986

Gast
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 !!








Code:
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

Aktives Mitglied
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:
 
S

SlaterB

Gast
> 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
 
C

Chris1986

Gast
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) ?
 
G

Gast

Gast
HeRaider danke , dass du mir geholfen hast war mir nach den beiden Postings klar ;)
 
S

SlaterB

Gast
> 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
 
S

SlaterB

Gast
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
 
G

Gast

Gast
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?
 
G

Gast

Gast
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?
 
S

SlaterB

Gast
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
 
G

Gast

Gast
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?
 
S

SlaterB

Gast
wie gesagt kann ich persönlich dir nicht weiterhelfen, ich bin kein Programmierkurs ;)
 
G

Gast

Gast
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?!
 
G

Gast

Gast
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...
 
S

SlaterB

Gast
hartnäckig ;)

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

Gast

Gast
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
 
G

Gast

Gast
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.
 
S

SlaterB

Gast
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 ;)
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
royale Breitendurchlauf / Dijkstra durch Graph, vereinfacht Allgemeine Java-Themen 3
E XML - Datei Darstellung in IntelliJ als Baum Allgemeine Java-Themen 2
Karl_Der_Nette_Anfänger Hat wer ne Lösung für verknüpfte Postleitzahlen? (Baum/Wurzel Struktur) Allgemeine Java-Themen 11
D 2,3-Baum rekursiv erstellen Allgemeine Java-Themen 20
D Datentypen 2-3 Baum erstellen mit geordnetem int-array Allgemeine Java-Themen 0
L Dependency Injection für Baum-Einträge Allgemeine Java-Themen 9
M Iterator für trinären Baum Allgemeine Java-Themen 0
N Rekursiv Höhe Baum Allgemeine Java-Themen 3
D Baum zeichnen hilfe Allgemeine Java-Themen 4
D if - else Baum vereinfachen Allgemeine Java-Themen 4
A AVL-Baum - Testen ob einer vorliegt Allgemeine Java-Themen 4
M Eclipse Stackoverflow beim Einlesen von großen Bilder in kd Baum Allgemeine Java-Themen 15
G Datentypen TreeMap nach Color sortiert (kd-Baum) Allgemeine Java-Themen 8
M Baum nach Stack plus Objektkonvertierung Allgemeine Java-Themen 5
S Baum mit vordefinierten Werten befüllen Allgemeine Java-Themen 2
D Datenstruktur für Hierarchie/Baum mit Tiefe 3 Allgemeine Java-Themen 8
D Rot-Schwart-Baum denkfehler im code? Allgemeine Java-Themen 6
M Baum Allgemeine Java-Themen 3
K Dependency Baum erstellen/analysieren Allgemeine Java-Themen 2
J Baum mit Adjazensmatrix Allgemeine Java-Themen 8
MQue Tidy HTML baum durchlaufen Allgemeine Java-Themen 5
C Fehler im Quellcode. Suche in einem Baum Allgemeine Java-Themen 3
R Daten aus Baum entsprechend in jTree einfuegen Allgemeine Java-Themen 2
C Daten möglichst schnell einem Baum zuordnen Allgemeine Java-Themen 2
S Datenstruktur für einen Baum Allgemeine Java-Themen 5
N Baum aus Datei laden. Allgemeine Java-Themen 3
B Best Practice Trendanalyse mit NN und Lib, wie vorgehen? (Allgemeiner Ablauf) Allgemeine Java-Themen 5
P PooledConnection früher schließen oder abarbeitung queuen? wie vorgehen Allgemeine Java-Themen 7
K Test-Frist Programmierung - wie vorgehen Allgemeine Java-Themen 5
O Vorgehen um Dateiformate einzulesen Allgemeine Java-Themen 3
X JDK updaten - wie am besten vorgehen? Allgemeine Java-Themen 5
F Vorgehen bei automatischen Programmablauf Allgemeine Java-Themen 2

Ähnliche Java Themen

Neue Themen


Oben