# Tiefe im binären Suchbaum



## newbie2009 (1. Jun 2010)

Hey ich habe einen binären Suchbaum, und wollte gerne die Tiefe bestimmen.
Habe mir überlegt jeweils den linken Ast zu durchlaufen und dann den rechten ,  und dann beide zu vergleichen und den größeren zu nehmen.

habe nun die folgende methode im internet gefunden:


```
int depth (Datum akt){
	  int tl, tr;
	  if (akt == null){ 
		  return (0);}
	    else{
	 
	  tl=depth(akt.getLinks());
	  tr=depth (akt.getRechts());
	  
	  if (tl > tr ) {
		  return (tl + 1);}
	  
	  else return (tr + 1);
	  }
	  
	  
	  
	  }
```
Ich verstehe aber eins nicht, am Anfang sind ja tl, tr noch garnicht initialisiert.
Daher finde ich den rekursiven Aufruf etwas seltsam.Könnte es jemand vll dumme ma erklären?


----------



## seakey (1. Jun 2010)

```
tl=depth(akt.getLinks());
tr=depth (akt.getRechts());
```

tl bzw. tr wird der Wert von 
	
	
	
	





```
depth(akt.getLinks());
```
 bzw. von 
	
	
	
	





```
depth(akt.getRechts());
```
 zugewiesen. Da das ein rekursiver Aufruf der Methode ist, wird diese Rekursion solange ausgeführt, bis akt == null ist. Dann erhält tl bzw. tr den Wert 0, wegen


```
if (akt == null){ 
          return (0);}
```

Entsprechend der Abfrage


```
if (tl > tr ) {
          return (tl + 1);}
      
      else return (tr + 1);
      }
```

werden diese Werte im Verlauf der Rekursion erhöht. 

Hoffe, es war einigermaßen verständlich


----------



## newbie2009 (1. Jun 2010)

```
tr=depth(akt.getLinks());
```
Ich verstehe aber nicht, denn get.Links() liefert ja nur die Referenz auf den nächsten Knoten, sprich es wird garnicht der Wert ausgelesen(ist ja auch nicht der sinn). Aber warum kann dann 
	
	
	
	





```
tr
```
 damit ein neuer wert zugewiesen, und wenn ja dann welcher, das verstehe ich nich so ganz.


----------



## Marco13 (1. Jun 2010)

newbie2009 hat gesagt.:


> sprich es wird garnicht der Wert ausgelesen(ist ja auch nicht der sinn).



Welchen Wert meinst du denn? Die höhe eines Binärbaumes ist
1 + die Höhe des höheren der beiden Kinder

Und das steht auch da... man kann das unterschiedlich "übersichtlich" schreiben ... z.B. so

```
public static int depth(Datum akt)
    {
        if (akt == null)
        {
            return 0;
        }

        int höheVomLinken = depth(akt.getLinks());
        int höheVomRechten = depth(akt.getRechts());
        int größereHöhe = 0;
        if (höheVomRechten > höheVomLinken)
        {
            größereHöhe = höheVomRechten;
        }
        else
        {
            größereHöhe = höheVomLinken;
        }
        return 1+größereHöhe;
    }
```
oder so 

```
public static int depth(Datum a)
    {
        return a==null?0:1+Math.max(depth(a.getLinks()),depth(a.getRechts()));
    }
```


----------



## newbie2009 (2. Jun 2010)

ja ok vielen dank 

ist schon bisschen verständlicher nur mir ist nicht ganz klar, was zum Beispiel hier für ein Integerwert geliefert wird.

```
int höheVomLinken = depth(akt.getLinks());
```

oder wird hier etwa dann jedes mal wenn 
	
	
	
	





```
(akt.getLinks()!=null)
```
 eine 1+0 dazugezählt.Die Rekursion verwirrt mich ein wenig an dieser Stelle.


----------



## Landei (2. Jun 2010)

depth akteptiert sowohl "volle" Knoten wie auch null. Wenn du eine null-Referenz übergibts, bekommst du - Überraschung! - eine Höhe von 0 zurück. Ansonsten rekursiert (und addiert) er halt weiter "in die Tiefe des Raums" hinein.

Um Rekursion zu verstehen, muss man erst einmal Rekursion verstehen... Nein, mal im Ernst: Um eine rekursive Funktion zu verstehen, geht man sie am besten wie eine normale Funktion durch und _setzt voraus_, dass die rekursiven Aufrufe darin "einfach das richtige" tun. Wenn du versuchst, den Aufrufen zu folgen, gibt es einen unlösbaren Hirnknoten.

Du denkst also: depth soll die Tiefe zurückliefern, wie macht es das? Erst prüft es, ob der Knoten null, also leer ist. Ein leerer Knoten hat die Höhe 0. Falls der Knoten nicht leer ist, müssen wir erst einmal die Höhe der Kindknoten kennen. Hach, wir haben ja die depth-Funktion, die genau das berechnet. Die rufen wir auf, wird schon gutgehen. Dann schauen wir, welches Kind die größere Höhe hat und zählen eins dazu. Fertig.


----------



## newbie2009 (2. Jun 2010)

Landei danke für die Beschreibung, aber dass eine rekursion ein Selbstaufruf der Methode ist, war mir glaub ich schon klar.
Nur mir fehlt irgendeine Anweisung in der Art 
	
	
	
	





```
int a=0;
if(knoten!null){
a++;}
```

Das verwirrt mich .


----------



## Marco13 (2. Jun 2010)

Hm. Das ist so dieser funktionale Gedanke, der hinter der Rekursion steckt. Wie Landei schon sagte: Man muss einfach darauf vertrauen, dass die Funktion das richtige tut.

Man könnte die Funktion auch so schreiben

```
public static int höheDesHöherenKindknotensVon(Datum akt)
    {
        int höheVomLinken = depth(akt.getLinks());
        int höheVomRechten = depth(akt.getRechts());
        int größereHöhe = 0;
        if (höheVomRechten > höheVomLinken)
        {
            größereHöhe = höheVomRechten;
        }
        else
        {
            größereHöhe = höheVomLinken;
        }
        return größereHöhe;
    }

    public static int depth(Datum akt)
    {
        if (akt == null)
        {
            return 0;
        }
        return 1+höheDesHöherenKindknotensVon(akt);
    }
```

Dann steht in der "depth"-Methode wirklich nur noch diese Definition. Man braucht da keine Variablen zu erhöhen oder so, man ruft die Funktion auf, und ihr Rückgabewert wird verwendet.


----------



## newbie2009 (4. Jun 2010)

Marco13 hat gesagt.:


> Hm. Das ist so dieser funktionale Gedanke, der hinter der Rekursion steckt. Wie Landei schon sagte: Man muss einfach darauf vertrauen, dass die Funktion das richtige tut.
> 
> Man könnte die Funktion auch so schreiben
> 
> ...



hehe danke das wollte ich wissen  also wird immer mindestens die 1 geliefert   wenn man es so aufschreibt sieht es für mich logischer aus, davor war ich mir nicht über den Rückgabewert bewusst.


----------



## Landei (4. Jun 2010)

Ich habe den Thread mal als Anlass genommen, allgemein über Rekursion zu schrieben:
http://www.java-forum.org/blogs/landei/124-rekursion-verstehen.html


----------

