Rekursive Berechnung der Höhe eines binären Baumes

Status
Nicht offen für weitere Antworten.

noirpapillon

Neues Mitglied
Hallo allerseits,

bin Neuling hier und im Bereich der Java Programmierung.
Ich habe mich heute mal mit der Implementierung eines binären Baumes versucht.
Das Einfügen von Objekten und Auffinden ist kein Problem nur an der Bestimmung der Höhe
beiße ich mir die Zähne aus :(

Vielleicht könnt ihr mir da weiterhelfen. Anbei eine entwurfene Methode, die wahrscheinlich
von grund auf verkehrt sein wird ... jaja diese Rekursionen :lol:


Code:
public static int getMaximaleHoehe(Knoten n){
		if (n==null) return hoehe;
		
		
		if (n.links!=null) {hoehe++;getMaximaleHoehe(n.links);}
		else if (n.rechts!=null) {hoehe++;getMaximaleHoehe(n.rechts);}
		else
//			return hoehe; ???
		}

Danke für Ratschläge schon im Voraus!

Grüße
Andreas
 

0x7F800000

Top Contributor
äääh, was soll das sein, diese methode da?

also, ich nehme mal an, dass du irgendsoeine struktur haben müsstest:
Code:
public class Node{
   private Collection<Node> childNodes;

   ...

   public int getTreeHeight(){
      if(childNodes.isEmpty){
          //no child nodes, its a leaf and has height of 1
          return 1;
      }else{
          //there are some child nodes/trees. get the maximum height of child trees
          int max=-1, tempHeight;
          for(Node child: childNodes){
             tempHeight=child.getTreeHeight();
             max=(tempHeight>max)?(tempHeight):(max);
          }
          //return the maximum height of child tree +1 (because this node itself also counts)
          return max+1;
      }
   }
}
die idee ist ganz einfach: wenn ein Knoten keine Kinder hat, gibt er 1 zurück, ansonsten sucht er die maximale Baumhöhe der Kinder aus, und gibt diese+1 zurück. Das wars schon.
 
G

Guest

Gast
@Andrey
Binärbäume sind gemeint, nicht irgendwelche verschachtelten Collections.

Code:
private int maxDepth(final int depth, final Node node) {
   return node != null ? Math.max(maxDepth(depth+1, node.left), maxDepth(depth+1, node.right)) : depth;
}

bzw.

private int maxDepth(final int depth, final Node node) {
   if( node != null ) {
      return Math.max( // Der tiefere Zweig zählt
         maxDepth(depth+1, node.left), // Links absteigen
         maxDepth(depth+1, node.right) // Rechts absteigen
      );
   }
   return depth;
}
 
S

SlaterB

Gast
mit dieser Rekursion würde man die ganze Zeit im ersten Node bzw gar in einer Methode außerhalb des Baums bleiben,
vielleicht gerade so gewollt,
aber es ginge auch eine Rekursion von allen Nodes aus, vor allem dann ganz ohne Parameter:

Code:
public int maxDepth() {
  int tiefeLinks = ..; // mit null-Prüfung, maxDepth()-Aufruf links, = 0 oder > 0
  int tiefeRechts = ..; 
   return max(tiefeLinks, tiefeRechts)+1;
}
 

0x7F800000

Top Contributor
Gast hat gesagt.:
@Andrey
Binärbäume sind gemeint, nicht irgendwelche verschachtelten Collections.
und Bäume sind deiner meinung nach was ...?
Wenn du ein Binärbaum willst, dann kannst du natürlich gerne auch statt einer collection zwei explizite referenzen reinbauen, das wird dann weniger allgemein, aber speichersparender und performanenter. Das ist dann genau das was SlaterB angedeutet hat. Aber bei beiden varianten sind irgendwelche statische Funktionen, die irgendwelche integer und referenzen in beide Richtungen weiterreichen und zurückgeben, nicht angebracht.
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
L Rekursive Methode zur Berechnung der Potenz q hoch p Java Basics - Anfänger-Themen 17
T Iterative Pi Berechnung in Rekursive Java Basics - Anfänger-Themen 2
M rekursive Funktion zur Berechnung der Spiegelzahl Java Basics - Anfänger-Themen 7
G Rekursive Berechnung von n über k schlägt fehl Java Basics - Anfänger-Themen 5
T Rekursive Methode Java Basics - Anfänger-Themen 13
emreiu Methoden Rekursive Methoden Runter- & Hochzählen Java Basics - Anfänger-Themen 2
Viktor A. Kaiser Rekursive Algorithmen Java Basics - Anfänger-Themen 9
til237 Iterative Methode in rekursive Methode umschreiben Java Basics - Anfänger-Themen 4
new_to_coding Rekursive Reihe implementieren Java Basics - Anfänger-Themen 1
J Rekursive Funktion und return statement Java Basics - Anfänger-Themen 3
S Rekursive Kombinationen Java Basics - Anfänger-Themen 6
P9cman Tipps für Rekursive Aufgaben mit Strings oder allgemein Java Basics - Anfänger-Themen 2
Csircc Rekursive Methode Stack Overflow Java Basics - Anfänger-Themen 10
schredder Rekursive Quadratzahlen - Ergebnisprozedur Java Basics - Anfänger-Themen 1
A Rekursive Implementation eines Codes Java Basics - Anfänger-Themen 4
L Rekursive Methoden Java Basics - Anfänger-Themen 14
C Rekursive Methode in Interative Methode umwandeln Java Basics - Anfänger-Themen 17
G Rekursive Methode mit 2 Aufrufen Java Basics - Anfänger-Themen 1
J Rekursive Folge (a=a-1) Java Basics - Anfänger-Themen 9
M Rekursive Java-Methode Java Basics - Anfänger-Themen 13
G Rekursive Methode liefert augenscheinlich keinen boolean-Wert zurück. Java Basics - Anfänger-Themen 4
veryck Methoden Rekursive Methoden mit Rückgabeparameter Java Basics - Anfänger-Themen 9
macle Rekursive String Methode, Gerade Zahlen rausfiltern Java Basics - Anfänger-Themen 10
M Rekursive Prüfung ob ein Array sortiert ist... Java Basics - Anfänger-Themen 4
J Rekursive swapArray Methode Java Basics - Anfänger-Themen 69
D Rekursive Methode Java Basics - Anfänger-Themen 8
R Methoden rekursive Methoden Java Basics - Anfänger-Themen 6
O Quersumme rekursive Methode Java Basics - Anfänger-Themen 3
B Treetable (rekursive Funktion) aufbauen von Datenbank Java Basics - Anfänger-Themen 4
M Rekursive Methode Programmieren Java Basics - Anfänger-Themen 3
J rekursive Methode Java Basics - Anfänger-Themen 26
M rekursive division/0 mit exception Java Basics - Anfänger-Themen 18
J Rekursive Methode - Ziffern einer Zahl ausgeben Java Basics - Anfänger-Themen 2
MiMa Rekursive Dateiliste erstellen mit Dateiendung(en) ?? Java Basics - Anfänger-Themen 4
S Rekursive Methode Java Basics - Anfänger-Themen 8
O Rekursive Methode Java Basics - Anfänger-Themen 4
V Methoden Rekursive Methode mit String als Rückgabe Java Basics - Anfänger-Themen 7
K Rekursive Methode Java Basics - Anfänger-Themen 1
K Rekursive Methode für Fakultät mit BigInteger Java Basics - Anfänger-Themen 10
L Rekursive Methode a * b berechnen Java Basics - Anfänger-Themen 2
J Methoden Rekursive Return Methode Java Basics - Anfänger-Themen 2
G Harmonische Rekursive Folge Java Basics - Anfänger-Themen 3
T Stack Overflow - Rekursive Fibonacci Java Basics - Anfänger-Themen 10
B Datentypen Suchbaum - Rekursive Ausgabe Java Basics - Anfänger-Themen 1
P Methoden Rekursive Methode für Potenzen Java Basics - Anfänger-Themen 2
M Methoden Binäre Suche als rekursive Variante Java Basics - Anfänger-Themen 5
B Rekursive Algorithmus schreiben Java Basics - Anfänger-Themen 8
S Eine rekursive Lösung Java Basics - Anfänger-Themen 4
S Int zu Hexadezimal - Rekursive Methode Java Basics - Anfänger-Themen 2
M Rekursive Suche in einem Feld Java Basics - Anfänger-Themen 11
N Rekursive Addition mit Scanner Java Basics - Anfänger-Themen 12
shiroX OOP Rekursive und Iterative Definition Java Basics - Anfänger-Themen 2
B Methoden Rekursive Methoden Java Basics - Anfänger-Themen 2
C rekursive methode Java Basics - Anfänger-Themen 2
D Methoden Rekursive Methoden Java Basics - Anfänger-Themen 13
R rekursive Methode funktioniert nicht Java Basics - Anfänger-Themen 4
M Stürzen alle Rekursive Methoden irgendwann ab? Java Basics - Anfänger-Themen 11
D Primzahlen und Rekursive Liste Java Basics - Anfänger-Themen 29
R Rekursive Methode, Files finden Java Basics - Anfänger-Themen 2
S rekursive folge verbessern Java Basics - Anfänger-Themen 2
C rekursive Methode verstehe nicht! Java Basics - Anfänger-Themen 3
S Methoden rekursive Methode funktioniert nicht Java Basics - Anfänger-Themen 4
E Rekursive Methode Java Basics - Anfänger-Themen 3
N Methoden Rekursive Fibonaccizahlen mit Array Java Basics - Anfänger-Themen 2
R Rekursive Ausgabe eines Binärbaums Java Basics - Anfänger-Themen 4
J Methoden Rekursive Potenz ohne Math.Pow() Java Basics - Anfänger-Themen 9
A Rekursive Methode in Iterative umwandeln Java Basics - Anfänger-Themen 6
S Labyrith Rekursive Wegsuche Java Basics - Anfänger-Themen 4
C Rekursive Methode - Ziffern in Zahl Java Basics - Anfänger-Themen 33
U Dezimal zu Hexadezimal rekursive Funktion Java Basics - Anfänger-Themen 8
L iterative und rekursive Folge Java Basics - Anfänger-Themen 20
G Rekursive Methode Java Basics - Anfänger-Themen 3
A rekursive Listen in Java? Java Basics - Anfänger-Themen 5
B OOP Einfach verkettete Liste - rekursive Methoden Java Basics - Anfänger-Themen 1
E Rekursive Methode mit Zufallsarray Java Basics - Anfänger-Themen 6
E Rekursive Methode Java Basics - Anfänger-Themen 18
U Rekursive lösung von pascal dreieck Java Basics - Anfänger-Themen 11
M Rekursive Methode - wo ist der Fehler? Java Basics - Anfänger-Themen 4
J rekursive methode Java Basics - Anfänger-Themen 6
H ScrollBar inaktiv / Rekursive Methode Java Basics - Anfänger-Themen 4
J Rekursive Methode Java Basics - Anfänger-Themen 11
G Rekursive Methode Java Basics - Anfänger-Themen 5
K Rekursive Methoden Java Basics - Anfänger-Themen 15
K Rekursive Funktion (Verständnissfrage) Java Basics - Anfänger-Themen 5
S Rekursive Bruch potenzierung Java Basics - Anfänger-Themen 2
D rekursive Summenberechnung Java Basics - Anfänger-Themen 8
J Rekursive Methode: Fakultaet berechnen Java Basics - Anfänger-Themen 5
E Rekursive definierten Folge Java Basics - Anfänger-Themen 10
A HILFE! Rekursive Funktion Java Basics - Anfänger-Themen 20
kulturfenster rekursive Binaere Suche Java Basics - Anfänger-Themen 12
F Rekursive Aufrufe, Parameterübergabe, call by reference Java Basics - Anfänger-Themen 3
B Rekursive & schreiben im ArrayList Java Basics - Anfänger-Themen 2
J Rekursive Fkt. Java Basics - Anfänger-Themen 2
A Rekursive Dateisuche Java Basics - Anfänger-Themen 12
K rekursive Funktion mit mehreren Parametern Java Basics - Anfänger-Themen 5
G rekursive Methode Java Basics - Anfänger-Themen 3
N rekursive Beispiele Java Basics - Anfänger-Themen 3
G rekursive u iterative Methode Java Basics - Anfänger-Themen 8
G Rekursive Methode Java Basics - Anfänger-Themen 7
ven000m Rekursive Funktionen - Frage Java Basics - Anfänger-Themen 16

Ähnliche Java Themen

Neue Themen


Oben