Rekursive Berechnung der Höhe eines binären Baumes

[noirpapillon]

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:

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]

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

also, ich nehme mal an, dass du irgendsoeine struktur haben müsstest:

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.

 

[Guest]

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

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;
}

 

[SlaterB]

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:

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

 

[0x7F800000]

@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.