---

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

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

// Добавление нового элемента

ttree *addtree(ttree *proot, int inf)
{
    ttree *nl, *pr, *ps;
    bool b;

    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;

    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[101];

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

    sort(a, a + 101);

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

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