Лаба 3 ЯМП

/*
19. Существует способ проверить, является ли один узел истинным
предком другого узла, который основан на следующем правиле : узел
m является истинным предком узла n, если узел m предшествует узлу
n при обходе дерева в X порядке, но следует за узлом n при обходе в Y
порядке.Где X и Y выбираются из множества обходов{ прямом,
обратном и симметричном }. Определите все возможные пары X и Y,
когда это правило справедливо.
*/

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

using namespace std;

struct Node
{
    int Key;
    int Count;
    Node* Left;
    Node* Right;
};

Node* tree;

int Initial(Node*&);
void Search(Node*&, int);
void Traversal_Straight(Node*, int*, int&);
void Traversal_Back(Node*, int*, int&);
void Traversal_Symmetric(Node*, int*, int&);
void Output(Node*, int l);
bool compare(int, int, int*, int*, int);

int main()
{
    int q;

    do
    {
        SetConsoleOutputCP(1251);
        SetConsoleCP(1251);

        int size = Initial(tree);//создаем дерево и узнаем количество узлов в нем
        cout << "Вывод дерева:" << endl;
        Output(tree, 0);
        int* arr1 = new int[size];//создаем массив под значения элементов при прямом обходе
        int* arr2 = new int[size];//при обратном
        int* arr3 = new int[size];//при симметричном

        int i = 0;

        Traversal_Straight(tree, arr1, i);
        cout << "Прямой порядок обхода:" << endl;
        for (int j = 0; j < size; j++)
            cout << arr1[j] << '\t';
        cout << endl;
        i = 0;
        Traversal_Back(tree, arr2, i);
        cout << "Обратный порядок обхода:" << endl;
        for (int j = 0; j < size; j++)
            cout << arr2[j] << '\t';
        cout << endl;
        i = 0;
        Traversal_Symmetric(tree, arr3, i);
        cout << "Симметричный порядок обхода:" << endl;
        for (int j = 0; j < size; j++)
            cout << arr3[j] << '\t';
        cout << endl;

        int n, m;
        cout << "Проверка: является ли узел истинным предком другого узла:" << endl;
        cout << "Введите предка:" << endl;
        cin >> m;
        cout << "Введите потомка:" << endl;
        cin >> n;

        cout << "Прямой и обратный обходы: ";
        if (compare(m, n, arr1, arr2, size))
            cout << "Справедливо" << endl;
        else cout << "Неверно" << endl;
        cout << "Обратный и прямой обходы: ";
        if (compare(m, n, arr2, arr1, size))
            cout << "Справедливо" << endl;
        else cout << "Неверно" << endl;

        cout << "Прямой и симметричный обходы: ";
        if (compare(m, n, arr1, arr3, size))
            cout << "Справедливо" << endl;
        else cout << "Неверно" << endl;
        cout << "Симметричный и прямой обходы: ";
        if (compare(m, n, arr3, arr1, size))
            cout << "Справедливо" << endl;
        else cout << "Неверно" << endl;

        cout << "Обратный и симметричный обходы: ";
        if (compare(m, n, arr2, arr3, size))
            cout << "Справедливо" << endl;
        else cout << "Неверно" << endl;
        cout << "Симметричный и обратный обходы: ";
        if (compare(m, n, arr3, arr2, size))
            cout << "Справедливо" << endl;
        else cout << "Неверно" << endl;

        cout << "0. Выход" << endl;
        cin >> q;
    } while (q != 0);
}

int Initial(Node*& tree)
{
    int elem;
    int size = 0;
    tree = nullptr;
    cout << "Введите ключи дерева:" << endl;
    cin >> elem;
    while (elem != 0)
    {
        size++;
        Search(tree, elem);
        cin >> elem;
    }

    return size;
}

void Search(Node*& tree, int elem)
{
    if (tree == nullptr)
    {
        tree = new Node;
        tree->Key = elem;
        tree->Count = 1;
        tree->Left = tree->Right = nullptr;
    }
    else
    {
        if (elem < tree->Key)
        {
            Search(*&tree->Left, elem);
        }
        else if (elem > tree->Key)
        {
            Search(*&tree->Right, elem);
        }
        else tree->Count++;
    }
}

void Traversal_Straight(Node* tree, int* arr1, int& i)
{
    if (tree != nullptr)
    {
        arr1[i] = tree->Key;
        i++;
        Traversal_Straight(tree->Left, arr1, i);
        Traversal_Straight(tree->Right, arr1, i);
    }
}

void Traversal_Back(Node* tree, int* arr2, int& i)
{
    if (tree != nullptr)
    {
        Traversal_Back(tree->Left, arr2, i);
        Traversal_Back(tree->Right, arr2, i);
        arr2[i] = tree->Key;
        i++;
    }
}

void Traversal_Symmetric(Node* tree, int* arr3, int& i)
{
    if (tree != nullptr)
    {
        Traversal_Symmetric(tree->Left, arr3, i);
        arr3[i] = tree->Key;
        i++;
        Traversal_Symmetric(tree->Right, arr3, i);
    }
}

void Output(Node* tree, int l)
{
    if (tree != nullptr)
    {
        Output(tree->Right, l + 1);
        for (int i = 1; i <= l; i++)
            cout << "     ";
        cout << tree->Key << endl;
        Output(tree->Left, l + 1);
    }
}

bool compare(int m, int n, int* arr1, int* arr2, int size)
{
    bool m_parent = false;
    bool n_child = false;
    for (int i = 0; i < size - 1; i++)
    {
        if (m == arr1[i])
            if (n == arr1[i + 1])
                m_parent = true;
        if (n == arr2[i])
            if (m == arr2[i + 1])
                n_child = true;
    }

    return (m_parent && n_child);
}