Двоичное дерево поиска

 #include <stdio.h>

#include <stdlib.h>

// Структура узла дерева

typedef struct Node {

    int data;

    struct Node *left;

    struct Node *right;

} Node;

// Создание нового узла

Node* createNode(int value) {

    Node* newNode = (Node*)malloc(sizeof(Node));

    if (newNode == NULL) {

        printf("Ошибка выделения памяти!\n");

        exit(1);

    }

    newNode->data = value;

    newNode->left = NULL;

    newNode->right = NULL;

    return newNode;

}

// Вставка значения в дерево

Node* insert(Node* root, int value) {

    if (root == NULL) {

        return createNode(value);

    }

    

    if (value < root->data) {

        root->left = insert(root->left, value);

    } else if (value > root->data) {

        root->right = insert(root->right, value);

    }

    

    return root;

}

// Поиск значения в дереве

Node* search(Node* root, int value) {

    if (root == NULL || root->data == value) {

        return root;

    }

    

    if (value < root->data) {

        return search(root->left, value);

    }

    

    return search(root->right, value);

}

// Нахождение минимального значения в дереве

Node* findMin(Node* root) {

    while (root != NULL && root->left != NULL) {

        root = root->left;

    }

    return root;

}

// Удаление узла из дерева

Node* deleteNode(Node* root, int value) {

    if (root == NULL) {

        return root;

    }

    

    if (value < root->data) {

        root->left = deleteNode(root->left, value);

    } else if (value > root->data) {

        root->right = deleteNode(root->right, value);

    } else {

        // Узел с одним потомком или без потомков

        if (root->left == NULL) {

            Node* temp = root->right;

            free(root);

            return temp;

        } else if (root->right == NULL) {

            Node* temp = root->left;

            free(root);

            return temp;

        }

        

        // Узел с двумя потомками

        Node* temp = findMin(root->right);

        root->data = temp->data;

        root->right = deleteNode(root->right, temp->data);

    }

    

    return root;

}

// Обход дерева в порядке "in-order" (левый-корень-правый)

void inOrderTraversal(Node* root) {

    if (root != NULL) {

        inOrderTraversal(root->left);

        printf("%d ", root->data);

        inOrderTraversal(root->right);

    }

}

// Обход дерева в порядке "pre-order" (корень-левый-правый)

void preOrderTraversal(Node* root) {

    if (root != NULL) {

        printf("%d ", root->data);

        preOrderTraversal(root->left);

        preOrderTraversal(root->right);

    }

}

// Обход дерева в порядке "post-order" (левый-правый-корень)

void postOrderTraversal(Node* root) {

    if (root != NULL) {

        postOrderTraversal(root->left);

        postOrderTraversal(root->right);

        printf("%d ", root->data);

    }

}

// Освобождение памяти, занятой деревом

void freeTree(Node* root) {

    if (root != NULL) {

        freeTree(root->left);

        freeTree(root->right);

        free(root);

    }

}

int main() {

    Node* root = NULL;

    

    // Вставка элементов

    root = insert(root, 50);

    insert(root, 30);

    insert(root, 20);

    insert(root, 40);

    insert(root, 70);

    insert(root, 60);

    insert(root, 80);

    

    printf("In-order обход: ");

    inOrderTraversal(root);

    printf("\n");

    

    printf("Pre-order обход: ");

    preOrderTraversal(root);

    printf("\n");

    

    printf("Post-order обход: ");

    postOrderTraversal(root);

    printf("\n");

    

    // Поиск элемента

    int key = 60;

    Node* found = search(root, key);

    if (found != NULL) {

        printf("Элемент %d найден в дереве.\n", key);

    } else {

        printf("Элемент %d не найден в дереве.\n", key);

    }

    

    // Удаление элемента

    printf("Удаляем элемент 20\n");

    root = deleteNode(root, 20);

    printf("In-order обход после удаления: ");

    inOrderTraversal(root);

    printf("\n");

    

    // Освобождение памяти

    freeTree(root);

    

    return 0;

}