Tiefe im binären Suchbaum

newbie2009

Bekanntes Mitglied
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:

Java:
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?:D
 

seakey

Mitglied
Java:
tl=depth(akt.getLinks());
tr=depth (akt.getRechts());

tl bzw. tr wird der Wert von
Code:
depth(akt.getLinks());
bzw. von
Code:
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

Java:
if (akt == null){ 
          return (0);}

Entsprechend der Abfrage

Java:
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

Bekanntes Mitglied
Java:
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
Java:
tr
damit ein neuer wert zugewiesen, und wenn ja dann welcher, das verstehe ich nich so ganz.
 

Marco13

Top Contributor
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
Java:
    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 :cool:
Java:
    public static int depth(Datum a)
    {
        return a==null?0:1+Math.max(depth(a.getLinks()),depth(a.getRechts()));
    }
 

newbie2009

Bekanntes Mitglied
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.
Java:
 int höheVomLinken = depth(akt.getLinks());

oder wird hier etwa dann jedes mal wenn
Java:
(akt.getLinks()!=null)
eine 1+0 dazugezählt.Die Rekursion verwirrt mich ein wenig an dieser Stelle.
 

Landei

Top Contributor
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.
 
Zuletzt bearbeitet:

newbie2009

Bekanntes Mitglied
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
Java:
int a=0;
if(knoten!null){
a++;}

Das verwirrt mich .
 

Marco13

Top Contributor
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
Java:
    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

Bekanntes Mitglied
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
Java:
    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.

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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
T Rekursiv Tiefe eines binären Suchbaums ermitteln Java Basics - Anfänger-Themen 22
L Tiefe Kopie einer Zeile eines zweidimensionalen Arrays Java Basics - Anfänger-Themen 1
X Kopierkonstruktor / tiefe Kopie Java Basics - Anfänger-Themen 3
V Tiefe Kopie Java Basics - Anfänger-Themen 3
K Rot-Schwarz-Baum min und max-Tiefe Java Basics - Anfänger-Themen 1
Helgon Baumstruktur tiefe N erzeugen Java Basics - Anfänger-Themen 3
S Klassen Tiefe Kopie mittels Kopierkonstruktor Java Basics - Anfänger-Themen 6
B Mehrdimensionales Array + Tiefe Java Basics - Anfänger-Themen 4
? clonen -tiefe Kopie Java Basics - Anfänger-Themen 6
K Tiefe im Binärbaum Java Basics - Anfänger-Themen 2
M Binärer Baum Tiefe Java Basics - Anfänger-Themen 14
I Methoden aufrufe in die Tiefe Java Basics - Anfänger-Themen 5
F Tiefe eines Baumes Java Basics - Anfänger-Themen 6
L Binären Bäume für beliebige Datentypen Java Basics - Anfänger-Themen 15
M Binären Baum Kinder setzen Java Basics - Anfänger-Themen 12
U Input/Output Elemente eines Binären Suchbaums ausgeben Java Basics - Anfänger-Themen 10
C Methoden Methode zu einem Binären Suchbaum Java Basics - Anfänger-Themen 8
L Indorder Traversierung eines binären Suchbaumes Java Basics - Anfänger-Themen 1
T Algorithmus zur Überprüfung eines binären Suchbaums Java Basics - Anfänger-Themen 2
N Binären Suchbaum erstellen, nachzuvollziehen Java Basics - Anfänger-Themen 0
W binären Suchbaum Kantenanzahl Java Basics - Anfänger-Themen 3
K Datentypen Umwandlung einer Textfeldeingabe in einen binären Wert Java Basics - Anfänger-Themen 2
J Ebene eines binären Baumes Java Basics - Anfänger-Themen 3
A OOP Binären Datenstrom in Datei schreiben Java Basics - Anfänger-Themen 4
E Alternativen zur binären Serialisierung ? Java Basics - Anfänger-Themen 9
N Rekursive Berechnung der Höhe eines binären Baumes Java Basics - Anfänger-Themen 4
G Pfadlänge eines binären Suchbaums Java Basics - Anfänger-Themen 4
H Tiefensuche im binären Baum Java Basics - Anfänger-Themen 2
G suchen und ersetzen in einer binären Datei Java Basics - Anfänger-Themen 4
H Löschen in einem binären Baum führt zu einem StackOverflow Java Basics - Anfänger-Themen 2
L Binären Baum speichern Java Basics - Anfänger-Themen 6
J String in binären Baum umwandeln Java Basics - Anfänger-Themen 7
Cassy3 Binärer Suchbaum Knoten rauslöschen Java Basics - Anfänger-Themen 1
G Java Binärer Suchbaum Java Basics - Anfänger-Themen 1
G Binärer Suchbaum Knoten zählen Java Basics - Anfänger-Themen 1
O Suchbaum Elternknoten finden Level eines Knoten bestimmen Java Basics - Anfänger-Themen 24
L Binärer Suchbaum Java Basics - Anfänger-Themen 2
N ID3 - Suchbaum ertellen! Java Basics - Anfänger-Themen 0
M Suchbaum implementieren Java Basics - Anfänger-Themen 8
J Suchbaum Java Basics - Anfänger-Themen 3
B Datentypen Suchbaum - Rekursive Ausgabe Java Basics - Anfänger-Themen 1
U Binärer Suchbaum delete Java Basics - Anfänger-Themen 1
S Binärer Suchbaum - Size als Variabel in innerer Klasse speichern Java Basics - Anfänger-Themen 2
G Rekursion Suchbaum Java Basics - Anfänger-Themen 2
W Löschen Datenknoten Suchbaum Java Basics - Anfänger-Themen 4
H Suchbaum iterativ absteigen? Java Basics - Anfänger-Themen 3
E binärer suchbaum Java Basics - Anfänger-Themen 8
K Binärer Suchbaum Java Basics - Anfänger-Themen 3
D Binärer Suchbaum Java Basics - Anfänger-Themen 11
Q Binärer suchbaum Java Basics - Anfänger-Themen 2
I Rekursives Löschen in Binärem Suchbaum Java Basics - Anfänger-Themen 2
Y Binärer Suchbaum Java Basics - Anfänger-Themen 5
A Suchbaum Java Basics - Anfänger-Themen 4
DasDogma Suche im Suchbaum Java Basics - Anfänger-Themen 2
D suchbaum out of heap space Java Basics - Anfänger-Themen 8
M Binärer Suchbaum Höhe Java Basics - Anfänger-Themen 6
G Hoffe jemand kann mir ein paar Tips geben:binärer Suchbaum Java Basics - Anfänger-Themen 3
G Binäre Suchbaum + Erstellung des Programmes Java Basics - Anfänger-Themen 4
E Binärer Suchbaum Java Basics - Anfänger-Themen 7
Bierhumpen Suchbaum problem. Java Basics - Anfänger-Themen 8
R binärer Suchbaum Java Basics - Anfänger-Themen 1

Ähnliche Java Themen

Neue Themen


Oben