Höhe Binärbaum

Snouty · Anmeldungsdatum: 16.06.2005 Beiträge: 1 Wohnort: Saarbrücken

Gegeben sei ein binärer Baum T. Geben Sie einen Algorithmus in Pseudocode an, der die Höhe h des Baums T ermittelt, wobei h die Anzahl der Knotenebenen des Baumes zählt, d.h. ein Baum mit nur einem Knoten hat bereits die Höhe 1.

Kann mir da jemand helfen?
ich bekomm das irgendwie nichtgebacken :-(

thx schonmal im vorraus

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

Ist der Baum vollständig? D.h. eine neue Ebene wird nur aufgemacht wenn die alten alle voll sind? Wenn ja, dann kann man leicht die Höhe über den Logarithmus dualis und die Anzahl der Knoten berechnen. Ansonsten muss man ihn angemessen traversieren.

physikerin · Gast

@tobias:

dasgleiche wollte ich auch gerade fragen Augenzwinkern

@snouty:
Grundlagen findest du hier:
http://www.iti.fh-flensburg.de/lang/algorithmen/grundlagen/graph.htm
--> Baum
Ein vollständiger binärer Baum T mit n Knoten hat eine Tiefe von

d(T)) = int(log(n)).

Bezüglich des Algorithmus, wie Tobias die Frage: Ist der Baum vollständig?

Gruß
Christiane

Erchamion · Anmeldungsdatum: 07.06.2005 Beiträge: 13

Wenn er nicht vollständig ist ging es evtl. so in O(n) Schritten:

Gast

@snouty:

Bezüglich der Traversierung könnte dir weiterhelfen:
http://www.mathematik.uni-ulm.de/sai/ss04/prog/slides/baeume.html
http://www.inf.hs-zigr.de/~linke01/traversierung/trav.html

weiterhelfen.

Gruß
Christiane

Crotaphytus · Anmeldungsdatum: 08.05.2005 Beiträge: 213

Also, ich würd eher davon ausgehen, dass der Baum nicht vollständig ist, sonst wär die Aufgabenstellung ja sinnlos. Dann müsst man ja nicht groß anfangen Knotenebenen zu zählen, eben weil man das dann schön einfach mitm Logarithmus ausrechnen kann.

So stimmt auf jeden Fall der Code von Erchamion. Allerdings stellt sich die Frage, ob dir auch klar ist was da gemacht wird, immerhin sollst du das ja verstehen und nicht einfach nur ne Lösung haben... Augenzwinkern

Gast

Also snouty - gecheckt? Augenzwinkern

Das ganze machst du am besten rekursiv:

so in der Art: ...

funktion hoehe(baum T) {
wenn knoten extern: hoehe = 1; (oder 0 - je nachdem wie das bei dir definiert ist...)
wenn (linkes kind und rechtes kind existieren)
hoehe = 1 + max {hoehe linkes kind, hoehe rechtes kind}
wenn nur linkes kind existiert: hoehe = hoehe linkes kind +1;
wenn nur rechtes kind existiert: hoehe = hoehe rechtes kind + 1;
}

Also, wenn du dir das mal aufmalst, wirst du sehen, dass das ziemlich intuitiv ist...
Viel Erfolg! Wink

gast · Gast

ganz am ende muss noch wenn keines von allen der fall ist return 1 Augenzwinkern

wenn er an einem punkt ist der keine linken und rechten nachfolger hat Big Laugh