work2/task1.cpp - develop - novd7/algirithms_sem2

work2/task1.cpp
175 строк6 KB
Новиков Владимир
work 2
03 апр 2026, 22:39
03 апр 2026, 22:3904518aa
#include <ctime>
#include <iostream>
using namespace std;

// Структура узла двоичного дерева
struct Node {
    int data;     // Данные узла
    Node* left;   // Указатель на левое поддерево
    Node* right;  // Указатель на правое поддерево
};

// Функция для создания нового узла
Node* createNode(int value) {
    Node* newNode = new Node;
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Функция для добавления элемента в дерево
Node* insert(Node* root, int value) {
    if (!root) {
        root = createNode(value);  // Если дерево пустое, создаём корень
    } else if (value < root->data) {
        root->left = insert(root->left, value);  // Рекурсивно вставляем в левое поддерево
    } else {
        root->right = insert(root->right, value);  // Рекурсивно вставляем в правое поддерево
    }
    return root;
}

// Прямой обход дерева
void preorder(Node* root) {
    if (root) {
        cout << root->data << " ";  // Посетить корень
        preorder(root->left);       // Обход левого поддерева
        preorder(root->right);      // Обход правого поддерева
    }
}

// Обратный обход дерева
void postorder(Node* root) {
    if (root) {
        postorder(root->left);
        postorder(root->right);
        cout << root->data << " ";
    }
}

// Симметричный обход дерева
void inorder(Node* root) {
    if (root) {
        inorder(root->left);
        cout << root->data << " ";
        inorder(root->right);
    }
}

// Вычисление глубины (высоты) дерева
int height(Node* root) {
    if (root == nullptr) {
        return -1;
    }
    return 1 + max(height(root->left), height(root->right));
}

// Поиск узла по значению
Node* search(Node* root, int key) {
    if (root == nullptr) return nullptr;

    if (root->data == key) return root;

    if (key < root->data)
        return search(root->left, key);
    else
        return search(root->right, key);
}

// Поиск минимального элемента в дереве
Node* findMin(Node* root) {
    if (root == nullptr) return nullptr;
    if (root->left == nullptr) return root;
    return findMin(root->left);
}

// Удаление узла по значению
Node* remove(Node* root, int key) {
    // Дерево пустое
    if (root == nullptr) return nullptr;

    // Если ключ меньше текущего
    if (key < root->data) root->left = remove(root->left, key);
    // Если ключ больше текущего
    else if (key > root->data)
        root->right = remove(root->right, key);
    // Узел с нужным ключом найден
    else {
        if (root->left == nullptr && root->right == nullptr) {
            // Случай 1: у узла нет потомков
            delete root;
            return nullptr;
        } else if (root->left == nullptr) {
            // Случай 2: есть только правый потомок
            Node* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            // Случай 2: есть только левый потомок
            Node* temp = root->left;
            delete root;
            return temp;
        } else {
            // Случай 3: два потомка
            Node* temp = findMin(root->right);
            root->data = temp->data;
            root->right = remove(root->right, temp->data);
        }
    }
    return root;
}

// Главная функция
int main() {
    Node* root = nullptr;  // Создаём пустое дерево
    int n;
    cout << "Введите количество элементов: ";
    cin >> n;

    // Инициализация генератора случайных чисел
    srand(time(0));

    // Заполняем дерево случайными числами
    cout << "Элементы дерева (случайные числа): ";
    for (int i = 0; i < n; i++) {
        int value = rand() % 100 + 1;  // Случайное число от 1 до 100
        cout << value << " ";
        root = insert(root, value);  // Добавляем элементы в дерево
    }
    cout << endl;

    cout << "Прямой обход:" << endl;
    preorder(root);
    cout << endl;

    cout << "Обратный обход:" << endl;
    postorder(root);
    cout << endl;

    cout << "Симметричный обход:" << endl;
    inorder(root);
    cout << endl;

    cout << "Глубина (высота) дерева: " << height(root) << endl;

    // Поиск узла по значению
    cout << "Какое значение хотите найти в дереве?" << endl;
    cin >> n;
    if (search(root, n)) {
        cout << "Узел со значением \"" << n << "\" найден" << endl;
    } else {
        cout << "Узел со значением \"" << n << "\" не найден" << endl;
    }

    // Удаление узла по значению
    cout << "Какое значение хотите удалить в дереве?" << endl;
    cin >> n;
    cout << "Удаляем узел со значением \"" << n << "\"" << endl;
    root = remove(root, n);
    cout << "Новый обход:" << endl;
    inorder(root);
    cout << endl;

    return 0;
}