---

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

int find_max(ttree *p) {
    while (p->right != NULL) p = p->right;
    return p->inf;
}

ttree *delete_node(ttree *proot, int inf) {
    ttree *ps = proot, *pr = proot, *w, *v;
    while ((ps != NULL) && (ps->inf != inf)) {
        pr = ps;
        if (inf < ps->inf) ps = ps->left;
        else ps = ps->right;
    }
    if (ps == NULL) return proot;
    if ((ps->left == NULL) && (ps->right == NULL)) {
        if (ps == pr) {
            delete ps;
            return NULL;
        }
        if (pr->left == ps) pr->left = NULL;
        else pr->right = NULL;
        delete ps;
        return proot;
    }
    if (ps->left == NULL) {
        if (ps == pr) {
            ps = ps->right;
            delete pr;
            return ps;
        }
        if (pr->left == ps) pr->left = ps->right;
        else pr->right = ps->right;
        delete ps;
        return proot;
    }
    if (ps->right == NULL) {
        if (ps == pr) {
            ps = ps->left;
            delete pr;
            return ps;
        }
        if (pr->left == ps) pr->left = ps->left;
        else pr->right = ps->left;
        delete ps;
        return proot;
    }
    w = ps->left;
    if (w->right == NULL) {
        w->right = ps->right;
    } else {
        while (w->right != NULL) {
            v = w;
            w = w->right;
        }
        v->right = w->left;
        w->left = ps->left;
        w->right = ps->right;
    }
    if (ps == pr) {
        delete ps;
        return w;
    }
    if (pr->left == ps) pr->left = w;
    else pr->right = w;
    delete ps;
    return proot;
}

ttree *delete_max_in_left_branch(ttree *proot) {
    if (proot == NULL) return NULL;
    if (proot->left == NULL) return proot;
    int max_key = find_max(proot->left);
    proot->left = delete_node(proot->left, max_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;

    cout << "Максимальный ключ в левой ветви: " << find_max(root->left) << endl;

    cout << "Удаление узла с максимальным ключом из левой ветви и всех связанных с ним узлов" << endl;
    root = delete_max_in_left_branch(root);

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