Binary Tree in C

Question

Wie funktioniert ein Binary Tree und wie erstelle ich einen in C?

Answer 1

Ein binärer Baum (Binary Tree) ist eine Datenstruktur die aus Knoten besteht, die miteinander verbunden sind. Jeder Knoten kann höchstens zwei Kindknoten haben: einen linken und einen rechten Kindknoten. Diese Struktur ermöglicht effiziente Such-, Einfüge- und Löschoperationen. Hier ist ein einfaches Beispiel mit einer Inorder Traversierung.

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

// Definition eines binären Baumnodens
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// Funktion zur Erstellung eines neuen Knotens
struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Funktion zur Einfügung eines Werts in den Baum
struct TreeNode* insert(struct TreeNode* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }

    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }

    return root;
}

// Funktion zur Durchführung einer Inorder-Traversierung (links, Wurzel, rechts)
void inorderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

int main() {
    struct TreeNode* root = NULL;
    root = insert(root, 5);
    root = insert(root, 3);
    root = insert(root, 8);
    root = insert(root, 1);
    root = insert(root, 4);

    printf("Inorder Traversierung: ");
    inorderTraversal(root);

    return 0;
}