Baum testen

[granini]

Hallo zusammen,

ich habe folgende Frage. Ich habe eine "public class BinTree" geschrieben, die ich gerne testen würde. Ich meine gelesen zu haben, am saubersten wäre es dafür eine neue Klasse zu schreiben?!

Wie mache ich das nun?
Mein Ansatz wäre

public class BinTest {

	public static void main(String args[]) {
        BinTree test = new BinTree ??(Was für ein Wert übergebe ich hier?)

       Aufruf der Methoden
       }
}

Wer kann mir da weiterhelfen?


Und dann habe ich noch eine Frage. Wie unterscheide ich in Java eine rekursive Klasse von einer rekursiven Methode?

Gruss

 

[Illuvatar]

1. Das ist das sauberste, ja, boch sauberer mit Tools wie JUnit, aber das wir für dich wohl nicht nötig sein.
2. Du hast BinTree geschrieben, dann musst du doch wissen, was das für Parameter kriegt :?
3. Was soll eine rekursive Klasse denn sein? 0o

 

[granini]

Ok, ich habe das Problem ad acta gelegt, und eine class implementiert.

Nun, habe ich aber noch Probleme mit der Ausgabe..

Meine Source

class Tree {
	int  content;
	Tree left;
	Tree right;
}

public class BinTree {
	public static Tree root;

	public static Tree create (int i) {
		Tree build = new Tree();
		build.content = i;
		build.left = null;
		build.right = null;
		return build;
	}
	public static void NodeInclude (Tree root, int newNode){
		
		if (newNode < root.content)
		{
			if (root.left == null){
				root.left = create(newNode);
			}
			else {
				NodeInclude(root.left,newNode);
			}
			
			if (root.right == null){
				root.right = create(newNode);
			}
			else {
				NodeInclude(root.right,newNode);
			}
		}
	}
	
	public static void NodeOutput(Tree root){
		if (root != null){
			System.out.println("                  "+root.content+"  ");
			System.out.println(root.left+"               "+root.right);
		}
	}
	
public static void main(String args[]) {
		
	root = create(500);
	NodeInclude(root,444);
	NodeInclude(root,521);
	NodeInclude(root,450);
	NodeInclude(root,857);
	NodeInclude(root,666);
	NodeInclude(root,300);
	BinTree.NodeOutput(root);
	System.out.println();
	   
	}  
}

Es erscheint folgende Ausgabe:

             500  
Tree@119c082               Tree@1add2dd

Wo liegt mein Fehler?
Was kann man am Code ncoh verbessern?

Danke für eure Meinungen..

Gruss

 

[Beni]

Fehler: du solltest die Methode "toString" überschreiben. Die Methode wird benutzt um Objekte in Strings umzuwandeln, und gibt standardmässig "Klasse@Speicheradresse" zurück...

 

[granini]

Fehler: du solltest die Methode "toString" überschreiben. Die Methode wird benutzt um Objekte in Strings umzuwandeln, und gibt standardmässig "Klasse@Speicheradresse" zurück...

Danke für die Antwort. Aber irgendwie kann ich nicht soviel damit anfangen.
Wo nutze ich dann diese Methode??

Oder ich verstehe jetzt was falsch...

:?:

 

[Beni]

Hier benutzt du die:

System.out.println(root.left+"               "+root.right);

.

Wieso? Weil der Compiler diesen Ausdruck (sinngemäss!) in folgendes umschreibt:

StringBuilder s = new StringBuilder();
s.append( root.left.toString() );
s.append( "           " );
s.append( root.right.toString() );
System.out.println( s.toString() );

 

[granini]

Hmm, wieso wird dann eine Zahl bei

System.out.println("                  "+root.content+"  ");

ausgegeben?


Und wie kann ich die einzelnen Nodes dann anzeigen lassen?

Gruss

 

[Leroy42]

root.content ist ein einfacher int für den das Java-System bereits weiß, wie
der auszugeben ist.

Wie du die Nodes anzeigen lassen kannst, hängt davon ab, wie du
sie angezeigt haben willst.

Deine Methode

   public static void NodeOutput(Tree root){ 
      if (root != null){ 
         System.out.println("                  "+root.content+"  "); 
         System.out.println(root.left+"               "+root.right); 
      } 
   }

legt nahe, daß du den ganzen Baum in einer einzigen Zeile ausgeben willst. Dann
mußt du einfach die Methode toString() in deiner Klasse überschreiben. Wichtig ist,
daß du den Methodenkopf (die Signatur) exakt so schreibst wie ich jetzt, andernfalls
definierst du lediglich eine neue Methode, die nichts mit der toString()-Methode
der Klasse Object zu tun hat und dementsprechend vom Java-System auch nicht
aufgerufen wird.

public String toString() {
  String res = "(";
  if (left != null) res = res + left;
  res = res + content;
  if (right != null) res = res + right;
  res = res + ")";
  return res;
}

(Eigentlich sollte man statt der Stringaddition einen StringBuffer verwenden,
aber um dich vorerst nicht zu verwirren, laß ich das mal weg).

Den ganzen Baum gibst du dann mit nur einem einzigen Aufruf von

System.out.println(myTree)

aus.

Falls du den Baum aber doch anders, z.B. zeilenweise, ausgeben willst,
melde dich nochmal.

 

[granini]

Hmm, und wie bringe ich die korrekt in meine Syntax ein.. Ich habe jetzt die Klasse geschrieben und dafür die Methode NodeOutput gecancelt.
Wo bringe ich den String ein bzw wo rufe ich ihn wieder auf??

 

[Leroy42]

Die Methode NodeOutput kannst du doch bestehen lassen.
Sie vereinfacht sich eben zu einem einzigen Aufruf:

   public static void NodeOutput(Tree root){ 
      System.out.println(root==null ? "Iss schon wieder Winter?" : root);
   }

P.S.: Gewöhne dir langsam an, Methodennamen klein zu schreiben: Codestyle

 

[granini]

Hmm, irgendwie selbes Ergebnis..

Ich poste nochmal meinen kompletten Code:

class Tree {
   int  content;
   Tree left;
   Tree right;
}

public class BinTree {
   public static Tree root;

   public static Tree create (int i) {
      Tree build = new Tree();
      build.content = i;
      build.left = null;
      build.right = null;
      return build;
   }
   public static void NodeInclude (Tree root, int newNode){
      
      if (newNode < root.content)
      {
         if (root.left == null){
            root.left = create(newNode);
         }
         else {
            NodeInclude(root.left,newNode);
         }
         
         if (root.right == null){
            root.right = create(newNode);
         }
         else {
            NodeInclude(root.right,newNode);
         }
      }
   }
   
public String toString() {
  String res = "(";
  if (root.left != null) res = res + root.left;
  res = res + root.content;
  if (root.right != null) res = res + root.right;
  res = res + ")";
  return res;
} 

   public static void NodeOutput(Tree root){
      if (root != null){ System.out.println(root);
      }
   }
   
public static void main(String args[]) {
      
   root = create(500);
   NodeInclude(root,444);
   NodeInclude(root,521);
   NodeInclude(root,450);
   NodeInclude(root,857);
   NodeInclude(root,666);
   NodeInclude(root,300);

   NodeOutput(root);
  
      
   } 
}

Ich werde mir angewöhnen Methoden klein zu schreiben.. Versprochen ;-)..

 

[Leroy42]

Die toString()-Methode gehört natürlich in die Klasse Tree, denn du willst ja einen
Tree ausgeben und keine Instanz der Steuerungsklasse BinTree.

Allerdings habe ich noch einen Fehler gemacht also ich auf eine Variable
namens root zugegriffen habe, die es in Tree natürlich nicht gibt.

public String toString() {
  String res = "(";
  if (left != null) res = res + left;
  res = res + content;
  if (right != null) res = res + right;
  res = res + ")";
  return res;
}

Also einfach die Methode so wie sie ist in Tree einfügen und es läuft...

 

[Leroy42]

Ohh, ich sehe gerade, daß ich die Methode ja doch richtig hatte.

Du warst es, der dieses root. eingefügt hast, um die Methode
innerhalb der BinTree-Klasse überhaupt übersetzen zu können, wo es
ja kein left, right und content gibt. :noe:

Pöser Pube! Einfach so an meinen Methoden herumzudoktern :wink:

 

[Leroy42]

Ich hab' dein Programm mal laufen lassen und bin über den etwas merkwürdig
konstruierten Baum gestolpert.

Vielleich hast du es schon bemerkt, aber ein deiner Einfügeroutine
ist dir eine geschlossene geschweifte Klammer irgendwie abhanden
gekommen

 

[granini]

Hmm,

ok ich habe es verstanden, was du meintest.. Nun werden immerhin die nodes ausgespuckt..

Aber

(((300)444(300))500((300)444(300)))

?

Oder habe ich noch was nicht beachtet?


Und wenn ich das so sehe, würde mich die Zeilenvariante auch noch interessieren.. Nur wenn es keine Umstände macht natülrich..

Gruss

 

[Leroy42]

3. Was soll eine rekursive Klasse denn sein?

Ich schätze er gebraucht diese Bezeichnung, wie Niklaus Wirth damals von
rekursiven Datenstrukturen gesprochen hat.

Also Instanzen der Klasse Tree bestehen ja aus einem Content sowie
einem linken und einem Rechten Tree.

Rekursiv eben.

 

[Leroy42]

Nur wenn es keine Umstände macht natürlich..

Latürnich doch

Da du die Zeilenumbrüche nicht in die toString()-Methode integrieren solltest,
ist es am besten zwei Methoden zu spendieren:

public String toString() {return ""+content;}

oder besser:

public String toString() {return String.valueOf(content);}

und als allgemeine Ausgabemethode:

public void print(PrintWriter p) {
  if (left != null) left.print(p);
  p.println(content);
  if (right != null) right.print(p);
}

Aufrufen tust du diese dann außerhalb:

root.print(System.out);

Auf diese Weise kannst du dann später einfach einen PrintWriter
übergeben, der deinen Baum in eine Datei speicher ohne irgend
etwas an der Klasse Tree ändern zu müssen.

 

[Leroy42]

der deinen Baum in eine Datei speichert

:noe:
Wenn schon, dann gleich richtig objektorientiert formulieren/denken.

in dessen zugeordneter Datei sich dein Baum speichert

 

[granini]

Danke dir.. Werde ich gleich mal versuchen umzusetzen..

Aber wieso ist meine Ausgabe noch fehlerhaft? Wenn du bzw jemand mir dazu noch Hilfestellung geben könnte...?

 

[Leroy42]

(((300)444(300))500((300)444(300)))

Wie du siehst, wurde dein Wert 300 gleich 4-mal und die 444 2-mal in
den Baum eingefügt.

Deine verschachtetelten if-Abfragen beim Einfügen sind etwas eigenwillig.

Tipp:

Wenn du etwas links einfügen mußt, fügst du es auch noch gleich
rechts mit ein.

Zum Ausgleich dafür, fügst du, was eigentlich rechts rein müßte,
gleich gar nicht ein. :shock:

Hat zwar was, ist aber auf Dauer irgendwie irritierend.

 

[granini]

Leroy42, ich danke dir für deine Unterstützung...

Da habe ich doch glatt ein "else" vergessen..