---

#include <iostream>
using namespace std;

// Структура узла бинарного дерева поиска (как в лекции)
struct ttree {
    int inf;
    ttree *left;
    ttree *right;
};

/* Функции из лекции (с исправлением опечаток: tree заменено на ttree) */

// Добавление нового элемента
ttree *addtree(ttree *proot, int inf) {
    ttree *nl, *pr, *ps;
    bool b;
    nl = new ttree;
    nl->inf = inf;
    nl->left = NULL;
    nl->right = NULL;
    if (proot == NULL) return nl;
    ps = proot;
    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;
}

// Обход дерева в порядке возрастания (inorder) из лекции
void wrtree(ttree *p) {
    if (p == NULL) return;
    wrtree(p->left);
    cout << p->inf << " ";
    wrtree(p->right);
}

// Прямой обход (preorder) – требуется заданием
void preorder(ttree *p) {
    if (p == NULL) return;
    cout << p->inf << " ";
    preorder(p->left);
    preorder(p->right);
}

// Обратный обход (postorder) – требуется заданием
void postorder(ttree *p) {
    if (p == NULL) return;
    postorder(p->left);
    postorder(p->right);
    cout << p->inf << " ";
}

// Поиск элемента с заданным ключом (исправлено: ttree вместо tree)
void poisktree(ttree *p, int key, bool &b, int &inf) {
    if ((p != NULL) && (b != true)) {
        if (p->inf != key) {
            poisktree(p->left, key, b, inf);
            poisktree(p->right, key, b, inf);
        } else {
            b = true;
            inf = p->inf;
        }
    }
}

// Поиск максимального ключа (исправлено: ttree вместо tree)
int poiskmaxtree(ttree *p) {
    while (p->right != NULL) p = p->right;
    return p->inf;
}

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

// Удаление элемента с заданным ключом (из лекции)
ttree *dellist(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;
}

/* Функция для индивидуального задания №2: подсчёт числа листьев */
int count_leaves(ttree *p) {
    if (p == NULL) return 0;
    if (p->left == NULL && p->right == NULL) return 1;
    return count_leaves(p->left) + count_leaves(p->right);
}

/* Построение сбалансированного дерева из отсортированного массива */
ttree* build_balanced(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 = build_balanced(arr, start, mid - 1);
    root->right = build_balanced(arr, mid + 1, end);
    return root;
}

int main() {
    // Диапазон чисел от -50 до +50
    const int N = 101;
    int arr[N];
    for (int i = 0; i < N; ++i)
        arr[i] = -50 + i;

    // Создание сбалансированного дерева поиска
    ttree *proot = build_balanced(arr, 0, N - 1);

    // Вывод обходов, требуемых заданием
    cout << "Прямой обход: ";
    preorder(proot);
    cout << endl;

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

    cout << "В порядке возрастания (inorder): ";
    wrtree(proot);
    cout << endl;

    // Индивидуальное задание: подсчёт числа листьев
    int leaves = count_leaves(proot);
    cout << "Число листьев в дереве: " << leaves << endl;

    // Демонстрация работы функций добавления, поиска и удаления
    proot = addtree(proot, 100);
    cout << "После добавления 100 (inorder): ";
    wrtree(proot);
    cout << endl;

    bool found = false;
    int found_inf;
    poisktree(proot, 100, found, found_inf);
    if (found)
        cout << "Элемент 100 найден: " << found_inf << endl;
    else
        cout << "Элемент 100 не найден" << endl;

    found = false;
    poisktree(proot, -25, found, found_inf);
    if (found)
        cout << "Элемент -25 найден: " << found_inf << endl;
    else
        cout << "Элемент -25 не найден" << endl;

    proot = dellist(proot, 100);
    cout << "После удаления 100 (inorder): ";
    wrtree(proot);
    cout << endl;

    // Освобождение всей выделенной памяти
    proot = deltree(proot);

    return 0;
}