# Frage zur einfügen in einem Binärbaum



## gustav-mega (11. Feb 2005)

Hallo,

ich habe das folgende Code:


```
class MMenge<T extends Comparable> 
{
  Node root = null;

  class Node<T extends Comparable>
  {
    T value;
    int indx = 1;
    Node left, right;

    public Node(T v)
    {
      value = v;
    }
  }

  void insert(T[] val)
  {
    boolean hilfe = true;
    for (int i = 0; i < val.length; i++)
    {
      if (root == null) 
      {
        root = new Node<T> (val[i]);
        return;
      }

      Node parent = null, child = root;

      while (child != null) 
      {
        parent = child;

        if (child.value.compareTo(val[i]) == 0) 
        {
          parent.indx += 1;
          hilfe = false;
          return;
        }

        if (child.value.compareTo(val[i]) < 0)
          child = child.left;
        else
          child = child.right;
      }

      if (parent.value.compareTo(val[i]) == 0 && hilfe) 
      {
        child.indx += 1;
        return;
      }

      if (parent.value.compareTo(val[i]) < 0 && hilfe)
        parent.left = new Node<T>(val[i]);

      else
        parent.right = new Node<T>(val[i]);
    }
  }
  
  int anzahl(MMenge<T> baum, T wert)
  {
    int ergebniss = -1;
    Node parent = root;
    while(parent != null)
    {
      if(parent.value.compareTo(wert) == 0)
      {
        ergebniss = parent.indx;
        return ergebniss;
      }
      if(parent.value.compareTo(wert) < 0)
        parent = parent.left;
      else
        parent = parent.right;
    }
    return ergebniss;
  }
  
  public static void main(String[] args)
  {
    MMenge<String> test = new MMenge<String>();
    String[] hallo = {"a","a","a","v","d","f","r"};
    test.insert(hallo);
    MMenge<String> test2 = new MMenge<String>();
    test2 = test;
    System.out.println(test.anzahl(test2, "a"));
  }
}
```
kann jemend vielleicht sagen, warum 1 als Ergebnis geliefert wird?

Gruß,
G.M.


----------



## bambi (11. Feb 2005)

Wo initialisierst Du denn root? Kann es evt. sein, dass root = null ist?


----------



## gustav-mega (11. Feb 2005)

in der Zeile 3.


----------



## bambi (11. Feb 2005)

initialisieren = wert zuweisen

sowas wie root = "irgendeinWert" // wobei "irgendeinWert" != null


----------



## gustav-mega (11. Feb 2005)

das mache ich doch in der Zeile 22 -26


----------



## bambi (11. Feb 2005)

also ich denke mal, dass root in deiner methode null ist und dass dann natuerlich auch parent = null ist, da du deine insert-methode ja gar nicht aufrufst, oder lieg' ich da jetzt falsch?

check einfach mal root, bevor du die zuweisung machst. wenns nicht null ist, dann sag' bescheid - ich schau dann noch mal genauer rein, okay?

und immer schoen  :lol:  okay?!?


----------



## gustav-mega (11. Feb 2005)

ich habe gerade mit dem Befehl getestet:

```
System.out.println(test.root != null);
```

und bekomme true, daher root kann nicht null sein!


----------



## Beni (11. Feb 2005)

Nur mal eine Frage: wie hast du das kompiliert? Eclipse streicht da viel rot an...

Das ist doch ein ideales Stück Code um einen Debugger auszuprobieren.
Nur so als Tipp: das Problem wird durch Zeile 25 verursacht :wink:


----------



## gustav-mega (11. Feb 2005)

Du must JDK 1.5 installiert haben, und ich habe es über Konsole kompiliert. Ich habe den Code jetzt soweit geändert:

```
class MMenge<T extends Comparable>
{
  Node root = null;

  class Node<T extends Comparable>
  {
    T value;
    int indx = 1;
    Node left, right;

    public Node(T v)
    {
      value = v;
    }
  }

  void insert(T[] val)
  {
    T element;
    for (int i = 0; i < val.length; i++)
    {
      element = val[i];
      
      Node parent = null, child = root;

      while (child != null)
      {
        parent = child;

        if (element.compareTo(child.value) == 0)
          child.indx += 1;

        if (element.compareTo(child.value) < 0)
          child = child.left;
        else
          child = child.right;
      }
      
      if (parent == null)
        root = new Node<T> (element);
      else
      {
        if (element.compareTo(parent.value) == 0)
          parent.indx += 1;
        
        if (element.compareTo(parent.value) < 0)
          parent.left = new Node<T>(element);

        else
          parent.right = new Node<T>(element);
      }
    }
  }

  int anzahl(MMenge<T> baum, T wert)
  {
    int ergebniss = -1;
    Node parent = root;
    while(parent != null)
    {
      if(parent.value.compareTo(wert) == 0)
      {
        ergebniss = parent.indx;
        //return ergebniss;
      }
      if(parent.value.compareTo(wert) < 0)
        parent = parent.left;
      else
        parent = parent.right;
    }
    return ergebniss;
  }

  public static void main(String[] args)
  {
    MMenge<String> test = new MMenge<String>();
    String[] hallo = {"a","a","a","a","v","d","f","r","a"};
    test.insert(hallo);
    MMenge<String> test2 = new MMenge<String>();
    test2 = test;
    System.out.println(test.root.right.right.value);
    System.out.println(test.anzahl(test, "f"));
  }
}
```


----------



## Beni (11. Feb 2005)

gustav-mega hat gesagt.:
			
		

> Du must JDK 1.5 installiert haben...


Das ist ja schon fast eine Beleidigung, natürlich hab ich Java 1.5 auf meinem Rechner, schon seit den ersten Betas  :!:  :wink: 

Zeile 24 und Zeile 58: mach aus den "Node" "Node<T>", sonst geht die Typsicherheit flöten (darum reklamierte auch mein liebes Eclipselein, du müsstest eigentlich ein paar Warnungen haben?).

Bin mir jetzt nicht ganz sicher, aber suchst du sowas? (Achtung: ich hab da zweimal "f" eingegeben, deshalb die Ausgabe 2)

```
class MMenge<T extends Comparable> {
	Node root = null;

	class Node<T extends Comparable> {
		T value;

		int indx = 1;

		Node left, right;

		public Node(T v){
			value = v;
		}
	}

	void insert( T[] val ) {
		for( T t : val )
			insert( t );
	}

	void insert( T element ) {
		Node<T> parent = null, child = root;

		if( root == null ){
			root = new Node<T>( element );
			return;
		}
		
		while( true ){
			parent = child;

			if( element.compareTo( child.value ) == 0 ){
				child.indx += 1;
				return;
			}

			if( element.compareTo( child.value ) < 0 ){
				child = parent.left;
				if( child == null ){
					parent.left = new Node<T>( element );
					return;
				}
			}
			else{
				child = parent.right;
				if( child == null ){
					parent.right = new Node<T>( element );
					return;
				}
			}
		}

	}

	int anzahl( T wert ) {
		Node<T> parent = root;
		while( parent != null ){
			if( parent.value.compareTo( wert ) == 0 ){
				return parent.indx;
			}
			if( parent.value.compareTo( wert ) > 0 )
				parent = parent.left;
			else
				parent = parent.right;
		}
		return 0;
	}

	public static <T extends Comparable> void print( int tab, Node<T> node ) {
		printTabs( tab );
		if( node == null )
			System.out.println( "-" );
		else{
			System.out.println( node.indx + " / " + node.value );
			print( tab + 1, node.left );
			print( tab + 1, node.right );
		}

	}

	public static void printTabs( int tabs ) {
		for( int i = 0; i < tabs; i++ )
			System.out.print( " " );
	}

	public static void main( String[] args ) {
		MMenge<String> test = new MMenge<String>();
		String[] hallo = { "a", "a", "a", "a", "v", "d", "f", "r", "f", "a" };
		test.insert( hallo );
		MMenge<String> test2 = new MMenge<String>();
		test2 = test;
		print( 0, test.root );
//		System.out.println( test.root.right.right.value );
		System.out.println( test.anzahl( "f" ) );
	}
}
```


----------



## gustav-mega (11. Feb 2005)

genau das wollte ich auch machen :toll: , was habe ich denn eigentlich falsche gemacht gehabt   ?


----------



## Beni (11. Feb 2005)

Du hattest keine richtigen Abbruchbedingungen in deiner Schleife (in "insert"). Wenn du ein Element gefunden hattest, wurde zwar der Knoten markiert, aber dann ging es munter weiter (was immer zu einem neuen Knoten führt).

Ich hab jetzt einfach deine "insert"-Methode in zwei verschiedene Methoden aufgeteilt, und springe mit "return" aus der zweiten Methode raus, sobald ein Werte gefunden wird.

Das zweite ist diese "anzahl" Methode: das Argument "MMenge<T> baum" ist unnötig, du suchst ja nicht "baum" ab, sondern das Objekt, von dem du "anzahl" aufgerufen hast.


----------



## gustav-mega (11. Feb 2005)

erstmal Vielen, Vielen, Vielen Dank   , und übrigens mit JDK 1.5 war nicht böse gemeint :wink: . Jetzt noch eine Frage: wenn ich eine while-Schleife in einer for-Schleife habe wie kann ich aus der while-Schleife rausspringen ohne, daß ich aus der for-Schleife rausgesprungen werde?


----------



## Beni (11. Feb 2005)

Das geht mit "break":


```
for(...){
  while(...){
    break; // beendet das while
  }
}
```

Du kannst auch ein Label verwenden (dann wirds übersichtlicher).


```
for(...){
  loop: while(...){
    break loop;  // beendet die mit "loop" markierte Schleife
  }
}
```


----------



## Illuvatar (11. Feb 2005)

So könntest du übrigens natürlich auch aus der äußeren Schleife springen:

```
loop: for(...){ 
  while(...){ 
    break loop;  // beendet die mit "loop" markierte Schleife 
  } 
}
```


----------



## bambi (11. Feb 2005)

kleine zwischenfrage:
ich hab' mal gelernt, dass labels "nicht so toller" programmierstil waeren - hat sich das jetzt mit java 1.5 geaendert? also bei c++ - ich weiss, das hier ist java - war's nicht so gut...


----------



## Illuvatar (11. Feb 2005)

Hm goto is schlechter Programmierstil, break und continue (auch mit labels) is imo v.a. nützlich.


----------



## gustav-mega (11. Feb 2005)

nur daß ich es auch richtig verstehe, mit return springe ich ganz aus aus alle Schleifen und der Methode raus, mit break aus der aktuelle Schleife und mit continue setzt sich die Schleife beim nächsten Schritt einfach fort, richtig?


----------



## Beni (11. Feb 2005)

Da hast du schon recht bambi. Theoretisch sollte man auch nur ein "return" pro Methode haben, und break (ah, es gibt auch noch continue  ) gar nicht benutzen, sondern alles mit if's lösen.
Das führt dann zu Code, der nicht "wild in der Gegend rumspringt".
Naja, und das gibt dann x ineinandergeschachtelte Klammern, ich finde die Lösung auch nicht gerade "so dolle".

Was wirklich schlecht ist, ist das goto. Da kann man wirklich Verwirrung stiften.

edit:
@gustav-mega
Jop, richtig verstanden


----------



## gustav-mega (11. Feb 2005)

was hätte ich ohne euch gemacht   . Nochmal  :toll: VIELEN DANK  :toll: 

Gruß,
G.M.


----------



## bambi (11. Feb 2005)

wie jetzt? kein break? das ist schlechter stil? einiges kann man doch gar nicht ohne break, oder?


@gustav-mega
zu break und continue kannst du dir mal 
http://www.galileocomputing.de/open...el_02_005.htm#Rxx365java02005040000A51F03221F
ansehen. das hilft sicher


----------



## Illuvatar (11. Feb 2005)

mit if/else und nem boolean ob er abbrechen soll z.B. gehts immer auch. Aber da wirds um einiges unübersichtlicher als nen kleines feines break irgendwo, find ich.

Edit: Is halt bissle wie goto, auch das kann man hin und wieder sinnvoll und mit gutem Programmierstil eingesetzt werden. Da das aber 0,1% der Leute so machen wurde es gleich weggelassen


----------

