#include<iostream>
#include"conio.h"
using namespace std;

struct Tree
{
    int number;
    char* FIO;
    Tree* left, * right;
};

void Add(Tree*& root, int num, char* fio);
void Prefiks(Tree*& node);
void Infiks(Tree*& node);
void Postfiks(Tree*& node);
void SearchbyKey(Tree*& node);
void Balance(Tree*& p, Tree** arr, int n, int k);
void Clear(Tree*& p);
void Solution(Tree* r, int& value, int& counter);
Tree* Delete(Tree* node, int inf);
void closestNode(Tree*& root, int sredn, Tree*&);


int main()
{
    setlocale(LC_ALL, "rus");
    int choice, num, count = 0, t = 0, key = 0, value = 0, counter = 0, srdn = 0;
    char fio[36];
    Tree* root = nullptr;
    Tree* result = nullptr;
    Tree** arr = new Tree * [count];
    while (true)
    {
        cout << "1.Добавить элемент в дерево\n2.Найти элемент по ключу\n3.Удалить элемент по ключу\n4.Сбалансировать дерево\n5.Префиксный просмотр (сверху вниз)\n6.Инфиксный просмотр (слева направо)\n7.Постфиксный просмотр (снизу вверх)\n8.Задание\n9.Выход" << endl;
        cin >> choice;
        switch (choice)
        {
        case 1:
            cout << "Введите ФИО: ";
            cin.ignore();
            cin.getline(fio, 36);
            cout << "Введите номер: ";
            cin >> num;
            Add(root, num, fio);
            break;
        case 2:
            SearchbyKey(root);
            _getch();
            break;
        case 3:
            cout << "Введите ключ";
            cin >> key;
            Delete(root, key);
            break;
        case 4:
            Balance(root, arr, 0, count);
            cout << "Дерево сбалансированно" << endl;
            _getch();
        case 5:
            if (root == NULL)
            {
                cout << "Дерево пустое" << endl;
            }
            Prefiks(root);
            _getch();
            break;
        case 6:
            if (root == NULL)
            {
                cout << "Дерево пустое" << endl;
            }
            Infiks(root);
            _getch();
            break;
        case 7:
            if (root == NULL)
            {
                cout << "Дерево пустое" << endl;
            }
            Postfiks(root);
            _getch();
            break;
        case 8:
            Solution(root, value, counter);
            srdn = value / counter;
            cout << "Среднее значение узлов равно ";
            cout << srdn << endl;
            result = root;
            closestNode(root, srdn, result);
            cout << "Ближайшая строка к среднему значению: ";
            cout << "ФИО: " << result->FIO << ", " << "номер: " << result->number << endl;
            _getch();
            break;
        case 9:
            cout << "Программа завершена" << endl;
            delete[] arr;
            Clear(root);
            break;
        default:
            cout << "Повторите еще раз" << endl;
        }
        system("cls");
    }
}
void Add(Tree*& root, int num, char* fio)
{
    if (root == NULL)
    {
        root = new Tree;
        root->number = num;
        root->FIO = fio;
        root->left = root->right = NULL;
    }
    if (num > root->number)
    {
        Add(root->right, num, fio);
    }
    else if (num < root->number)
    {
        Add(root->left, num, fio);
    }
}

void Prefiks(Tree*& node)
{
    if (node != NULL)
    {
        cout << "ФИО: " << node->FIO << ", " << "номер: " << node->number << endl;;
        Prefiks(node->left);
        Prefiks(node->right);
    }

}

void Infiks(Tree*& node)
{
    if (node != NULL)
    {
        Infiks(node->left);
        cout << "ФИО: " << node->FIO << ", " << "номер: " << node->number << endl;;
        Infiks(node->right);
    }

}

void Postfiks(Tree*& node)
{
    if (node != NULL)
    {
        Postfiks(node->left);
        Postfiks(node->right);
        cout << "ФИО: " << node->FIO << ", " << "номер: " << node->number << endl;
    }

}

void SearchbyKey(Tree*& node)
{
    Tree* a = node;
    int key;
    bool search = false;
    cout << "Введите ключ" << endl;
    cin >> key;
    while (a != NULL)
    {
        if (a->number > key)
        {
            a = a->right;
        }
        else if (a->number < key)
        {
            a = a->left;
        }
        else
        {
            search = true;
            cout << "ФИО: " << a->FIO << ", " << "Номер:" << a->number << endl;
            break;
        }
    }
    if (!search)
    {
        cout << "Такого ключа нет" << endl;
    }
}

void Balance(Tree*& p, Tree** arr, int n, int k)
{
    if (n == k)
    {
        p = NULL;
        return;
    }
    else
    {
        int m = (n + k) / 2;
        p = arr[m];
        Balance(p->left, arr, n, m);
        Balance(p->right, arr, m + 1, k);
    }
}

void Clear(Tree*& p)
{
    if (p == NULL) return;
    Clear(p->left);
    Clear(p->right);
    delete(p);
    p = NULL;
}

Tree* Delete(Tree* node, int inf)
{
    Tree* ps = node, * pr = node, * w = nullptr, * v = nullptr;
    // Поиск удаляемого узла
    while ((ps != NULL) && (ps->number != inf))
    {
        pr = ps;
        if (inf < ps->number)
        {
            ps = ps->left;
        }
        else
        {
            ps = ps->right;
        }
    }
    if (ps == NULL)
    {
        return node; // Если узел не найден
    }

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

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

    // Если узел имеет дочь только слева
    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 node;
    }

    // Если узел имеет двух дочерей
    w = ps->left;
    if (w->right == NULL) // Если максимальный следует за ps
    {
        w->right = ps->right;
    }

    else   // Если максимальный не следует за ps
    {
        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 node;
}

void Solution(Tree* r, int& value, int& counter)
{
    if (r)
    {
        value += r->number;
        ++counter;
        Solution(r->left, value, counter);
        Solution(r->right, value, counter);
    }
}

void closestNode(Tree*& root, int sredn, Tree*& result)
{
    if (root == NULL)
    {
        return;
    }
    if (abs(root->number - sredn) < abs(result->number - sredn))
    {
        result = root;
    }
    if (sredn < root->number)
    {
        closestNode(root->left, sredn, result);
    }
    else
    {
        closestNode(root->right, sredn, result);
    }

}