Die maximale Anzahl der direkten Nachfolger, die ein Knoten hat,
heiß Grad des Baumes.
Ein Baum vom Grad 2 ist der binäre Baum. Er stellt einen wichtigen
Sonderfall dar. Gegenüber dem allgemeinen Baum zeichnet er sich
folgendermaßen aus:
- Jedes Element außer dem Anfangselement hat genau einen
direkten Vorgänger.
- Jedes Element hat null bis zwei direkte Nachfolger, die als
linker bzw. rechter Nachfolger unterschieden werden.
- Der Binärbaum besteht also aus einer Wurzel und zwei
Teilbämen, wobei ein Baum und damit auch ein Teilbaum leer sein kann.
- Eine Sonderform ist der vollständige Binärbaum,
bei dem jeder Knoten außer den Blättern zwei nicht leere
Teilbäume besitzt und jeder Pfad die gleiche Länge hat.
Offensichtlich kann man in einem binären Baum der Tiefe n höchstens
2n-1 Knoten unterbringen. Bei einem unvollständigen Baum sind
es entsprechend weniger. Im ungünstigsten Fall lassen sich nur n Elemente
unterbringen, genau dann, wenn jeder Knoten nur einen Nachfolger besitzt.
In diesem Fall degeneriert der Baum zu einer linearen Liste.
Die Baumstruktur ist rekursiver Natur, da die Nachfolger eines Knotens
jeweils wieder als Wurzeln von Bäumen aufgefasst werden können.
Diese Baum-Teilbaum-Beziehung lässt sich rekursiv wie folgt
definieren:
Ein Binärbaum ist entweder leer oder er besteht aus einer
Wurzel, die über bis zu zwei Kanten mit disjunkten nicht-leeren
Binärbäumen verbunden ist.
Wenn die Knoteninhalte untereinander keine Ordnung besitzen ist der Baum ungeordnet.
Bei geordneten Bäumen ist eine vollständige Ordnungsrelation zwischen
den Knoten Voraussetzung. Sie wird oft über einen Schlüssel realisiert.
Beispiele für Ordnungsschlüssel sind:
- Enthalten die Knoten nur natürliche Zahlen, so ist die
numerische Ordnung eine derartige Relation.
- Falls die Knoten Zeichenketten enthalten, so ist die lexikographische
Ordnung geeignet.
Lege nun "<" eine vollständige Ordnungsrelation
zwischen den Knoten eines Binärbaums fest, dann ist jeder Knoten des Baums
kleiner als alle Knoten seines rechten Teilbaums und zugleich größer
oder gleich als alle Knoten seines linken Teilbaums.
Offensichtlich gilt für jeden Knoten, daß ein kleinerer Nochfolgeknoten
links und ein größerer rechts unterhalb anzuordnen ist. Nach der
verwendeten Ordnungsrelation ist im Fall der Gleichheit ein
Nachfolgeknoten ebenfalls links unterhalb anzuordnen.
Der Suchbaum
Der geordnete Baum erlaubt eine schnelle Suche von Informationen, ähnlich
wie das binäre Suchverfahren in linearen Strukturen. Der geordnete Baum
heißt deshalb auch Suchbaum. Dazu ein Beispiel.
Gegeben sei folgende lineare Liste:
Der direkte Zugriff auf die Elemente der Liste sei möglich. Bei der
binären Suche wird auf das mittlere Element zugegriffen. Das
Anfangselement ist somit nicht mehr A sondern E, das die Liste in zwei
Teile teilt:
Ist E nicht das gesuchte Element, wird in der linken oder rechten Teilliste
weitergesucht.
Teilt man die Liste solange nach diesem Verfahren, bis diese nur noch aus
je einem Element bestehen, so liegt ein geordneter Baum in der bekannten
Darstellung vor.
Dieser Baum ist so geordnet, dass alle Elemente im rechten Teilbaum einen
lexikalisch größeren Wert besitzen als die Wurzel, und alle Elemente im
linken Teilbaum einen kleineren. Dies gilt auch für alle Teilbäume. Einen
derart georneten Baum bezeichnet man als binären Suchbaum.
Damit wurde die linear verkettete Struktur, auf der im Prinzip nur
sequentiell gesucht werden kann, durch Umorganisation in eine binäre
Baumstruktur überführt, auf der der Suchvorgang aufgrund der
Ordnungsrelation binär verläuft.
Auch bei der Datenstruktur Baum besteht die Notwendigkeit, Elementinhalte
dauerhaft zu speichern und bei Bedarf zu laden. Dies führt zu dem
grundsätzlichen Problem, die binär verzweigte Struktur so in eine lineare
Struktur zu überführen, dass die Daten so als Datei gespeichert werden
können, dass später daraus der ursprüngliche Binärbaum wieder
rekonstruiert werden kann. Gegeben sei folgender Binärbaum:
- Inorder Traversierung
Die Inorder-Traversierung hat stets die Reihenfolge linker
Teilbaum - Wurzel - rechter Teilbaum. Die Wurzel steht in der Mitte.
Der Baumdurchlauf nach dem Inorder-Algorithmus hat die besondere
Eigenschaft, die nach einem bestimmten Kriterium in den Baum
eingefügten Informationen der Knoten in ihrer sortierten Reihenfolge
auszugeben.
2 4 5 7 13 14 16 19 20 22 24 25 26 29 31
inorder (baumtyp *baum)
{
if (baum != NULL)
{
inorder (linker_teilbaum);
verarbeite Wurzelinformation von baum;
inorder (rechter_teilbaum);
}
}
Anwendungsbeispiel:
Dies ist die typische Traversierungs-Strategie, um eine vollständig
sortierte Liste aus einem Suchbaum zu bekommen: Besuche den linken Teilbaum (in dem alle
Elemente kleiner als das Wurzelelement sind), dann die Wurzel, dann den rechten Teilbaum
(in dem alle Elemente größer als die Wurzel sind).
- Postorder Traversierung
Ändert man den Traversierungsalgorithmus dahingehend ab, dass der Baum
in der Reihenfolge linker Teilbaum - rechter Teilbaum - Wurzel
durchlaufen wird, spricht man von Postorder-Traversierung.
2 5 4 13 16 14 7 20 24 22 26 31 29 25 19
Dieses Ergebnis erzielt man, wenn man von der Wurzel ausgehend links herum
alle Knoten längs der Kanten besucht und jedesmal, wenn man
rechts neben einem Knoten vorbeikommt, den Knoteninhalt
aufschreibt.
postorder (baumtyp *baum)
{
if (baum nicht leer)
{
postorder (linker_teilbaum);
postorder (rechter_teilbaum);
verarbeite Wurzelinformation von baum;
}
}
Anwendungsbeispiel:
Bei einem Taschenrechner oder anderen einfachen Automaten müssen zunächst
intern die Argumente einer Rechenoperation in Register geladen werden. Danach wird die
verknüpfende Operation aufgerufen (umgekehrt polnische Notation). POST-Order
liefert dazu die passende Besuchs-Reihenfolge: (Argument1, Argument2)
Operation.
- Preorder Traversierung
Eine dritte Möglichkeit der Traversierung besteht in der Reihenfolge
Wurzel - linker Teilbaum - rechter Teilbaum:
19 7 4 2 5 14 13 16 25 22 20 24 29 26 31
Dieses Ergebnis erzielt man, wenn man von der Wurzel ausgehend links herum
alle Knoten längs der Kanten besucht und jedesmal, wenn man
links neben einem Knoten vorbeikommt, den Knoteninhalt
aufschreibt.
preorder (baumtyp *baum)
{
if (baum nicht leer)
{
verarbeite Wurzelinformation von baum;
preorder (linker_teilbaum);
preorder (rechter_teilbaum);
}
}
Anwendungsbeispiel:
Im Zusammenhang mit Funktionen kann in der Wurzel der Funktionsaufruf, in
den Teilbäumen die Argumente stehen. PRE-Order ergibt dann die "gewohnte"
Schreibweise Funktion (Argument1, Argument2)
Beispielimplementierung: Einfügen in einen Baum und Ausgabe des Baums:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXLEN 80
struct tnode /* Binaerbaum */
{
char word[MAXLEN]; /* Text */
int count; /* Zaehler */
struct tnode *left; /* linker Nachfolger */
struct tnode *right; /* rechter Nachfolger */
};
struct tnode *talloc(void);
/* Platz fuer einen tnode besorgen */
struct tnode *insert_tree(struct tnode *p,char *w);
/* w bei oder nach p einfuegen */
void treeprint(struct tnode *p);
/* Baum p rekursiv ausgeben */
int main(void)
{
struct tnode *root;
char word[MAXLEN];
root = NULL;
while ((gets(word)) != NULL) /* Baum einlesen */
root = insert_tree(root,word);
printf("\n");
treeprint(root); /* Baum ausgeben */
return(0);
}
struct tnode *talloc(void)
/* Platz fuer einen tnode besorgen */
{
return((struct tnode *) malloc(sizeof(struct tnode)));
}
struct tnode *insert_tree(struct tnode *p,char *w)
/* w bei oder nach p einfuegen */
{
struct tnode *talloc();
int cond;
if (p == NULL)
{ /* ein neues Wort */
p = talloc(); /* einen neuen Knoten anlegen */
strcpy(p->word, w);
p->count = 1;
p->left = NULL;
p->right = NULL;
}
else
{
cond = strcmp(w, p->word); /* Vergleich w mit Knoten */
if (cond == 0)
p->count++; /* Wort w schon vorhanden */
else if (cond < 0) /* w ist kleiner, links darunter */
p->left = insert_tree(p->left,w);
else /* w ist groesser, rechts darunter */
p->right = insert_tree(p->right,w);
}
return(p);
}
void treeprint(struct tnode *p)
/* Baum p rekursiv ausgeben */
{
if (p != NULL)
{
treeprint(p->left);
printf("%s (%4d)\n", p->word, p->count);
treeprint(p->right);
}
}
Ein weiteres Beispiel: Das folgende Programm liest aus der Quellatei die
Wörter und gibt sie lexikographisch sortiert mit Häufigkeitsangabe
in die Zieldatei aus.
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#define MAX_WORT 200
struct tnode
{
char *wort;
int zahl;
struct tnode *links;
struct tnode *rechts;
};
typedef struct tnode knoten;
FILE *quelle, *ziel;
FILE *eopen(char *file,char *mode);
int lieswort(char *w, int lim);
knoten *suche(knoten *p, char *w);
inorder(knoten *p);
char *merke_wort(char *s);
int main(int argc, char *argv[])
{
knoten *unterbaum, *suche();
char progname[500];
char wort [MAX_WORT];
int c;
progname = argv[0];
if (argc != 3)
{
fprintf(stderr,"Syntax: %s Quelldatei Zieldatei\n",progname);
exit(1);
}
quelle = eopen(argv[1],"r");
unterbaum = NULL;
while ((c = lieswort(wort, MAX_WORT)) != -1)
if (c == 1)
unterbaum = suche(unterbaum, wort);
fclose(quelle);
ziel = eopen(argv[2],"w");
inorder(unterbaum);
fclose(ziel);
return 0;
}
int lieswort(char *w, int lim)
/* lieswort liest aus einer Datei ein Wort der Laenge lim in den
** Speicher, auf den w zeigt, und gibt 1 zurueck, falls es
** wirklich Alphazeichen gelesen hat, jedoch -1 im Fall zu
** grosser Wortlaenge. Falls Nicht-Alpha-Zeichen gelesen werden,
** wird 0 zurueckgegeben.
*/
{
int c;
while (!isalpha(c = getc(quelle)))
if (c == EOF) return -1;
*w++ = c;
lim--;
while (isalpha(c = getc(quelle)) && (lim > 0))
{
*w++ = c; lim--;
}
if (lim == 0)
{
printf("%s: Error: Wort zu lang ", progname);
return -1;
}
else
*w = '\0';
if (lim < MAX_WORT) return 1;
else return 0;
}
FILE *eopen(char *file,char *mode)
{
FILE *fp, *fopen();
if ( (fp = fopen(file, mode)) != NULL )
return fp;
fprintf(stderr,
"%s: Datei %s kann im Modus %s nicht geoeffnet werden\n",
progname, file, mode);
exit(1);
}
knoten *suche(knoten *p, char *w)
/* suche durchsucht den Baum auf das Vorkommen des Wortes w,
** traegt es gegebenenfalls lexikographisch richtig ein bzw. erhoeht
** dessen Zahl und gibt den Pointer auf seinen Knoten zurueck.
*/
{
int cond;
if (p == NULL)
{
p = (knoten *) malloc(sizeof(knoten));
p->wort = merke_wort(w);
p->zahl = 1;
p->links = p->rechts = NULL;
}
else if ((cond = strcmp(w, p->wort)) == 0)
p->zahl++;
else if (cond < 0)
p->links = suche(p->links, w);
else p->rechts = suche(p->rechts, w);
return p ;
}
inorder(knoten *p)
/* inorder gibt den Unterbaum, auf den p zeigt, in Inorder aus.
*/
{
if (p != NULL)
{
inorder(p->links);
fprintf( ziel, "%4d %s\n", p->zahl, p->wort);
inorder(p->rechts);
}
}
char *merke_wort(char *s)
/* merke_wort speichert das Wort, auf dessen ersten Charakter s zeigt,
** und gibt einen Zeiger auf dessen neue Lokation an.
*/
{
char *p;
if ((p = (char *)malloc( strlen(s)+1 )) != NULL)
strcpy(p, s);
return p ;
}
|
| 
DIENSTE
