Binärbaum höhe herausfinden

[babuschka]

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]

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]

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

 

[Rosa]

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]

'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]

[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]

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

 

[Andi_CH]

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]

sry:

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

 

[thorstennn]

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]

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]

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]

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 🙂