Binäre Bäume

Schlagwörter:
Knoten, Knotenpunkte, Eintragen, Ausgeben, Programmierung, Referat, Hausaufgabe, Binäre Bäume
Themengleiche Dokumente anzeigen

Referat
Binäre Bäume 1. Allgemeines Binäre Bäume werden grundsätzlich verwendet, um Zahlen der Größe nach, oder Wörter dem Alphabet nach zu sortieren. Dem einfacheren Verständnis zu Liebe werde ich mich hier besonders auf die Zahlen beziehen, doch mit Buchstaben besteht in der Funktionsweise kein Unterschied. Zur Definition einiger Begriffe: Knoten bzw. Knotenpunkte sind die Stellen, wo die Zahlen eingetragen werden. Wurzel wird der aller oberste Knoten genannt. Verzweigungen sind die Verweise eines Knoten auf seinen linken oder rechten Nachfolgers. Als Tiefe wird bei den Binären Bäumen die Anzahl der Knotenpunkte bis zum tiefsten Element genannt. Nimmt man n als Tiefe an, so kann ein binärer Baum maximal 2n -1 Knoten haben. 2. Funktionsweise 2.1 Eintragen Das Prinzip basiert darauf, daß eine Zahl immer auf zwei weitere verweist, eine größere rechts und eine kleinere links. Die erste Zahl, die eingelesen wurde, dient als Wurzel. Von ihr gehen dann die weiteren Verzweigungen aus. Bei der nächsten Zahl vergleicht man diese mit der Wurzel. Ist die neue Zahl kleiner als die Wurzel, folgt man dem linken Zweig, ist sie größer, dem Rechten. Steht dort wieder eine Zahl, wird wieder verglichen, bis man an einem freien Platz angekommen ist. Hat man einen freien Platz erreicht, kann die Zahl eingetragen werden. 2.2 Ausgeben Möchte man nun die Zahlen ausgeben, fängt man wieder bei der Wurzel an. Sollen die Zahlen aufwärts sortiert ausgegeben werden, geht man den linken Verzweigungen nach, ...

Autor:
Kategorie:
Informatik
Anzahl Wörter:
1105
Art:
Referat
Sprache:
Deutsch
Bewertung dieser Hausaufgabe
Diese Hausaufgabe wurde bislang noch nicht bewertet.
Zurück