siaod_lr2

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

#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 initTree(char _key)
{
    NODEPTR newNODEPTR = new NODE;  // Создание нового узла
    newNODEPTR->key = _key;
    newNODEPTR->left = NULL;
    newNODEPTR->right = NULL;
    return newNODEPTR;
}

// Поиск с включением
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 (_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)
{
    int tmp = 0;
    if (Root == NULL) return 0;
    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)
{
    int result = rand() % N;
    return (char)result;
}

// ФУНКЦИЯ ФОРМИРОВАНИЯ СЛУЧАЙНОГО МАССИВА ДАННЫХ
int formRandCharArray(Data* data)
{
    char tmp = NULL;
    int i = 0;

    while (i < data->size)
    {
        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);

    Tree = initTree(Array.mas[0]);

    for (int i = 1; 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)];
    //char tmp = Array.mas[0];
    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;
}