---

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

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

ttree* addtree(ttree *proot, int inf) {
    ttree *nl = new ttree{inf, NULL, 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* findParent(ttree* root, int key, ttree** parent) {
    ttree* cur = root;
    *parent = NULL;
    while (cur && cur->inf != key) {
        *parent = cur;
        if (key < cur->inf) cur = cur->left;
        else cur = cur->right;
    }
    return cur;
}

void delSub(ttree* node) {
    if (!node) return;
    delSub(node->left);
    delSub(node->right);
    delete node;
}

ttree* deleteBranch(ttree* root, int key) {
    ttree *par, *tgt = findParent(root, key, &par);
    if (!tgt) { std::cout << "Не найден\n"; return root; }
    if (!par) { delSub(tgt); return NULL; }
    if (par->left == tgt) par->left = NULL;
    else par->right = NULL;
    delSub(tgt);
    std::cout << "Ветвь с ключом " << key << " удалена\n";
    return root;
}

void print(ttree* p) {
    if (!p) return;
    print(p->left);
    std::cout << p->inf << " ";
    print(p->right);
}

int main() {
    setlocale(LC_ALL, "Russian");
    srand(time(0));
    
    ttree *root = NULL;
    int nums[10];
    
    std::cout << "Исходные числа: ";
    for (int i = 0; i < 10; i++) {
        nums[i] = rand() % 101 - 50;  // от -50 до +50
        std::cout << nums[i] << " ";
        root = addtree(root, nums[i]);
    }
    
    std::cout << "\nДерево (по возрастанию): ";
    print(root);
    
    std::cout << "\nВведите ключ для удаления ветви: ";
    int key;
    std::cin >> key;
    
    root = deleteBranch(root, key);
    
    std::cout << "Итог: ";
    print(root);
    std::cout << "\n";
    
    return 0;
}