Binäre Bäume sind im Prinzip ähnlich wie verkettete Listen. Mit dem Unterschied zu doppelt verkettete Listen sind Binäre Bäume nicht linear angeordnet. Bevor ich weitererkläre hierzu 2 Bilder...
Und welchen Vorteil haben nun binäre Bäume? Zählen sie doch mal die Schritte die sie brauchen bis sie vom Anfang der doppelt verketteten Liste zur Ziffer 5 brauchen und dann die Schritte beim Binären Baum! Der Anfang (Wurzel) beim Binären Baum ist die Ziffer 3. Bei solch kleinen Beispielen mag das jetzt kein Vergleich Wert sein, aber wenn wir z.B. Tausende von Einträgen haben wirkt sich das schon aus. Sicher fällt Ihnen an diesem Bild auch auf das alle Werte die kleiner sind als 3 auf der linken Seite des Baumes sind und alle die größer sind auf der rechten Seite des Baumes sind. Aber das ist jetzt erst mal nebensächlich. Folgende 2 Regeln gelten für Binäre Bäume....
- Jeder Knoten besitzt höchstens 2 Nachfolger.
- Es gibt 1 Knoten, die sogenannte Wurzel (root) welcher keinen Vorgänger besitzt.
Die Gesamtheit eines Nachfolgerknoten eines Knotens bilden zusammen einen Teilbaum. So ist z.B.: der Knoten mit den Wert 2 und 1 der linke Teilbaum und die Knoten mit dem Werten 4 und 5 nennt man den rechten Teilbaum.
Die Knoten mit der Nummer 1 und 5 nennt man ein Blatt da diese Knoten keinen Nachfolger mehr haben.
Mit diesem Grundlagenwissen können wir nun beginnen einen Binären Baum zu Programmieren. Wie soll also unsere Struktur für einen Knoten aussehen?
struct knoten{
int wert;
struct knoten *links;
struct knoten *rechts;
};
Damit der Umfang unseres Beispiels nicht allzu sehr anwächst möchte ich mich mit der Eingabe eines Wertes (int wert) in unserer Struktur begnügen. Sie könne sich ja das Programm Ihren Bedürfnissen anpassen wie wir es schon in dem Kapitel der verketteten Listen getan haben. Außer dem einem int-Wert besitzt unsere Struktur noch jeweils einen Zeiger auf den linken und einen Zeiger auf den rechten Nachfolger des Knotens. Somit können sie sich unsere Struktur vom Typ knoten etwa so vorstellen.....
Als erstes benötigen wir also eine Funktion mit der wir unsere Werte einordnen. Wir wollen die kleineren Werte immer auf die Linke Seite und die Größeren Werte immer auf die rechte Seite einordnen....
struct knoten{
int wert;
struct knoten *links;
struct knoten *rechts;
};
typedef struct knoten KNOTEN;
KNOTEN *einordnen(KNOTEN *zeiger)
{ //---->Funktion......
Hier nochmals schnell die Struktur. Ich habe außerdem mit typedef einen neuen Datentyp Namens KNOTEN definiert. Kommen zur Funktion mit der wir unsere Struktur einordnen. Folgende 3 Möglichkeiten können uns beim Einordnen in dem Binären Baum passieren....
- Es ist noch kein Element (genauer noch es fehlt die Wurzel (root)) im Baum und das von uns eingefügte ist das Erste Element und somit die Wurzel des Baumes....
if(zeiger==NULL) { zeiger=(KNOTEN*)malloc(sizeof(KNOTEN)); zeiger->wert=zahl; zeiger->links=zeiger->rechts=NULL; }
- Unsere neue Zahl ist kleiner als die Wurzel bzw. bei weiterem Verlauf als der Knoten somit wollen wir die neue Struktur links von der Wurzel bzw. Knoten einordnen...
else if(zeiger->wert >= zahl) zeiger->links=einordnen(zeiger->links);Hier erfolgt nun der 1. Rekursive Aufruf. Unser Zeiger zeiger der nach links zeigt bekommt die Adresse von von dem erneuten Funktionsaufruf einordnen(zeiger->links).
- Als letzte Möglichkeit haben wir, falls der Wert des neuen Elementes größer als der der Wurzel bzw. des Knotens ist, so kommt dieser immer auf die rechte Seite der Wurzel bzw. des Knotens....
else if(zeiger->wert < zahl) zeiger->rechts=einordnen(zeiger->rechts);
Hier nun die Komplette Funktion zum Einordnen eines neuen Elementes in dem Binären Baum mit main - Funktion...
/*Download:bbaum1.c*/ |
Ich will ihnen anhand von 5-6 Zahlen die Funktion Bildlich und Schriftlich erklären. Wir starten das Programm und geben als ersten Wert...
10
ein. Nun wird mittels wurzel=einordnen(wurzel) die Funktion mit Übergabe als Parameter den Datentyp KNOTEN *wurzel. Nun trifft in der Funktion einordnen() die erste if - Anweisung....
if(zeiger==NULL)
..gleich zu. Womit die Zahl 10 unser 1.Element und somit die Wurzel unseren Baumes darstellt. Die beiden Zeiger links und rechts bekommen noch einen NULL - Zeiger zugewiesen...
Als nächstes geben wir z.B. die Zahl '8' ein. Wieder wird über die main - Funktion die Funktion einordnen() aufgerufen. Diese mal ist aber (zeiger==NULL) unwahr den unser 1. Element bzw die Wurzel unseres Baumes stellt die Zahl 10 da. Also auf zur else - if Abfrage...
else if(zeiger->wert >= zahl)
Aber das trifft jetzt zu zeiger->wert ('10') ist größer als die von uns zuvor eingegebene Zahl. Also auf zu ersten Funktionsselbstaufruf....
zeiger->links=einordnen(zeiger->links);
Nun soll also unser Zeiger zeiger der auf links zeigt die Adresse bekommen von dem erneuten Funktionsaufruf einordnen(zeiger->links). Also beginnen wir wieder erneut die Funktion durchzugehen....
if(zeiger==NULL)
Und tatsächlich zeigt unser Zeiger zeiger nun auf NULL, da er ja zuvor durch den erneuten Aufruf die Adresse von der linken Seite des 1.Elements ('10') bekommen hat. Also allokieren wir wieder Speicher und fügen unser neues Element ein. Der linke und der rechte Zeiger unseres neuem Elementes geben wir wieder die NULL-Zeiger...
Als nächstes geben wir jetzt z.B. die Zahl 9 ein. Im ersten Durchlauf wird....
else if(zeiger->wert >= zahl)
zeiger->links=einordnen(zeiger->links);
...wie schon zuvor ausgeführt. Jetzt zeigt unser Zeiger zeiger auf die Adresse mit dem Wert '8'. Also ist zeiger==NULL nicht wahr und......
else if(zeiger->wert >= zahl)
....ist diesesmal aber auch nicht wahr, denn zeiger->wert ('8') ist dieses mal nicht größer oder gleich der von uns eingegeben Zahl ('9'). Also zur nächsten else - if - Anweisung.....
else if(zeiger->wert < zahl)
...und diese ist wahr denn 8<9 trifft zu nun der 2. Rekursive Funktionsaufruf (einer liegt ja schon auf dem Stack)....
zeiger->rechts=einordnen(zeiger->rechts);
Dieses mal bekommt der Zeiger zeiger der auf rechts zeigt die Adresse von einordnen(zeiger->rechts). Das ist übrigens auch der Grund weswegen unsere Funktion eine Rückgabewert vom Typ KNOTEN *einordnen() hat! Also auf zum erneuten Durchlauf der Funktion. zeiger==NULL trifft wieder zu also haben wir den Platzt für das neue Element wieder gefunden ...
Zum return-Wert muss ich glaube ich nicht mehr viel zu sagen. Um beim Beispiel zu bleiben gibt unser neues Element mit dem Wert 9 an Ihrem Aufrufer dem Element mit dem Wert 8 Ihre Adresse an. Unser Element mit dem Wert von 8 wurde auch rekursiv Aufgerufen von dem Element mit dem Wert 10 und gibt somit auch die Adresse von sich selbst an das Element mit dem Wert 10. Und unsere Wurzel ('10') gibt Ihre Adresse mittels return auch wieder an Ihren Aufrufer, im letzten Fall an die main - Funktion zurück.
Als nächstes wollen wir die Zahl 20 eingeben. Hierzu will ich nur noch ein Bild hinzufügen da die Funktion jetzt Ausführlich erklärt wurde und es an der Zeit ist das sie das Beispiel jetzt selber durchgehen......
Im nächsten Kapitel wollen wir die einzelnen Knoten mal Durchforsten, Ausgeben oder Löschen.
