Binärbäume in C erstellen und in die Konsole printen

Published by Philipp Schuster on 2016-07-202016-07-20

Oh je, seit über einem Monat habe ich mich schon nicht mehr im Blog gemeldet. Sorry, das tut mir leid. Ich bin seit Wochen fleißig und erfolgreich am lernen und nun mitten im Prüfungszeitraum. Das dauert auch noch drei Wochen, bis ich wieder Ruhe habe. In dem Zeitraum kann und will ich keine Zeit in den Blog stecken, da ich lernen muss. Hier habe ich aber heute immerhin was kleines für euch aus der Rubrik Programmierung und Skripte. Ich habe in C eine Funktion implementiert, die einen Binärbaum mit n Knoten erstellt und alle Knoten korrekt, aufeinander folgend beschriftet. Wer das auch mal im Studium braucht oder aus sonstigen Gründen, kann sich ja von meiner Lösung inspirieren lassen. Sie basiert auf folgender Tatsache:

Zeichnet ihr einen vollständigen Binärbaum auf, dann seht ihr schnell, dass jeder linke Folgeknoten den doppelten Wert des oberen Knotens hat und der rechte Nachfolger den doppelten Wert, der zusätzlich um eins inkrementiert wird. Mit dieser Bedingung kann ich rekursiv den Baum so weit es nötig ist aufspannen.

Zusätzlich habe ich eine einfache PrintTree-Funktion implementiert. Schaut euch meine Lösung einfach mal an, wenn ihr selbst Probleme habt eine zu implementieren. Alternativ könnt ihr mir auch gerne Tipps und Verbesserungsvorschläge geben.

 #include <stdio.h>
 #include <stdlib.h>

 struct treeNode {
   int key;
   struct treeNode * left;
   struct treeNode * right;
 };

 int countTreeNodes(struct treeNode * );
 struct treeNode * createNode(int);
 struct treeNode * createBinaryTree(int);
 void _createBinaryTreeHelper(int, int, struct treeNode * );

 // Zählt alle Knoten eines Binärbaumes ausgehend von einem Root-Knoten
 int countTreeNodes(struct treeNode * t) {
   if (t == NULL) {
     return 0;
   }
   return 1 + countTreeNodes(t -> left) + countTreeNodes(t -> right);
 }

 // erstellt einen einzelnen Knoten und setzt die Nachfolger auf NULL
 struct treeNode * createNode(int key) {
   struct treeNode * t = malloc(sizeof(struct treeNode));
   t -> key = key;
   t -> left = t -> right = NULL;
   printf("DEBUG: createNode(): Knoten mit key=%d angelegt\n", key);
   return t;
 }

 // erstellt einen vollständigen, korrekt beschrifteten Binärbaum
 struct treeNode * createBinaryTree(int nodeCount) {
   struct treeNode * tree = malloc(sizeof(struct treeNode));
   tree = createNode(1);
   // vom Root-Knoten ausgehend
   _createBinaryTreeHelper(nodeCount, 1, tree);
   return tree;
 }
 // erstellt ausgehend von einem Root-Knoten den restlichen Binärbaum
 void _createBinaryTreeHelper(int toKey, int key, struct treeNode * tree) {
   int
   const NEXT_KEY_LEFT = 2 * key;
   int
   const NEXT_KEY_RIGHT = 2 * key + 1; // geht aus vollständigem Binärbaum hervor

   printf("\nAktueller Key:%d\n", key);
   printf("  ->Right->Key :%d\n", NEXT_KEY_RIGHT);
   printf("  ->Left->Key :%d\n", NEXT_KEY_LEFT);

   if (key > toKey) {
     return;
   } else {
     tree -> key = key;
     // kann mit dem Knoten-Limit (Anzahl) ein Linker Nachfolger erzeugt werden?
     if (NEXT_KEY_LEFT <= toKey) {
       tree -> left = createNode(NEXT_KEY_LEFT);
       _createBinaryTreeHelper(toKey, NEXT_KEY_LEFT, tree -> left);
       // wenn der linke Nachfolger nicht erstellt werden konnte
       // kann der rechte erst Recht nicht erstellt werden
       if (NEXT_KEY_RIGHT <= toKey) {
         tree -> right = createNode(NEXT_KEY_RIGHT);
         _createBinaryTreeHelper(toKey, NEXT_KEY_RIGHT, tree -> right);
       }
     }
     return;
   }
 }

 void printBinaryTree(struct treeNode * tree) {
   if (tree -> left != NULL) {
     printf("(");
     printBinaryTree(tree -> left);
     printf(")<-");
   }
   // Knoten die keine Blätter sind hervorheben mit []
   if (tree -> left != NULL && tree -> right != NULL) {
     printf("[%d]", tree -> key);
   } else {
     printf("%d", tree -> key);
   }
   if (tree -> right != NULL) {
     printf("->(");
     printBinaryTree(tree -> right);
     printf(")");
   }
 }

 int main() {
   int nodeCount = 0;
   while (nodeCount < 1) {
     printf("Vollständigen Binärbaum erstellen:\n");
     printf("(Bitte eine ganze Zahl eingeben.)\n");
     printf("Eingabe: ");
     scanf("%d", & nodeCount);
   }
   struct treeNode * rootNodeBinaryTree = createBinaryTree(nodeCount);
   printf("\n---\n~fertig~\n");
   printf("Gefundene Knoten: %d\n\n", countTreeNodes(rootNodeBinaryTree));
   printf("Binärbaum geprinted:\n");
   printf("(Knoten in []-Klammern haben Nachfolger, Knoten nur in ()-Klammern sind Blätter)\n");
   printBinaryTree(rootNodeBinaryTree);
   printf("\n");
 }