Informatik - Übungen zu C - Binärer Baum
// bintree.c // zeigt zwei Grundaufgaben mit Bäumen #include <stdio.h> #include <stdlib.h> // Datenstruktur für einen Knoten: Inhalt und zwei Zeiger auf die nächsten Knoten typedef struct node { int wert; struct node* left; struct node* right; } t_node; // Alle Knoten eines Baum in der Reihenfolge // Wurzel -> Knoten -> Blätter (top-down) erfassen. // printf steht stellvertretend fÜr die Aktion mit dem Knoten void topdown(t_node* node) { if (node != NULL) { printf("%i\n", node->wert); topdown(node->left); topdown(node->right); } } // Alle Knoten eines Baum in der Reihenfolge // Blätter -> Knoten (bottom-up) erfassen // printf steht stellvertretend fÜr die Aktion mit dem Knoten void bottomup(t_node* node) { if (node != NULL) { bottomup(node->left); bottomup(node->right); printf("%i\n", node->wert); } } int main(void) { t_node *root; t_node *nodelist[11]; int i; int size = sizeof (t_node); /* Beispiel eines Baumes: 0 | +--------+--------+ | | 1 6 | | +---+---+ +---+---+ | | | | 2 3 7 8 | | +---+---+ +---+---+ | | | | 4 5 9 10 Der Aufbau des Baumes erfolgt hier auf eine sehr einfache Art: Zuerst werden die einzelnen Knoten erzeugt, Inhalt des Knotens ist eine fortlaufende Nummer. Der Inhalt kann jedoch beliebig sein: ein Zeichen, eine Zeichenkette, eine Struktur. Die Adressen der Knoten merken wir uns vorläufig in einem Vektor nodelist[]. Bei dieser Methode werden also zuerst "frei herumliegende Knoten" erzeugt. Öfters wachsen Bäume aus sich selber heraus, d. ausgehend von einem Knoten erzeugt man sich weitere Knoten und hängt sie an den Knoten. */ for (i = 0; i < 11; i++) { nodelist[i] = (t_node*) malloc(size); // Speicherplatz anfordern nodelist[i]->wert = i; // Inhalt festlegen nodelist[i]->left = NULL; // Zeiger auf nächsten Knoten links nodelist[i]->right = NULL; // Zeiger auf nächsten Knoten rechts } // Jetzt stellen wir die Verbindungen zwischen den Knoten her, // d.h bauen den eigentlichen Baum auf. root = nodelist[0]; nodelist[0]->left = nodelist[1]; nodelist[0]->right = nodelist[6]; nodelist[1]->left = nodelist[2]; nodelist[1]->right = nodelist[3]; nodelist[3]->left = nodelist[4]; nodelist[3]->right = nodelist[5]; nodelist[6]->left = nodelist[7]; nodelist[6]->right = nodelist[8]; nodelist[8]->left = nodelist[9]; nodelist[8]->right = nodelist[10]; // Kontrollausgabe for (i = 0; i < 11; i++) { printf("%2i: %2i left = %p, right = %p\n", i, nodelist[i]->wert, nodelist[i]->left, nodelist[i]->right); } // Jetzt brauchen wir die Liste eigentlich nicht mehr und zeigen wie man // den Baum von oben nach unten durchläuft printf("List the tree top-down\n"); topdown(root); // den Baum von unten nach oben durchläuft printf("List the tree bottom up\n"); bottomup(root); return 0; }