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

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. Finden könnt ihr das auch auf GithubC-Code Binärbäume.

 #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");
}

Philipp Schuster

Ich bin Philipp, studiere Informatik an der TU Dresden und arbeite als Werkstudent im Bereich Software-Entwicklung bei T-Systems MMS. Ich bin 22 Jahre alt und beschäftige mich in meiner Freizeit gerne mit meinem Blog, Programierung, Technik, aber auch mit Joggen und vielen anderen Dingen. Get To Know Me oder schreibt mich an!

Das könnte Dich auch interessieren …

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.