Binärbaum

Status
Nicht offen für weitere Antworten.
T

Tombery

Aktives Mitglied
Hi,

wir sollen einen binärbaum erstellen (zusätzlich mit einer tiefen Kopie) mit diesen methoden:

Java: 
public class Node { 

        private String name; 
        private Node left; 
        private Node right; 
        int wert; 
        
        //Custom-Konstruktor 
        
        Node(String name){ 
                
                //Erster Knoten(Wurzel) 
                name = "node"+wert; 
                wert = 1; 
                
        } 
        
        //Copy-Konstruktor kopiert ersten/aktuellen Knoten und alle untergeordneten 
        
        Node(Node node1){ 
                
                name = "c_node"+wert; 
        } 
        
        addLeft(Node node){ 
                
                //neues Objekt 
                Node neu = new Node("node"+wert); 
                
                //der Objektvariable left wird das neue Objekt zugewiesen 
                left = neu.Node("node"+wert); 
                
                //Wert steigt um 1 
                wert = (this.wert + 1); 
        } 
        
        addRight(Node node){ 
                
                //neues Objekt 
                Node neu = new Node("node"+wert); 
                
                //der Objektvariable left wird das neue Objekt zugewiesen 
                right = neu.Node("node"+wert); 
                
                //Wert steigt um 1 
                wert = (this.wert + 1); 
                
        } 
        
        void output(){ 
                
                //Ausgabe der Baumhierarchie als einfache Tabelle 
                
        } 
        
}

und die sollte zu dieser anwendung passen:

Java: 
public class Application { 


        public static void main(String[] args) { 
                
                // Initialisierung der 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"); 

                // Aufbau eines beispielhaften Binärbaums 
                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(); 

        } 
}

doch... jetzt stehe ich erstmal da und weiß nicht weiter...muss man diesen binärbaum wirklich mit referenzen machen? stimmt mein ansatz so weit?
ich habe auch im internet schon ein oder das andere programm dazu gesehen...doch wirklich verständlich waren sie nicht.
 
Meldanor

Meldanor

Bekanntes Mitglied
Na, ein Baum ist eine Liste von Elementen, wo jedoch jedes Element auf mehr als ein anderes Element verweist.

Das wirste so im Internet auch finden ^^

Deswegen die Erläuterung.

In einem Arrays sind alle Elemente in Felder gespeichert. Das ist wie auf einem Schachbrett, wo du WEISST, dass auf 5 und 7 die und die Figur steht, sagen wir mal der Springer.

In einer Liste wäre es so, dass du weißt, dass die Liste anfängt mit dem Bauer. Du weißt jedoch nicht, was nach dem Bauern ist, indem du dort schaust wie beim Feld, sondern, du schaust nach, worauf der Bauer zeigt.
Bauer1 zeigt auf Bauer2 und Bauer2 zeigt auf Bauer3.
Im Array wäre das
0. Element = Bauer1;
1. Element = Bauer2;
2. Element = Bauer3;

Im Baum ist es wie eine Liste, nur dass Bauer1 nicht "nur" auf Bauer2 zeigen kann, sondern auch auf Bauer3.
Sprich: Bauer1 zeigt auf Bauer2 und Bauer3. Bauer2 jedoch nicht auf Bauer3 und Bauer3 nicht auf Bauer2.
Dafür kann Bauerr2 auf Dame zeigen und König, und Bauer3 zeigt auf Läufer und Turm.

Um nun an den Turm ranzukommen, musst du schauen, wer auf den Turm zeigt, dass ist Bauer3. Nun aber zeigt auch Bauer1 auf Bauer3.
Im Binärbaum zeigt jeder Knoten(jeder "Bauer", jeder "Turm") auf maximal 2 andere Knoten.
 
J

javimka

Top Contributor
Da es sich um Java handelt, wirst du um die Benutzung von Referenzen nicht herumkommen ;) (Pointer exisitieren ja nicht).

Dein Copy Konstruktor ist etwas komisch. Du solltest doch sicher die Eigenschaften des gegebenen Nodes übernehmen. Stattdessen weist du dem Attribut name einen String zu, wobei Wert zu diesem Zeitpunkt noch gar nicht definiert, also sicherlicht 0 sein wird.

Deine setLeft/Reight Methoden machen meiner Meinung nach auch nicht so richtig Sinn. Wazu instanzierst du ein neues Objekt. Du könntest doch einfach this.left = node schreiben und damit den übergebenen Node als left speichern.
 
T

Tombery

Aktives Mitglied
so?

Java: 
public class Node {

	private String name;
	private Node left;
	private Node right;
	//Anfangswert ist 1
	int wert = 1; 
	
	//Custom-Konstruktor
	
	Node(String name){
		
		//Erster Knoten(Wurzel)
		name = "node"+this.wert;
		
	}
	
	//Copy-Konstruktor kopiert ersten/aktuellen Knoten und alle untergeordneten
	
	Node(Node node1){
		
		//Kopie für ersten Knoten wird erstellt
		Node copy = new Node("c_node"+this.wert);
		
	}
	
	addLeft(Node node){
		
		//der Objektvariable left wird das Objekt zugewiesen
		this.left = node;
		
		//Wert steigt um 1
		wert = (this.wert + 1);
		
		return node;
	}
	
	addRight(Node node){
		
		//der Objektvariable left wird das Objekt zugewiesen
		this.right = node;
		
		//Wert steigt um 1
		wert = (this.wert + 1);
		
		return node;
		
	}
	
	void output(){
		
		//Ausgabe der Baumhierarchie als einfache Tabelle
		
		
	}
	
}
 
J

javimka

Top Contributor
im Custom Konstruktor steht: [c] name = "node" + this.wert[/c]
Wenn schon, dann ist es this.name, denn im Moment speicherst du den neuen Namen auf das übergebene Argument ab, was gar keinen Effekt hat. Ausserdem ist this.wert jedesmal 1, also wirst du allen Knoten einfach eine 1 anhängen, was wohl auch kaum gewollt sein kann.
Dein Copy-Konstruktor erzeugt ein neues Objekt vom Typ Node... und macht dann nichts damit. Das sollte doch eher sowas geben wie [c]this.name = node.name; this.wert = node.wert;[/c], um die Attribute des übergebenen Nodes zu kopieren.
Gehen wir mal davon aus, dass es aus irgendeinem Grund sinnvoll ist, dass du den Wert um eines erhöhst, wenn du einen Knoten links oder rechts anhängst, dann bleibt immer noch der Fehler, dass du node zurückgibst, obwohl deine Funktion gar keinen Rückgabeparameter definiert. Auch nicht void, wie ich es gemacht hätte.

Diese Fehler hättest du doch alle auch herausgefunden, wenn du es einmal hättest laufen lassen. Das kompiliert ja nicht einmal.
 
T

Tombery

Aktives Mitglied
habe jetzt das hier:

aber es kommen so seltsame ergebnisse raus...und die tiefe kopie funktioniert nicht oô

Java: 
public class Node {

	private String name;
	private Node left;
	private Node right;

	//Custom-Konstruktor
	
	Node(String name){
		
		//Knoten definieren
		this.name = name;
		
	}
	
    //Copy-Konstruktor kopiert die Baumhierarchie
	
	Node(Node node){
		
		//dieselben Prüfungen wie bei dem Original
		
		if (this.name != null){
			
            System.out.print("c_" + this.name + " ");
            
		}
		
        if (this.left != null){
        	
            System.out.print("c_" + this.left.name + " ");
        
        }
        
        if (this.right != null){
        	
            System.out.print("c_" + this.right.name + " ");
            
        }
            
            System.out.println();
            
        
        
        if (this.left != null){
        	
            this.left.output();
        }
     
        if (this.right != null){
        	
            this.right.output();
        
	    }
		
	}
	
	void addLeft(Node node){
		
		//Linkes Objekt
		this.left = node;
		
	}
	
	void addRight(Node node){
		
		//Rechtes Objekt
		this.right = node;
		
	}
	
	void output(){
		
		//Ausgabe der Baumhierarchie als einfache Tabelle
		
		//wenn keine Knoten vorhanden, keine Ausgabe
		
		if(this.name == null){
			//keine Ausgabe
		}
		
		//wenn Knoten vorhanden, Ausgabe
		
		if(this.name != null){
			
			System.out.print(this.name + " ");
		
		  //wenn linker Kindknoten vorhanden, Ausgabe
		  if(this.left != null){
			
			System.out.print(this.left.name + " ");
			
		  //wenn rechter Kindknoten vorhanden, Ausgabe
		  if(this.right != null)
			
			System.out.print(this.right.name + " ");
		  
		    //neue Zeile
			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();
	        
		  }
		
	}
	
}
 
Zuletzt bearbeitet:
J

javimka

Top Contributor
Zeile 78:
Java: 
        if(this.name == null){
            //keine Ausgabe
        }
Kannst du mir das erklaeren?
 
T

Tombery

Aktives Mitglied
wenn objekt/name ist gleich null (also existiert NICHT), wird keine ausgabe gemacht, also nichts.

also so im gegenzug zu dem, dass wenn objekt/name exisitiert, eine ausgabe gemacht wird.

aber...du hast recht, man kann es auch weglassen. war nur für vollständigkeit....

wegen tiefe Kopie:

habs hier falsch.....eine tiefe kopie geht ganz anders. werde ich morgen machen und mal sehen, ob ich es dann hinbekomme.

die Ausgabe:

Original:
node1 node2 node3
node2 node4
node4 node7
node7

stimmt soweit. und von genau diesem sollen wir ne tiefe kopie machen.
 
Zuletzt bearbeitet:
T

Tombery

Aktives Mitglied
habe jetzt die tiefe kopie versucht...aber mir wird bei der ausgabe unter "tiefe kopie:" rein garnichts angezeigt oÔ

obwohl ich es so gemacht habe wie im vorlesungsbeispiel:

Java: 
//Beispiel: Deep-Copy Kopierkonstruktor für die Klasse RationalRange:

class RationalRange {

RationalRange(RationalRange rr) {

lowerRange = new Rational(rr.lowerRange);
upperRange = new Rational(rr.upperRange);

}
}

mein quelltext:

Java: 
public class Node {

	private String name;
	private Node left;
	private Node right;

	//Custom-Konstruktor
	
	Node(String name){
		
		//Knoten definieren
		this.name = name;
		
	}
	
    //Copy-Konstruktor kopiert die Baumhierarchie
	
	Node(Node node){
		
		//dieselben Prüfungen wie bei dem Original
		
		
		if (this.name != null){
			
			//Tiefe Kopie vom Knoten
			this.name = node.name;
			
            System.out.print("c_" + this.name + " ");
            
		}
		
        if (this.left != null){
        	
        	//Tiefe Kopie vom linken Kindknoten
        	this.left = new Node(node.left);
        	
            System.out.print("c_" + this.left.name + " ");
        
        }
        
        if (this.right != null){
        	
        	//Tiefe Kopie vom rechten Kindknoten
        	this.right = new Node(node.right);
        	
            System.out.print("c_" + this.right.name + " ");
            
            System.out.println();
            
            this.left.output();
            
        }
            
            System.out.println();
		
	}
	
	void addLeft(Node node){
		
		//Linkes Objekt
		this.left = node;
		
	}
	
	void addRight(Node node){
		
		//Rechtes Objekt
		this.right = node;
		
	}
	
	void output(){
		
		//Ausgabe der Baumhierarchie als einfache Tabelle
		
		//wenn keine Knoten vorhanden, keine Ausgabe
		
		if(this.name == null){
			//keine Ausgabe
		}
		
		//wenn Knoten vorhanden, Ausgabe
		
		if(this.name != null){
			
			System.out.print(this.name + " ");
		
		  //wenn linker Kindknoten vorhanden, Ausgabe
		  if(this.left != null){
			
			System.out.print(this.left.name + " ");
			
		  //wenn rechter Kindknoten vorhanden, Ausgabe
		  if(this.right != null)
			
			System.out.print(this.right.name + " ");
		  
		    //neue Zeile
			System.out.println();
			
			this.left.output();
			
		  }
	        System.out.println();
	        
		  }
		
	}
	
}
 
J

javimka

Top Contributor
In deinem Copy-Konstruktor schreibst du [c]if (this.name!=null) then ... [/c]. Das macht relativ wenig Sinn, denn name wird gerade mit null initialisiert, das heisst, diese If-Klausel rein gar nie durchlaufen. Der Copy-Kunstruktor muss doch gar keine Rücksicht darauf nehmen, in welchem Zustand die attribute zur Zeit sind, der muss doch eifach die Attribute des übergebenen Objektes übernehmen. Also musst du alle if-Klauseln löschen und Befehle wie [c]this.name = node.name[/c] so stehen lassen.
Ohne all die Output-Befehle sollte der Copy-Konstruktor genau 3 Zeilen benötigen, um alles Nötige zu kopieren.
 
T

Tombery

Aktives Mitglied
habe ich gemacht...aber jetzt geht garnichts mehr! :eek:

Java: 
public class Node {

	private String name;
	private Node left;
	private Node right;

	//Custom-Konstruktor
	
	Node(String name){
		
		//Knoten definieren
		this.name = name;
		
	}
	
    //Copy-Konstruktor kopiert die Baumhierarchie
	
	Node(Node node){
			
			//Kopie vom Knoten
			this.name = node.name;
      
        	//Tiefe Kopie vom linken Kindknoten
        	this.left = new Node(node.left);
        
        	//Tiefe Kopie vom rechten Kindknoten
        	this.right = new Node(node.right);
		
	}
	
	void addLeft(Node node){
		
		//Linkes Objekt
		this.left = node;
		
	}
	
	void addRight(Node node){
		
		//Rechtes Objekt
		this.right = node;
		
	}
	
	void output(){
		
		//Ausgabe der Baumhierarchie als einfache Tabelle
		
		//wenn keine Knoten vorhanden, keine Ausgabe
		
		if(this.name == null){
			//keine Ausgabe
		}
		
		//wenn Knoten vorhanden, Ausgabe
		
		if(this.name != null){
			
			System.out.print(this.name + " ");
		
		  //wenn linker Kindknoten vorhanden, Ausgabe
		  if(this.left != null){
			
			System.out.print(this.left.name + " ");
			
		  //wenn rechter Kindknoten vorhanden, Ausgabe
		  if(this.right != null)
			
			System.out.print(this.right.name + " ");
		  
		    //neue Zeile
			System.out.println();
			
			this.left.output();
			
		  }
	        System.out.println();
	        
		  }
		
	}
	
}
 
J

javimka

Top Contributor
Müsste jetzt eigentlich funktionieren. Kann es sein, dass du einen Zyklus in deinem Baum hast, also dass Knote A einen linken Knoten B hat, der wiederum einen linken oder rechten Knoten A hat? Das muss natürlich strikt verhindert werden, weil sonst der Copy-Konstruktor abwechslungsweise Knoten A und B kopiert, ohne je an ein Ende zu kommen.

//EDIT: Das würde zu einem StackOverflowError führen. Tut es das? Oder was passiert sonst?
 
T

Tombery

Aktives Mitglied
die fehlermeldung ist diese hier:

Exception in thread "main" java.lang.NullPointerException
at Aufgabe2.Node.<init>(Node.java:27)
at Aufgabe2.Node.<init>(Node.java:30)
at Aufgabe2.Node.<init>(Node.java:30)
at Aufgabe2.Node.<init>(Node.java:30)
at Aufgabe2.Node.<init>(Node.java:30)
at Aufgabe2.Application.main(Application.java:31)

ich glaube weil ich nur kopien mache von wurzel, linken knoten und rechten knoten, aber nicht von den darauffolgenden, kann das sein? aber wie mache ich das für darauffolgende?
 
J

javimka

Top Contributor
Das Problem ist folgendes. Früher oder später kopierst du einen Knoten ohne einen linken Sohn. Dabei führst du [c]this.left = new Node(node.left)[/c] aus, wobei node.left ja null ist. Aber du führst den Copy-Konstruktor aus und es kommt zum Befehl node.left, wobei node hier null ist und dadurch entsteht die NullpointerException.

Versuch es mal so:
Java: 
            //Tiefe Kopie vom linken Kindknoten
            if (node.left!=null)
            this.left = new Node(node.left);
        
            //Tiefe Kopie vom rechten Kindknoten
            if (node.right!=null)
            this.right = new Node(node.right);
 
Status
Nicht offen für weitere Antworten.

Aktuelle Jobs

Neue Themen


Oben