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