---

#include <iostream>
#include <random>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <algorithm>
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 wrtree(ttree *p)
{
    if (p == NULL) return;
    wrtree(p->left);
    cout << p->inf << "  ";
    wrtree(p->rigth);
}

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

ttree *deltree(ttree *p)
{
    if (p == NULL) return NULL;
    deltree(p->left);
    deltree(p->rigth);
    delete p;
    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;
}

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

void sumAndCount(ttree *p, long long &sum, int &cnt)
{
    if (p == NULL) return;
    sum += p->inf;
    cnt++;
    sumAndCount(p->left, sum, cnt);
    sumAndCount(p->rigth, sum, cnt);
}

void findClosest(ttree *p, double avg, int &bestVal, double &bestDiff, bool &found)
{
    if (p == NULL) return;

    double d = fabs(p->inf - avg);
    if (!found || d < bestDiff)
    {
        bestDiff = d;
        bestVal = p->inf;
        found = true;
    }

    findClosest(p->left, avg, bestVal, bestDiff, found);
    findClosest(p->rigth, avg, bestVal, bestDiff, found);
}

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;

    long long sum = 0;
    int cnt = 0;
    sumAndCount(proot, sum, cnt);

    double avg = 0.0;
    if (cnt > 0) avg = static_cast<double>(sum) / cnt;

    int bestVal = 0;
    double bestDiff = 0.0;
    bool found = false;
    findClosest(proot, avg, bestVal, bestDiff, found);

    cout << "Среднее значение всех ключей: " << avg << endl;
    if (found)
        cout << "Узел с ближайшим ключом: " << bestVal << endl;

    bool b = false;
    int inf = 0;
    poisktree(proot, a[0], b, inf);
    if (b) cout << "Проверка поиска: элемент " << inf << " найден" << endl;
    else cout << "Проверка поиска: элемент не найден" << endl;

    proot = dellist(proot, a[0]);
    cout << "После удаления одного элемента, обход по возрастанию: ";
    wrtree(proot);
    cout << endl;

    proot = deltree(proot);
    return 0;
}