---

#include <iostream>
#include <random>
#include <ctime>
#include <cstdlib>
using namespace std;

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

// Добавление нового элемента
ttree *addtree(ttree *proot, int inf)
{
    ttree *nl, *pr = NULL, *ps;
    bool b = false;

    nl = new ttree;
    nl->inf = inf;
    nl->left = NULL;
    nl->rigth = 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->rigth;
    }

    if (b) pr->left = nl;
    else pr->rigth = nl;

    return proot;
}

// Прямой обход: корень - левое - правое
void pretree(ttree *p)
{
    if (p == NULL) return;
    cout << p->inf << "  ";
    pretree(p->left);
    pretree(p->rigth);
}

// Обратный обход: левое - правое - корень
void posttree(ttree *p)
{
    if (p == NULL) return;
    posttree(p->left);
    posttree(p->rigth);
    cout << p->inf << "  ";
}

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

// Поиск элемента с заданным ключом
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->rigth, key, b, inf);
        }
        else
        {
            b = true;
            inf = p->inf;
        }
    }
    return;
}

// Поиск элемента с максимальным ключом
int poiskmaxtree(ttree *p)
{
    while (p->rigth != NULL) p = p->rigth;
    return p->inf;
}

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

// Удаление элемента с заданным ключом
ttree *dellist(ttree *proot, int inf)
{
    ttree *ps = proot, *pr = proot, *w, *v = NULL;

    while ((ps != NULL) && (ps->inf != inf))
    {
        pr = ps;
        if (inf < ps->inf) ps = ps->left;
        else ps = ps->rigth;
    }

    if (ps == NULL) return proot;

    // Если узел не имеет дочерей
    if ((ps->left == NULL) && (ps->rigth == NULL))
    {
        if (ps == pr)
        {
            delete(ps);
            return NULL;
        }
        if (pr->left == ps)
            pr->left = NULL;
        else
            pr->rigth = NULL;
        delete(ps);
        return proot;
    }

    // Если узел имеет дочь только справа
    if (ps->left == NULL)
    {
        if (ps == pr)
        {
            ps = ps->rigth;
            delete(pr);
            return ps;
        }

        if (pr->left == ps)
            pr->left = ps->rigth;
        else
            pr->rigth = ps->rigth;

        delete(ps);
        return proot;
    }

    // Если узел имеет дочь только слева
    if (ps->rigth == NULL)
    {
        if (ps == pr)
        {
            ps = ps->left;
            delete(pr);
            return ps;
        }

        if (pr->left == ps)
            pr->left = ps->left;
        else
            pr->rigth = ps->left;

        delete(ps);
        return proot;
    }

    // Если узел имеет двух дочерей
    w = ps->left;
    if (w->rigth == NULL)
        w->rigth = ps->rigth;
    else
    {
        while (w->rigth != NULL)
        {
            v = w;
            w = w->rigth;
        }
        v->rigth = w->left;
        w->left = ps->left;
        w->rigth = ps->rigth;
    }

    if (ps == pr)
    {
        delete(ps);
        return w;
    }

    if (pr->left == ps)
        pr->left = w;
    else
        pr->rigth = w;

    delete(ps);
    return proot;
}

// Подсчет числа листьев
int countLeaves(ttree *p)
{
    if (p == NULL) return 0;
    if (p->left == NULL && p->rigth == NULL) return 1;
    return countLeaves(p->left) + countLeaves(p->rigth);
}

// Вспомогательная функция для построения сбалансированного дерева
void addBalanced(ttree *&root, int a[], int l, int r)
{
    if (l > r) return;

    int m = (l + r) / 2;
    root = addtree(root, a[m]);

    addBalanced(root, a, l, m - 1);
    addBalanced(root, a, m + 1, r);
}

int main()
{
    srand(time(0)); // чтобы менялись числа при каждом запуске

    ttree *proot = NULL;
    int a[10];

    for (int i = 0; i < 10; i++)
    {
        a[i] = rand() % 101 - 50; // генерация случайного числа
    }

    // Сортировка для построения сбалансированного дерева
    for (int i = 0; i < 9; i++)
    {
        for (int j = i + 1; j < 10; j++)
        {
            if (a[i] > a[j])
            {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
    }

    // Создание сбалансированного дерева поиска
    addBalanced(proot, a, 0, 9);

    cout << "Сгенерированные числа: ";
    for (int i = 0; i < 10; i++)
        cout << a[i] << " ";
    cout << endl;

    cout << "Прямой обход: ";
    pretree(proot);
    cout << endl;

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

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

    cout << "Число листьев в дереве: " << countLeaves(proot) << endl;

    bool b = false;
    int inf = 0;
    poisktree(proot, 0, b, inf);
    if (b) cout << "Элемент 0 найден" << endl;
    else cout << "Элемент 0 не найден" << endl;

    proot = deltree(proot);
    return 0;
}