Binärbaum

[itse]

Hallo Zusammen,

ein Binärbaum soll erzeugt werden, dieser enthält dann wieder Kinder (left und right) usw. Je nachdem wie man den Baum erzeugt.

Dies geschieht über addLeft und addRight. Eine Frage: Ist diese Methode so richtig? Es soll nicht berücksichtigt werden, ob bereits ein Objekt zugewiesen wurde.

Ich nun ein Problem beim Kopier-Konstruktor und der Ausgabe der beiden Bäume.

Problem Kopier-Konstruktor:

Es sind ja Referenzdatentypen, also reicht eine einfache Wertzuweisung nicht aus. Also wollte ich neue Objekte erzeugen, diese dann den Parameter übergeben. Jedoch erhalte ich immer eine NullPointer-Exception.

Wie kann man das realisieren, zur Unterscheidung, damit es neue unabhänige Objekte sind, soll beim Namen noch ein c_ angehängt werden.

Problem Ausgabe:

Bei dem Baum, so wie es bisherig erzeugt wurde, sollte folgendes rauskommen (Format: Knoten, left, right):

node1 node2 node3
node2 node4
node4 node7
node7
node3 node5 node6
node5
node6

Bei mir kommt aber:

node1 node2 node3
node2 node4
node4 node7
node7


node3 node2
node3 node5 node6
node5
node6 node5
node6

Und einen Knoten 3 mit Kind 2 gibt es ja gar nicht und auch Knoten 6 mit Kind 5 sollt es nicht geben.

Wo liegt da der Fehler? Geht es nicht auch einfacher?

Vielen Dank.

public class Node {
    String name;
    Node left;
    Node right;

    //Konstruktor
    Node(String name) {
	this.name = name;
	this.left = null;
	this.right = null;
    }

    //Kopier-Konstruktor, tiefe Kopie des aktuellen Knotens
    //sammt aller Unterknoten
    Node(Node node) {
	this.left = new Node(node.left);
	this.right = new Node(node.right);
	this.name = "c_" + node.name;
    }

    //Rechtes Objekt zuweisen
    public void addLeft(Node node) {
	this.left = node;
    }

    //Linkes Objekt zuweisen
    public void addRight(Node node) {
	this.right = node;
    }

    // Ausgabe des kompletten Baums, beginnend mit dem aufrufenden Node-Objekte
    public void output() {
	if (this.name == null)
	    return;

	if (this.name != null) {
	    System.out.print(this.name + " ");

	    if (this.left != null) {
		System.out.print(this.left.name + " ");
		if (this.right != null)
		    System.out.print(this.right.name + " ");
		System.out.println();
		this.left.output();
	    }
	    if (this.right != null) {
		System.out.print(this.right.name + " ");
		if (this.left != null)
		    System.out.print(this.left.name + " ");

		System.out.println();
		this.right.output();
	    }
	    System.out.println();
	}
    }

    public static void main(String[] args) {

	// Initialisierung Knoten
	Node node1 = new Node("node1");
	Node node2 = new Node("node2");
	Node node3 = new Node("node3");
	Node node4 = new Node("node4");
	Node node5 = new Node("node5");
	Node node6 = new Node("node6");
	Node node7 = new Node("node7");

	// Beispiel Binärbaum
	node1.addLeft(node2);
	node1.addRight(node3);
	node2.addLeft(node4);
	node3.addLeft(node5);
	node3.addRight(node6);
	node4.addLeft(node7);

	// Erstelle tiefe Kopie des ersten Objekts des Baums
	Node node = new Node(node1);

	// Test und Ausgabe der Tiefen Kopie
	System.out.printf("%-13s %n", "Tiefe Kopie:");
	node.output();
	System.out.println();

	// Test und Ausgabe des Originals
	System.out.printf("%-13s %n", "Original:");
	node1.output();
	System.out.println();

    }
}

 

[Civilazi]

Nur ganz kurz, da keine Zeit mehr:

Der Copyconstructor ruft sich immer wieder selbst auf und wandert am linken Ast in den Baum, bis er irgendwann bei nem Blatt ist. Da ist node.left == null. Aber dein Konstruktor will weitermachen, also:
new Node(null.left) und schon hast du deine NPE

Die Ausgabe hab ich mir nicht angeguckt.

 

[itse]

Danke hat mich schon mal weitergebracht.

Ich habe es nun so umgeschrieben:

    Node(Node node) {
	int count =0;
	
	if(count%2 == 0){
	
	    if (node.left != null) {
		this.name = "c_" + node.name;
		this.left = new Node(node.left);
		count++;
	    }
	}
	if(count%2 != 0){  
	    if (node.right != null) {
		this.name = "c_" + node.name;
		this.right = new Node(node.right);
		count++;
	    }
	}
    }

Das mit dem count soll denn Sinn haben, dass nach erneutem Aufruf druch new Node(), nun das rechte Kind kopiert werden soll. Da ist mir nicht besseres eingefallen.

Jedoch wird noch immer nicht, die komplette Struktur kopiert. In der Ausgabe steht folgendes:

Tiefe Kopie:
c_node1 c_node2 c_node3
c_node2 c_node4
c_node4 null


c_node3 c_node2
c_node3 null null
null null

Wie kann ich denn am besten den kompletten Baum durchlaufen, damit jedes Objekt kopiert wird?

 

[itse]

Hallo,

ich komme einfach nicht weiter. Es ist ja vorgegeben, dass die Ausgabe in folgender Reihenfolge ausgegeben werden soll:

Knoten
Left
Right

Also als preOrder. Ich erhalte aber immer die oben genannte Ausgabe. Ich habe zum Beispiel auch folgendes probiert:

	if(this.name != null)
	    System.out.print(this.name+" ");
	if(this.left.name != null)
	    System.out.print(this.left.name+" ");
	if(this.right.name != null)
	    System.out.print(this.right.name+" ");

	System.out.println();

	    if(this.left != null)
	        this.left.output();

	    if(this.right != null)
	        this.right.output();
    }

Es kommt aber immer eine NullPointerException nach der zweiten Zeile. Wie kann ich den Inhalt des kompletten Baums ausgeben?

Kann ich dies dann auch für den Copy-Konstruktor nutzen, damit der Baum komplett kopiert wird, also eine tiefe Kopie erzeugt wird?

 

[Landei]

if(this.left != null && this.left.name != null) u.s.w.

 

[itse]

Ich hab den Fehler nun gefunden, so funktionierts:

	if (this.name != null)
	    System.out.print(this.name + " ");
	if (this.left != null)
	    System.out.print(this.left.name + " ");
	if (this.right != null)
	    System.out.print(this.right.name + " ");

	System.out.println();

	if (this.left != null)
	    this.left.output();

	if (this.right != null)
	    this.right.output();