Binary tree

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

using namespace std;

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

Node* tree;

void Initial(Node*&);
void Search(Node*&, int);
void Traversal_Straight(Node*);
void Traversal_Back(Node*);
void Traversal_Symmetric(Node*);
int Height(Node*);
void Clean(Node*);
void Output(Node*, int l);
void Delete_1(Node*&, Node*&);
void Delete(Node*&, int);
Node* Search_Elem(Node*, int);

int main()
{
    int q;

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

        cout << "Выберите действие:" << endl;
        cout << "1. Инициализация дерева" << endl;
        cout << "2. Прямой обход дерева" << endl;
        cout << "3. Обратный обход дерева" << endl;
        cout << "4. Симметричный обход дерева" << endl;
        cout << "5. Определить высоту дерева" << endl;
        cout << "6. Очистить дерево" << endl;
        cout << "7. Вывод дерева" << endl;
        cout << "8. Добавить вершину" << endl;
        cout << "9. Удалить вершину" << endl;
        cout << "10. Найти адресс вершины с нужным значеним" << endl;
        cout << "0. Выход" << endl;
        cin >> q;
        if (q == 1)
            Initial(tree);
        else if (q == 2)
        {
            Traversal_Straight(tree);
            cout << endl;
        }
        else if (q == 3)
        {
            Traversal_Back(tree);
            cout << endl;
        }
        else if (q == 4)
        {
            Traversal_Symmetric(tree);
            cout << endl;
        }
        else if (q == 5)
            cout << Height(tree);
        else if (q == 6)
            Clean(tree);
        else if (q == 7)
            Output(tree, 0);
        else if (q == 8)
        {
            int elem;
            cin >> elem;
            Search(tree, elem);
        }
        else if (q == 9)
        {
            int elem;
            cin >> elem;
            Delete(tree, elem);
        }
        else if (q == 10)
        {
            int elem;
            cin >> elem;
            cout << "Адресс элемента " << elem << " равен: " << Search_Elem(tree, elem) << endl;
        }

    } while (q != 0);
}

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

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)
{
    if (tree != nullptr)
    {
        cout << tree->Key << ' ';
        Traversal_Straight(tree->Left);
        Traversal_Straight(tree->Right);
    }
}

void Traversal_Back(Node* tree)
{
    if (tree != nullptr)
    {
        Traversal_Back(tree->Left);
        Traversal_Back(tree->Right);
        cout << tree->Key << ' ';
    }
}

void Traversal_Symmetric(Node* tree)
{
    if (tree != nullptr)
    {
        Traversal_Symmetric(tree->Left);
        cout << tree->Key << ' ';
        Traversal_Symmetric(tree->Right);
    }
}

int Height(Node* tree)
{
    int h1, h2;
    if (tree == nullptr)
        return -1;
    else
    {
        h1 = Height(tree->Left);
        h2 = Height(tree->Right);
        if (h1 > h2)
            return (h1 + 1);
        else return (h2 + 1);
    }
}

void Clean(Node* tree)
{
    if (tree != nullptr)
    {
        Clean(tree->Left);
        Clean(tree->Right);
        delete tree;
    }
}

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

void Delete(Node*& tree, int elem)
{
    Node* tmp;

    if (tree == nullptr)
        cout << "Такой вершины не найдено" << endl;
    else if (elem < tree->Key)
        Delete(tree->Left, elem);
    else if (elem > tree->Key)
        Delete(tree->Right, elem);
    else
    {
        tmp = tree;
        if (tmp->Right == nullptr)
        {
            tree = tmp->Left;
            delete tmp;
        }
        else if (tmp->Left == nullptr)
        {
            tree = tmp->Right;
            delete tmp;
        }
        else Delete_1(tmp->Left, tmp);
    }
}

void Delete_1(Node*& tmp1, Node*& tmp2)
{
    Node* tmp3;
    if (tmp1->Right == nullptr)
    {
        tmp2->Key = tmp1->Key;
        tmp2->Count = tmp1->Count;
        tmp2 = tmp1;
        tmp3 = tmp1;
        tmp1 = tmp1->Left;
        delete tmp3;
    }
    else Delete_1(tmp1->Right, tmp2);
}

Node* Search_Elem(Node* tree, int elem)
{
    if (tree == nullptr)
        return tree;
    else if (elem == tree->Key)
        return tree;
    else if (elem < tree->Key)
        return Search_Elem(tree->Left, elem);
    else return Search_Elem(tree->Right, elem);
}