#include <iostream>
#include <Windows.h>
#include <ctime>
#include <iomanip>

// ASCii коды русских букв
#define char_A 'А'
#define char_R 'Я'
#define char_a 'а'
#define char_r 'я'

int maximum(int a, int b) // функция выбора максимального числа
{
    if (a > b) return a;
    else return b;
}

int minimum(int a, int b) // функция выбора минимального числа
{
    if (a > b) return b;
    else return a;
}

struct NODE // узел
{
    char key; // ключ
    NODE* left; // левый дочерний узел
    NODE* right; // правый дочерний узел
};

typedef NODE* NODEPTR; // указатель на узел

NODEPTR searchInsert(NODEPTR *Root, char _key) // поиск/вставка нового узла
{
    // если узел существует, то осуществляется его поиск
    // если узел не найден, создается новый
    NODEPTR tmp = *Root;
    NODEPTR prev = NULL;
    bool found = false;

    // поиск узла
    while ((tmp != NULL) && (found == false))
    {
        prev = tmp; // запоминание предыдущего узла
        if (_key == tmp->key) // если найден
            found = true;
        else
        {
            // переходим в соответствующее поддерево
            if (_key < tmp->key) tmp = tmp->left;
            else  tmp = tmp->right;
        }
    }
    if (found)
        return tmp; // возврат указателя на найденный узел

    // создание нового узла
    NODEPTR newNODEPTR = new NODE;
    newNODEPTR->key = _key;
    newNODEPTR->left = NULL;
    newNODEPTR->right = NULL;

    // если узел корневой
    if (prev == NULL)
    {
        // запись в корень дерева
        *Root = newNODEPTR;
        return newNODEPTR;
    }

    if (_key < prev->key)
        // присоединение к левому  поддереву предка
        prev->left = newNODEPTR;
    else
        // присоединение к правому поддереву предка
        prev->right = newNODEPTR;

    // возврат указателя на новый узел
    return newNODEPTR;
}

int getNodeCount(NODEPTR Root) // нахождение числа узлов
{
    if (Root == NULL) return 0;
    else return getNodeCount(Root->left) + getNodeCount(Root->right) + 1;
}

bool isVowel(char _key) // фукнкция, определяющая является ли буква гласной
{
    char mas[18] = { 'А', 'а', 'У', 'у', 'О', 'о', 'Ы', 'ы', 'И', 'и', 'Э', 'э', 'Я', 'я', 'Ю', 'ю', 'Е', 'е' };
    for (int i = 0; i < 18; i++)
    {
        if (_key == mas[i]) return true;
    }
    return false;
}

int getVowelCount(NODEPTR Root, int level) // нахождение гласных на отстоящих на 1 уровнях
{
    int tmp = 0;
    if (Root == NULL) return 0;
    // если уровень четный и буква - гласная, то запоминаем 1
    if ((level % 2 == 0) && (isVowel(Root->key) == true)) tmp = 1;
    return getVowelCount(Root->left, level + 1) + getVowelCount(Root->right, level + 1) + tmp;
}

int getMaxTreeHeight(NODEPTR Root) // функция определения максимальной высоты дерева
{
    if (Root == NULL)
        return 0;
    return 1 + maximum(getMaxTreeHeight(Root->left), getMaxTreeHeight(Root->right));
}

int getMinTreeHeight(NODEPTR Root)  // функция определения минимальной высоты дерева
{
    if (Root == NULL)
        return 0;
    return 1 + minimum(getMinTreeHeight(Root->left), getMinTreeHeight(Root->right));
}

void printTree(NODEPTR Root, int level) // печать дерева в консоль
{
    if (Root != NULL)
    {
        printTree(Root->right, level + 1); // вывод левого поддерева
        for (int i = 0; i < level; i++) std::cout << "   ";
        std::cout << Root->key << std::endl; // вывод корня поддерева
        printTree(Root->left, level + 1); // вывод правого поддерева
    }
}

void traverseSymmetricTree(NODEPTR Root) // симметричный обход дерева
{
    if (Root == NULL) return;
    else
    {
        traverseSymmetricTree(Root->left);
        std::cout << Root->key << " ";
        traverseSymmetricTree(Root->right);
    }
}

void deleteTree(NODEPTR* Root) // удаление поддерева
{
    NODEPTR tmp = *Root;
    if (*Root == NULL) return;

    deleteTree(&(tmp)->left); // удаление левого поддерева
    deleteTree(&(tmp)->right); // удаление правого поддерева
    delete *Root; // удаление узла
    *Root = NULL;
    return;
}

int deleteNode(NODEPTR* Root, char _key) // удаление узла и перестройка дерева
{
    NODEPTR tmp = *Root;
    NODEPTR prev = NULL;
    bool found = false;
    bool isLeftChild = false;

    // поиск узла
    while ((tmp != NULL) && (found == false))
    {
        if (_key == tmp->key)
        {
            // найден искомый узел
            found = true;
            break;
        }
        prev = tmp; // запоминаем предыдущий
        if (_key < tmp->key)
        {
            // ищем искомый узел в левом поддереве
            tmp = tmp->left;
            isLeftChild = true;
        }
        else
        {
            // ищем искомый узел в правом поддереве
            tmp = tmp->right;
            isLeftChild = false;
        }
    }
    // если узел не найден - выход из функции
    if (found == false) return -1;

    // анализируем число потомков найденного узла
    // если нет потомков
    if ((tmp->left == NULL) && (tmp->right == NULL))
    {
        deleteTree(&tmp);
        if (prev == NULL) // если узел - корневой
        {
            *Root = NULL;
            return 0;
        }
        if (isLeftChild == true) prev->left = NULL;
        else prev->right = NULL;
        return 0;
    }
    // если есть оба потомка
    if ((tmp->left != NULL) && (tmp->right != NULL))
    {
        NODEPTR foundNode = tmp;
        tmp = tmp->right;
        while (tmp->left != NULL)
        {
            tmp = tmp->left;
        }
        tmp->left = foundNode->left;
        if (prev == NULL)
        {
            *Root = foundNode->right;
            delete foundNode;
            return 0;
        }
        if (isLeftChild == true) prev->left = foundNode->right;
        else prev->right = foundNode->right;
        delete foundNode;
        return 0;
    }
    // если есть только левый потомок
    if (tmp->left != NULL)
    {
        if (prev == NULL)
        {
            *Root = tmp->left;
            delete tmp;
            return 0;
        }
        if (isLeftChild == true) prev->left = tmp->left;
        else prev->right = tmp->left;
        return 0;
    }
    // если есть только правый потомок
    if (tmp->right != NULL)
    {
        if (prev == NULL)
        {
            *Root = tmp->right;
            delete tmp;
            return 0;
        }
        if (isLeftChild == true) prev->left = tmp->right;
        else prev->right = tmp->right;
        return 0;
    }

    return 0;
}

struct DATA // структура данных
{
    char* mas; // массив букв
    int size;  // размер массива
};

typedef struct DATA Data; // определение типа "данные"

char random(int N) // функция нахождения числа в промежутке [0; N - 1]
{
    int result = rand() % N;
    return (char)result;
}

int formRandCharArray(Data* data) // функция формирования случайного массива данных - последовательности русских букв
{
    char tmp = NULL;
    int i = 0;

    while (i < data->size)
    {
        // coin - выбор размера буквы: заглавная или прописная
        int coin = random(2);
        if (coin == 0)
        {
            // случайная заглавная буква
            tmp = char_A + random(char_R - char_A + 1);
        }
        else
        {
            // случайная прописная буква
            tmp = char_a + random(char_r - char_a + 1);
        }
        // запись в массив
        data->mas[i] = tmp;
        i++;
    }
    return 0;
}

void printMas(Data& data) // функция вывода данных на экран
{
    for (int i = 0; i < data.size; i++)
        std::cout << data.mas[i] << ' ';
    std::cout << '\n';
}

int main()
{
    system("color F0");
    setlocale(LC_ALL, "RUS");

    srand(time(NULL));

    // новое дерево
    NODEPTR Tree = NULL;
    // данные - последовательность русских букв
    Data Array{ NULL, 18 };

    Array.mas = new char[Array.size];

    // формирование последовательности русских букв
    formRandCharArray(&Array);

    std::cout << "Массив случайных букв русского языка: "; printMas(Array);

    // вставка массива русских букв в дерево
    for (int i = 0; i < Array.size; i++)
    {
        searchInsert(&Tree, Array.mas[i]);
    }

    std::cout << "\n*****************************************************\n";
    std::cout << "\nРезультирующее бинарное дерево поиска: \n\n";
    printTree(Tree, 0); // вывод дерева
    std::cout << "\nМаксимальная высота: " << getMaxTreeHeight(Tree) << ", Минимальная высота: " << getMinTreeHeight(Tree) << ", Число узлов: " << getNodeCount(Tree) << ", Число гласных букв (на четных уровнях): " << getVowelCount(Tree,1) << "\n";

    std::cout << "\nСимметричный обход дерева: ";
    traverseSymmetricTree(Tree); // обход дерева
    std::cout << "\n";

    // выбор случайной буквы на удаление из массива
    char tmp = Array.mas[random(Array.size)];
    std::cout << "\nУдаление узла '" << tmp << "' из дерева\n";
    deleteNode(&Tree, tmp); // удаление выбранной буквы

    std::cout << "\nИзмененное бинарное дерево поиска: \n\n";
    printTree(Tree, 0); // вывод измененного дерева

    std::cout << "\n\n*****************************************************\n";

    // удаление дерева
    deleteTree(&Tree);

    // удаление данных
    delete[] Array.mas;
}