---

#include <iostream>
#include <cstdlib>
#include <ctime>

struct ttree {
    int inf;
    ttree *left;
    ttree *right;
};

// Добавление элемента в дерево поиска
ttree* addtree(ttree *proot, int inf) {
    ttree *nl = new ttree;
    nl->inf = inf;
    nl->left = NULL;
    nl->right = NULL;
    if (proot == NULL) return nl;

    ttree *ps = proot, *pr;
    bool b;
    while (ps != NULL) {
        pr = ps;
        b = (inf < ps->inf);
        if (b) ps = ps->left;
        else ps = ps->right;
    }
    if (b) pr->left = nl;
    else pr->right = nl;
    return proot;
}

// Создание сбалансированного дерева из отсортированного массива
ttree* createBalanced(int arr[], int start, int end) {
    if (start > end) return NULL;
    int mid = (start + end) / 2;
    ttree *root = new ttree;
    root->inf = arr[mid];
    root->left = createBalanced(arr, start, mid - 1);
    root->right = createBalanced(arr, mid + 1, end);
    return root;
}

// Прямой обход (Корень -> Левое -> Правое)
void preorder(ttree *p) {
    if (p == NULL) return;
    std::cout << p->inf << " ";
    preorder(p->left);
    preorder(p->right);
}

// Обратный обход (Левое -> Правое -> Корень)
void postorder(ttree *p) {
    if (p == NULL) return;
    postorder(p->left);
    postorder(p->right);
    std::cout << p->inf << " ";
}

// Симметричный обход (по возрастанию)
void inorder(ttree *p) {
    if (p == NULL) return;
    inorder(p->left);
    std::cout << p->inf << " ";
    inorder(p->right);
}

// Поиск узла и его родителя по ключу
ttree* findParent(ttree* root, int key, ttree** parent) {
    ttree* current = root;
    *parent = NULL;
    while (current != NULL && current->inf != key) {
        *parent = current;
        if (key < current->inf)
            current = current->left;
        else
            current = current->right;
    }
    return current;
}

// Удаление всей ветви (поддерева) начиная с узла
void deleteSubtree(ttree* node) {
    if (node == NULL) return;
    deleteSubtree(node->left);
    deleteSubtree(node->right);
    delete node;
}

// Удаление ветви с вершиной, имеющей заданный ключ
ttree* deleteBranch(ttree* root, int key) {
    ttree* parent = NULL;
    ttree* target = findParent(root, key, &parent);

    if (target == NULL) {
        std::cout << "Ключ " << key << " не найден в дереве.\n";
        return root;
    }

    // Если удаляется корень
    if (parent == NULL) {
        deleteSubtree(target);
        return NULL;
    }

    // Отсоединяем узел от родителя
    if (parent->left == target)
        parent->left = NULL;
    else
        parent->right = NULL;

    // Удаляем всё поддерево
    deleteSubtree(target);
    
    std::cout << "Ветвь с ключом " << key << " удалена.\n";
    return root;
}

// Удаление всего дерева (для очистки памяти)
void deltree(ttree *p) {
    if (p == NULL) return;
    deltree(p->left);
    deltree(p->right);
    delete p;
}

int main() {
    setlocale(LC_ALL, "Russian");
    
    // Создаём массив чисел от -50 до 50
    const int SIZE = 101;
    int arr[SIZE];
    for (int i = 0; i < SIZE; i++) {
        arr[i] = -50 + i;
    }

    // Строим сбалансированное дерево
    ttree *root = createBalanced(arr, 0, SIZE - 1);

    std::cout << "Симметричный обход (по возрастанию):\n";
    inorder(root);
    std::cout << "\n\n";

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

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

    // Выполнение индивидуального задания №3
    int key;
    std::cout << "Введите ключ вершины, ветвь которой нужно удалить: ";
    std::cin >> key;

    root = deleteBranch(root, key);

    std::cout << "\nДерево после удаления ветви (симметричный обход):\n";
    inorder(root);
    std::cout << "\n";

    // Очистка памяти
    deltree(root);
    
    return 0;
}