Bäume in C

Unter einem Binärbaum von Werten soll hier eine Entität verstanden werden, die entweder

A' „leer “ ist (der leere Baum ) oder

B' zwei verschiedene Bäume, die direkter linker Unterbaum und direkter rechter Unterbaum genannt werden, und einen Wert enthält.

Wenn im Fall B' die beiden Unterbäume leer sind, dann wird der Baum Blatt oder Blattbaum genannt.

Ein Baum heißt direkter Unterbaum eines anderen Baums, wenn er der direkte linke Unterbaum oder der direkte rechte Unterbaum dieses anderen Baums ist.

Der Übergang von einem Baum zu einem seiner direkten Unterbäume wird hier ein „Schritt “ genannt. Eine Folge von Schritten heißt ein „Pfad “. Ein Baum heißt Unterbaum eines anderen Baumes, wenn er durch einen Pfad von diesem anderen Baum aus erreicht werden kann.

Von einem leeren Baum oder einem Blattbaum führt kein Weg zu einem anderen Baum.

Die Definition eines Baumes ist rekursiv, da im Fall B' wieder auf Bäume bezug genommen wird. Ein Baum ist jedoch selber keine zirkuläre Datenstruktur, das heißt, es gibt keinen nichtleeren Pfad, der von einem Baum zu sich selbst führt.

Ein solcher Baum kann in der Programmiersprache C durch einen Zeiger repräsentiert (dargestellt) werden, der entweder

A gleich 0 ist oder

B auf eine Struktur mit zwei weiteren solcher Zeiger und einen Wert zeigt.

Bei Blättern wird etwas Speicherplatz für zwei Nullzeiger „verschenkt“, jedoch vermeidet diese Darstellung eines Baum die Komplikationen der Polymorphie, die sich ergeben würden, wenn statt dessen eine spezielle andere Struktur für Blätter verwendet werden würde.

Statische angelegte Bäume und ihre Ausgabe

Das folgende Beispielprogramm legt einen kleinen Baum an und gibt ihn wieder aus.

Anlegen und Ausgeben eines Baumes

#include <stdio.h>  /* printf, putchar */
#include <stdlib.h> /* EXIT_SUCCESS    */
typedef struct tree
{ struct tree * left; int value; struct tree * right; } * TREE;
void print( TREE const tree )
{ if( tree ){ putchar( '(' ); print( tree->left );
    printf( "%d", tree->value ); print( tree->right ); putchar( ')' ); }}
extern struct tree t1, t0, t2, t4; struct tree t3 =
                                      { &t1, 3, &t4 },
           t1 ={ &t0, 1, &t2 },                               t4 ={ 0, 4, 0 },
t0 ={ 0, 0, 0 },        t2 ={ 0, 2, 0 };
int main( void ){ print( &t3 ); putchar( '\n' ); return EXIT_SUCCESS; }

output

(((0)1(2))3(4))

Die folgende Veranschaulichung erhält man, indem man in dem obigen Quelltext von der Adresse »&t1« eine Linie zur darunter befindlichen Definition von »t1« zieht, und dies für die anderen Namen »t0«, »t2«, »t3« und »t4« entsprechend wiederholt.

Veranschaulichung

Entsprechend der obenstehenden Definition eines Baumes wurde hier mit »typedef« ein Zeiger auf eine Struktur als Baumtyp »tree« definiert, denn nur ein Zeiger kann auch 0 sein, wie im Fall „A“ festgelegt.

Man beachte wie die Struktur der Funktion »print« der Definition der Datenstruktur „Baum“ folgt: Es wird die Fallunterscheidung berücksichtigt und dann werden gegebenenfalls die einzelnen Komponenten behandelt.

Rob Pike's “Rule 5”: Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming.

Daß dann der Name des Parameters der print -Funktion gleich dem Namen dieses Typs gewählt wurde, ist sicher nicht jedermanns Geschmack, aber es ist technisch gesehen möglich (dann bezeichnet »tree« innerhalb des Funktionsrumpfs nur den Parameter »tree«, aber nicht mehr den Typ »tree«).

Die Initialisierung der Struktur muß in C90 außerhalb des Funktionsrumpfs erfolgen, wenn sie Initialisierer (wie »{ &t0, 1, &t2 }«) verwenden sollen, weil Initialisierer in C90 nur zur Schreibzeit bekannte Werte enthalten dürfen und die Adressen (wie »&t0«) nur bei Objekten mit statischer Speicherdauer konstant sind. Wenn die Adressen nicht konstant wären, dann wären nämlich nur Zuweisungen, wie in »t1.left = &t0; t1.right = &t2;«, möglich. In C99 könnten die Definitionen der fünf Variablen auch im Rumpf der Funktion »main« stehen, was eigentlich schöner wäre, da sie nur dort lokal benötigt werden.

Zwei Deklarationen, wie »int a; int b;« können auch als »int a, b;« zusammengefaßt werden, doch bedeutet »char* a, b;« »char *a; char b;« und nicht »char *a; char *b;«.

Da die Initialisierung einiger Baumstrukturen Vorwärtsbezüge auf andere Bäume enthält, wurden die Baumstrukturen zuvor mit Hilfe des Schlüsselwortes »extern« deklariert. Die Bäume wurden dann so definiert, daß die Anordnung der Initialisierer im Quelltext der Veranschaulichung der Baumstruktur ähnelt.

Die Ausgabefunktion »print« ist rekursiv. Rekursive Datenstrukturen legen oft entsprechend rekursive Algorithmen nahe. Man beachte, daß die Struktur der print -Funktion der Struktur der Datenstruktur »tree« recht ähnlich ist.

/ Präsenzaufgabe Baum durchsuchen: Schreiben Sie eine Funktion »contains« die einen Baum und eine Zahl als Argumentwerte akzeptiert und genau dann 0 ergibt, wenn die Zahl nirgends in dem Baum vorkommt, andernfalls soll sie einen Unterbaum aus dem Baum ergeben, der diese Zahl direkt darstellt (enthält). (Hierbei soll nicht angenommen werden, daß die Werte in dem Baum irgendwie „sortiert“ sind.)
/ Übungsaufgabe Vorhandene Bibliotheken nutzen: Wie bei Listen ist es auch beim Bäumen manchmal besser, vorhandene Bibliotheken zu nutzen. Finden Sie eine C -Bibliothek für (binäre) Bäume, erstellen Sie damit den oben veranschaulichten Baum und geben Sie diesen (möglichst mit Hilfe dieser Bibliothek) aus.; Hinweis Es wurde nicht geprüft, ob es tatsächlich eine passende Bibliothek gibt.

Die Textdarstellung eines Baums als Text, wie beispielsweise »(((0)1(2))3(4))« folgt der folgenden Grammatik mit dem Startsymbol 〈tree 〉.

〈tree 〉 ::=: [〈entry 〉].
〈entry 〉 ::=: '(' 〈tree 〉 〈number 〉 〈tree 〉 ')'.
〈number 〉 ::=: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'.

Die durch diese Grammatik beschriebene Sprache wird hier „Tree “ genannt..

Der rekursiven Struktur der darzustellenden Daten entspricht die rekursive Struktur dieser Grammatik.

Bei der Ausgabe (oder allgemeiner: beim Behandeln von Bäumen) werden verschiedene Möglichkeiten unterschieden:

Der Wert des Baumes wird zuerst behandelt, es folgt die Behandlung seines direkten linker Unterbaums und dann die Behandlung seines direkten rechten Unterbaums (“pre-order traversal ”).
Der direkte linke Unterbaum des Baumes wird zuerst behandelt, es folgt die Behandlung seines Wertes und dann die Behandlung seines direkten rechten Unterbaums (“in-order traversal ”). Das ist die in dem obigen Programm zur Ausgabe verwendete Vorgehensweise. Sie ist auch im folgenden anzunehmen, wenn keine andere Vorgehensweise angegeben wird.
Der direkte linke Unterbaum des Baumes wird zuerst behandelt, es folgt die Behandlung seines direkten rechten Unterbaums und dann die Behandlung seines Wertes (“post-order traversal ”).

Entsprechende Darstellungen arithmetischer Terme nennt man dann „Präfix/Infix/Postfix-Notation“: +(1,2); 1+2; 1,2,+. Eine Variante der ersteren wird als Cambridge-Notation in LISP verwendet, eine Variante der letzteren als „UPN“ bei einigen (heute wohl historischen) Taschenrechnern.

/ Präsenzaufgabe Durchlaufen eines Baumes: Schreiben Sie die Funktion »print« so um, daß sie ein “pre-order traversal ” verwendet. (Die Ausgabe des Programms sollte dann die Zahlen in der Reihenfolge „3,1,0,2,4“ enthalten – das genaue Format der Darstellung kann bei dieser Übungsaufgabe frei gewählt werden.

Dynamische angelegte Bäume und ihr Einlesen

Das folgende Programm zeigt das Einlesen und Ausgaben eines Baumes. Zum Einlesen wird ein rekursiver syntaktischer Abstiegsanalysator (“recursive descent parser ”), der aus den beiden Funktionen »tree_« und »entry« besteht verwendet. Seine Struktur entspricht der obigen Grammatik.

Zur Vereinfachung wird der Baum nicht aus einer Datei gelesen, sondern aus dem im Programm selber enthaltenen Text »(((0)1(2))3(4))«. Zum Einlesen lexikalischer Einheiten dient der lexikalische Analysator (“scanner ”) »get«.

Die Fehlerbehandlung ist vereinfacht oder fehlt, und es werden auch nur einstellige Zahlen verarbeitet.

Einlesen und Ausgeben eines Baumes

#include <stdio.h>   /* printf, putchar */
#include <stdlib.h>  /* EXIT_SUCCESS, abort */
/* tree */
typedef struct tree
{ struct tree * left;
  int value;
  struct tree * right; } * TREE;
TREE newtree( TREE const left, int const value, TREE const right )
{ TREE const result = malloc( sizeof *result );
  if( !result )abort();
  result->left  = left;
  result->value = value;
  result->right = right;
  return result; }
/* scanner */
char get( int const move )
{ static char const * const source = "(((0)1(2))3(4))";
  static int pos = 0;
  char const result = source[ pos ];
  if( result )pos += !!move;
  return result; }
/* parser */
int number( void ){ return get( 1 )- '0'; }
TREE tree( void );
TREE entry( void )
{ TREE left, right; int value;
  get( '(' );
  left  = tree();
  value = number();
  right = tree();
  get( ')' );
  return newtree( left, value, right ); }
TREE tree( void )
{ return get( 0 )== '(' ? entry() : 0; }
/* serializer */
void print( const TREE const tree )
{ if( tree )
  { putchar( '(' ); print( tree->left ); printf( "%d", tree->value );
    print( tree->right ); putchar( ')' ); }}
/* main */
int main( void )
{ print( tree() ); putchar( '\n' );
  return EXIT_SUCCESS; }

stdout

(((0)1(2))3(4))

Man beachte eine Vorabdeklaration („Vorwärtsdeklaration“) der Funktion »tree«, die nötig ist, weil »tree« und »entry« sich gegenseitig aufrufen (damit ist jede dieser beiden Funktionen indirekt rekursiv).

Man beachte auch die konstruierenden Funktionen („Konstruktoren“) »newtree« und »newleaf« (siehe unten) zum Erzeugen eines Baums beziehungsweise eines Blatts. Diese beiden Funktionen zeigen also, wie Bäume zur Laufzeit angelegt werden können, während das erste Programmbeispiel einen statischen Baum enthielt.

newleaf

TREE newleaf( int const value ){ return newtree( 0, value, 0 ); }

? Übungsfrage static

Welchen Sinn hat die Verwendung von »static« in der Methode »get«.

? Übungsfrage !!

Welchen Sinn hat die Verwendung von »!!« in der Methode »get«?

? Übungsfrage entry

Könnten die Funktion »entry« auch folgendermaßen (etwas kürzer) geschrieben werden?

tree entry( void )
{ tree result, left, right;
  get( '(' );
  result = newtree( tree(), numeral(), tree() ); 
  get( ')' );
  return result; }

Serialisierung

Dieses Programm zeigt eine ohne Verlust relevanter Informationen vorgenommene Hin-und-her-Wandlung zwischen einer struct -Repräsentation eines Baumes (»struct tree«) und einer Textdarstellung desselben Baumes in der Sprache Tree . Relevante Informationen interner Datenstrukturen werden oft in Texte gewandelt, um sie außerhalb eines Programms und seiner Laufzeit in eine Textdatei oder Datenbank ablegen („persistieren “) zu können. Die Wandlung in eine Textdarstellung (oder Byte -Sequenz) wird auch „Serialisierung “ genannt (“serialization ”, “marshalling ” [manchmal auch mit etwas speziellerer Bedeutung], oder seltener: “pickling ” [wörtlich: soaking something in vinegar to preserve it ] oder “shelving ”), die Wandlung einer Textdarstellung in eine interne Darstellung „Deserialisierung“ (“deserialization ”, “unmarshalling ”, “demarshalling ”).

XML ist ein Standardformat für Daten, das Baumstrukturen durch die Möglichkeit der Verschachtelung von XML -Elementen direkt unterstützt.

/ Übungsaufgabe Lesen aus Strom: Schreiben Sie das obige Programm so um, daß es die derzeit als Text im Programm enthaltene Baumdarstellung von der Standardeingabe »stdin« liest.
/ Übungsaufgabe Größere Zahlen: Schreiben Sie das obige Programm oder das Ergebnis der vorherigen Übungsaufgabe so um, daß in der Textdarstellung auch Numerale ganzer Zahlen, die größer als 9 sind, vorkommen können und richtig eingelesen werden.

Binäre Suchbäume

Bei binären Suchbäumen sind die (stets voneinander verschiedenen) Werte in aufsteigender Reihenfolge angeordnet. Dies ist in dem oben als Beispiel verwendeten Baum schon zu sehen, obwohl des oben noch nicht vorausgesetzt wurde.

Durch die Sortierung ist eine schnelle, binäre Suche nach Werten möglich. Diese Werte können auch Schlüssel zum Erreichen anderer Daten sein. Etwa Kennzahlen von Datensätzen, wobei dann ein Baum neben seinem Wert auch noch einen Verweis auf den zugehörigen Datensatz enthalten könnte. Die Suche nach Werten in solchen sortierten Bäumen ist meist schneller als die Suche nach Werten in linearen Listen.

In der Anwendungsprogrammierung empfiehlt es sich im allgemeinen nicht, Standardbehälter, wie binäre Suchbäume, erneut zu implementieren. Statt dessen sollte eine vorhandene Implementation (Bibliothek) oder eine Datenbank verwendet werden. Dadurch wird Zeit gespart, und die Qualität sorgfältig ausgewählter Fremdprodukte übertrifft oft die selbstgeschriebener Implementationen. Man würde normalerweise ja auch den verwendeten Rechner nicht selber bauen.

/ Übungsaufgabe Binäre Suchbäume: Auf verschiedenen Webseiten, wie etwa; http://de.wikipedia.org/wiki/Bin%C3%A4rer_Suchbaum; finden sich Beschreibungen typischer Operationen auf Binärbäumen wie der Suche oder dem Einfügen.; Das Einfügen können Sie auch an Hand der Operation “Insert ” mit dem Applet auf der Seite; http://www.cs.umd.edu/~egolub/Java/BinaryTree.html; beobachten, indem Sie wiederholt unterschiedliche Zahlen in das Textfeld schreiben und mit der Tastfläche »Insert« einfügen.; Implementieren Sie diese Operationen (Suchen, Einfügen und Löschen ) in C, indem Sie das zuletzt vorgestellte Programm zunächst an den von Ihnen bevorzugten Stil anpassen und dann entsprechend erweitern.; Beim Löschen eines Baumes sollte auch daran gedacht werden, nicht mehr benötigten Speicher mit allozierter Lebensdauer wieder freizugeben.
/ Übungsaufgabe Behälter veränderlicher Größe [wichtige Aufgabe, da ausdrücklich gewünscht! ]: Ein Programm soll die Menge der Benutzernamen einer Benutzergruppe modellieren. Da Benutzer aus der ganzen Welt über eine Web-Schnittstelle ein- oder austreten können, könnte die Anzahl der Benutzer auch groß werden. Andererseits soll zu jedem Zeitpunkt nicht mehr Speicher reserviert oder verwendet werden als benötigt wird.; Das Programm akzeptiert Zeilen, die mit einem Plus »+«, einem Fragezeichen »?« oder einem Minus »-« beginnen, dem direkt der Benutzername als Rest der Zeile folgt. (Ein Benutzername darf kein Zeilenendzeichen enthalten und besteht nur aus druckbaren Zeichen.); + Ein Benutzername, dem ein Pluszeichen vorangestellt ist, soll zur Benutzermenge hinzugefügt werden. Falls dies möglich war, soll nichts ausgegeben werden, falls der Name aber schon in der Menge enthalten ist oder das Einfügen scheiterte, soll eine Zeile mit einer entsprechenden Meldung ausgegeben werden.; ? Wenn ein Benutzername, dem ein Fragezeichen vorangestellt ist, in der Benutzermenge enthalten ist, soll die Zeile »1« ausgegeben werden, wenn nicht, die Zeile »0«.; - Ein Benutzername, dem ein Minuszeichen vorangestellt ist, soll aus der Benutzermenge entfernt werden. Falls dies möglich war, soll nichts ausgegeben werden, falls der Name aber schon vorher nicht in der Menge enthalten war oder das Entfernen scheiterte, soll eine Zeile mit einer entsprechenden Meldung ausgegeben werden.; Zur Vereinfachung der Lösung kann angenommen werden, daß fehlerhafte Eingaben bereits durch ein anderes Programm ausgefiltert wurden, so daß alle Eingaben syntaktisch korrekt sind.; Die Menge soll hierbei als (verkettete) Liste oder als binärer Baum oder als binärer Suchbaum realisiert werden. Da mit dieser Aufgabe die Verwaltung von Speicher mit allozierter Lebensdauer geübt werden soll, soll in diesem Fall keine Bibliothek anderer Autoren verwendet werden.; (Hinweis: In bestimmten Umgebungen kann der Speicher durch viele kleine Anforderungen und Freigaben ungünstig fragmentiert werden, besonders, wenn diese auch noch unterschiedliche Größe haben. Dann kann es besser sein, den Speicher teilweise innerhalb des Programms zu verwalten, was aber hier nicht behandelt werden kann. In der Praxis würde man für solche Aufgaben oft eine Datenbank verwenden.); (Hinweis: In der Mathematik sind Mengen nicht zeitlich veränderlich. Daher sollte oben genau genommen von einem „Mengenspeicher“ und nicht von einer „Menge“ gesprochen werden.)