# einen binärbaum implementieren



## paco89 (4. Dez 2011)

hallo,


ich versuche gerade einen binärbaum zu implementieren und habe mir dazu zwei methoden aus einem buch abgetippt, um überhaupt zu sehen wie diese funktionieren. ich habe diese 2 codeabschnitte aus einem buch und werde mal versuchen diese mit meinen eigenen worten zu erklären, damit ich sehen kann ob ich das überhaupt verstanden habe. also:



```
class Knoten 
{ int Zahl ;
  Knoten links , rechts;

  Knoten ( int Zahl )

  { 
    this. Zahl = Zahl; 
    links = rechts = null;
  }
}
```


```
class Baum 
{
   Knoten Wurzel;
   
   Baum()
   {
      Wurzel = null;
   }
   
   Knoten suche(int Zahl)
   {
      return suche(Zahl, Wurzel);
   }
   
   Knoten suche(int Zahl, Knoten k)
   {
      if (k==null)
        return null;
      
      else if(k.Zahl == Zahl)
        return k;
        
      else
      {
        Knoten s = suche (Zahl, k.links);
        if (s!=null) return s;
        else         return suche (Zahl, k.rechts);
      }
   }
   
   void erzeuge_Blatt(int Zahl)
   {
      Wurzel = erzeuge_Blatt(Zahl, Wurzel);
   }

    Knoten erzeuge_Blatt(int Zahl, Knoten k)
    {
      if(k==null)
      
        return new Knoten(Zahl);
      
      else if (Zahl < k.Zahl)
      {
        k.links = erzeuge_Blatt(Zahl, k.links); 
          return k;
      }
      
      else 
      {
        k.rechts = erzeuge_Blatt(Zahl, k.rechts);
          return k;
      }
    }


}
```



also :
in der klasse knoten gibt es die variablen Zahl vom typ int, und die beiden variablen links und rechts vom typ knoten. zudem gibt es noch einen konstruktor, der die gewünschte zahl an die obige variable zahl übergibt.
wenn man sich das ganze bildlich vorstellt, dann mus man quasi an ein objekt denken, der einen wert speichern kann und dessen beide variablen rechts und links auf ein anderes zeigt.

in der klasse baum gibt es eine variable wurzel vom typ knoten und einen konstruktor baum, der dafür sorgt, dass die wurzel auf null zeigt.

nun zu den methoden:
wenn die methoden void erzeuge_Blatt(int Zahl) aufgerufen wird, sagen wir mal in der main-methode schreibt jmd. Baum B = new Baum() und anschließend B.erzeuge_Blatt(6); 
so geschieht doch folgendes:
zunächst ruft die methode erzeuge_Blatt(int Zahl) die andere rekursive methode Knoten erzeuge_Blatt(int Zahl, Knoten k) auf. danach zeigt knoten k auf die Wurzel, da Wurzel als aktueller parameter an Knoten k übergeben wird. 
so jetzt die fallunterscheidungen: zeigt k auch auf null, so wird ein objekt vom typ knoten erzeugt mit der gewünschten zahl.
ist die eingebene zahl kleiner als k, also kleiner als das bearbeitete listenelement, so wird die methode erzeuge_Blatt wieder aufgerufen....

...und das danach passiert, versteh ich gar nicht mehr. die andere methode suche habe ich erst gar nicht verstanden....bitte daher um ausführliche erklärungen....


----------



## Marcinek (4. Dez 2011)

Maybe hilft das:

Binärbaum ? Wikipedia


----------



## paco89 (4. Dez 2011)

ja, danke. aber das habe ich mir schon durchgelesen. komme aber nicht weit. der grund warum ich das gepostet ist, dass ich die methode nicht auswendig lernen will, weil das sowieso nichts bringt. in dem buch was ich habe, werden die methoden, die in dem code auftauchen, kaum erklärt. 
da ich ein anfänger bin, würde ich schon vertstehen wollen, was diese fallunterscheidungen in den geschweiften klammern de rekursiven methoden zu bedeuten haben.

ich lese mir gerade den abschnitt "Rekursion" nochmal durch....in der hoffnung ich check das doch noch....trotzdem danke für deinen beitrag


----------



## Marcinek (4. Dez 2011)

Linker Zweig runtergehen oder rechter Zweig runter gehen.


----------



## Dekker (4. Dez 2011)

Der erste Schritt um etwas zu programmieren ist immer erst mal verstanden zu haben was man programmieren möchte. Du hast offensichtlich noch Probleme mit dem Binärbaum selbt (zumindest lese ich das so aus deinem Post heraus?), ergo solltest du dir keine Codebeispiele suchen sondern erstmal die Theorie des Baumes verstehen. Dann wäre dir auch klarer warum das IF darüber entscheidet, wo eingefügt wird.


----------

