# Binärbaum höhe herausfinden



## babuschka (9. Jun 2011)

Hi zusammen,
habe folgendes Problem:

Die Methode soll die Höhe des Binärbaums zurück geben. 
Habe einen Lösungsansatz.Allerdings glaube ich, dass es wesentlicher einfacher und schicker geht.

Habt ihr eine Idee?


```
public class TreeN {
	
	private TreeN links, rechts;
	
	TreeN(TreeN links, TreeN rechts){
		this.links = left;
		this.rechts = right;
	}
	
	public int getHoehe(TreeN t){
                TreeN hilfe = t;
		int hoehe;
		int a = 0;
		int b = 0;
		
		if(t==null){
			return -1;
		}else{
			while (hilfe.left != null){
				a++;
			}
			while (hilfe.right != null){
				b++;
				
			}
			
			hoehe = Math.max(a,b);
		}
		return hoehe;


}
```


----------



## SlaterB (9. Jun 2011)

bevor es ans 'besser' geht, wie wärs damit, deinen Code überhaupt als korrekt zu zu bestimmen, überhaupt einmal zu testen?!
kann mir nicht vorstellen dass du den hast laufen lassen,


```
while (hilfe.left != null){
                a++;
            }
```
was passiert wenn hilfe.left tatsächlich mal != null ist? a wird erhöht und dann kommt die Schleifenbedingung erneut dran, 
was passiert jetzt? und danach? und danach? und danach? und danach?...


----------



## babuschka (9. Jun 2011)

DAS ist ja mein Problem...Es läuft nicht...Hab mich vielleicht falsch ausgedrückt.


----------



## Rosa (9. Jun 2011)

greenbird hat gesagt.:


> DAS ist ja mein Problem...Es läuft nicht...Hab mich vielleicht falsch ausgedrückt.



Ich glaube, Du musst erstmal dafür sorgen das bei jedem Listenelement, was Du in die Liste hängst,  Links und Rechts auch NULL ist. Also:
public void insertElement(TreeN elem){
  elem.Links=null;
  elem.Rechts=null;
  // add to tree
  // ...
}

aber so, wie ich den Code verstehe, arbeitest Du mit Links,Rechts, left und right. Vielleicht solltest Du dich auf eine Schreibweise einigen, um die richtigen Attribute zu erwischen!!!
Rosa


----------



## SlaterB (9. Jun 2011)

'binärbaum höhe bestimmen' ist ein klassischen Thema was sich gut suchen lässt wenn du auf eigenes Denken verzichten willst, 
ansonsten schreibst du quasi nur dass du ein Problem hast, 
ok, wenn man einen Algorithmus nicht kennt kann man das kaum richtig beschreiben aber ein bisschen doch wohl noch?
etwa dass du, wenn du einen left-Nachfolger != null siehst, mit diesem irgendwie weiterarbeiten musst? hilfe.left.left?


----------



## Shulyn (9. Jun 2011)

[Java]
// Beispielhaft

while (hilfe.left != null){
    a++;
    hilfe = hilfe.left;
}
while (hilfe.right != null){
    b++;
    hilfe = hilfe.right;
}
[/Java]

Du musst nach jedem "prüfen" auch weiter gehen im Baum. Zur Zeit Prüfst du immer wieder die selbe stelle ...


----------



## thorstennn (9. Jun 2011)

```
return node == null ? 0 : Math.max( height(left, 1 + i), height(right, 1 + i) );
```


----------



## Andi_CH (9. Jun 2011)

Falls du nicht sowieso derselbe bist, schliess die mit dem da zusammen - der hat dieselben Probleme.

Höhe bestimmen und Knoten zählen läuft nach demselben Muster ab - rekursiv geht es am elegantesten.


----------



## thorstennn (9. Jun 2011)

sry:

```
return node == null ? -1 : Math.max( height(node.left, 1 + i), height(node.right, 1 + i) );
```


----------



## thorstennn (9. Jun 2011)

nein, i-1
löscht die anderen am besten oder fügt alle zusammen:

```
return node == null ? i-1 : Math.max( height(node.left, 1 + i), height(node.right, 1 + i) );
```
einfach zu schwierig heute


----------



## Andi_CH (9. Jun 2011)

Wie waers damit? Das ist natürlich Bestandteile eines nodes


```
public int hoehe() {
		int l = 0;
		int r = 0;
		if (leftSon != null)
			l = leftSon.hoehe();
		if (rightSon != null)
			r = rightSon.hoehe();
		return 1 + Math.max(l, r);
	}
```

Wenn man unbedingt murksen will, geht auch das mit ?: Notation auf einer Zeile, aber wir haben ja hier keinen Thrad wie diesen da


----------



## thorstennn (9. Jun 2011)

die letzte zeile ist auch gequetscht und jetzt zähle ich schon sieben statt einer zeile und dass auch noch bei auslassung aller optionaler klammern


----------



## Andi_CH (9. Jun 2011)

Newlines sind auch Optional - es ist also nur eine Zeile 

Ich bleibe dabei, dass die ?: notation wesentlich weniger gut zu verstehen ist als eine schön aufgebautes if und ich glaube nicht, dass es irgendwelche Vorteile hat.

Habs eben kurz getestet - funktioniert sogar richtig


----------

