---

#include <iostream>
using namespace std;

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;
}

void wrtree(ttree *p) {
    if (p == NULL) return;
    wrtree(p->left);
    cout << p->inf << " ";
    wrtree(p->right);
}

void wrtree_reverse(ttree *p) {
    if (p == NULL) return;
    wrtree_reverse(p->right);
    cout << p->inf << " ";
    wrtree_reverse(p->left);
}

void wrtree_desc(ttree *p) {
    if (p == NULL) return;
    wrtree_desc(p->right);
    cout << p->inf << " ";
    wrtree_desc(p->left);
}

bool searchtree(ttree *p, int key, int &inf) {
    if (p == NULL) return false;
    if (p->inf == key) {
        inf = p->inf;
        return true;
    }
    if (key < p->inf) return searchtree(p->left, key, inf);
    else return searchtree(p->right, key, inf);
}

ttree *delete_branch(ttree *proot, int key) {
    if (proot == NULL) return NULL;
    if (proot->inf == key) {
        ttree *temp = proot->left;
        ttree *temp2 = proot->right;
        delete proot;
        if (temp) {
            ttree *ps = temp;
            while (ps->right != NULL) ps = ps->right;
            ps->right = temp2;
            return temp;
        }
        return temp2;
    }
    if (key < proot->inf)
        proot->left = delete_branch(proot->left, key);
    else
        proot->right = delete_branch(proot->right, key);
    return proot;
}

ttree *deltree(ttree *p) {
    if (p == NULL) return NULL;
    deltree(p->left);
    deltree(p->right);
    delete p;
    return NULL;
}

int main() {
    ttree *root = NULL;
    int nums[] = {10, -20, 30, -40, 0, 25, -5, 15, 45, -30, 20, 5, -10, 35, -15};
    for (int i = 0; i < 15; i++) {
        root = addtree(root, nums[i]);
    }

    cout << "Прямой обход (возрастание): ";
    wrtree(root);
    cout << endl;

    cout << "Обратный обход (убывание): ";
    wrtree_desc(root);
    cout << endl;

    cout << "Обход в порядке возрастания: ";
    wrtree(root);
    cout << endl;

    int key = 25;
    cout << "Удаление ветви с вершиной " << key << endl;
    root = delete_branch(root, key);

    cout << "Прямой обход после удаления: ";
    wrtree(root);
    cout << endl;

    int searchKey = 15;
    int foundInf;
    if (searchtree(root, searchKey, foundInf))
        cout << "Найден ключ: " << foundInf << endl;
    else
        cout << "Ключ " << searchKey << " не найден" << endl;

    root = deltree(root);
    return 0;
}