дерево черновик старый

#include <iostream>
#include <Windows.h>
#include <conio.h>
#include <cmath>
using namespace std;
struct BinTree {
    int value; //содержит значение
    BinTree* left;//адрес левого поддерева
    BinTree* right;//адрес правого поддерева
};


/*
 * Inserting Element into the Tree
 */
/*
void newBinTree(int val, BinTree** Tree, BinTree* newnode)
{
    if (root == NULL)
    {
        root = new BinTree;
        root->value = newnode->value;
        root->left = NULL;
        root->right = NULL;
        cout << "Root Node is Added" << endl;
        return;
    }

    if ((*Tree)->value > newnode->value)
    {
        if ((*Tree)->left != NULL)
        {
            newBinTree((*Tree)->value,(*Tree)->left, newnode);
        }
        else
        {
            (*Tree)->left = newnode;
            ((*Tree)->left)->left = NULL;
            (tree->left)->right = NULL;
            cout << "Node Added To Left" << endl;
            return;
        }
    }
    else
    {
        if ((*Tree)->right != NULL)
        {
            insert(tree->right, newnode);
        }
        else
        {
            tree->right = newnode;
            (tree->right)->left = NULL;
            (tree->right)->right = NULL;
            cout << "Node Added To Right" << endl;
            return;
        }
    }
}
*/
//Функция для создания дерева
//Вход: значение будущего узла,узел бинарного дерева
//Выход: упорядоченое бинарное деревоб,заполеное значениями
void newBinTree(int val, BinTree** Tree) {

/*
    TNode** cur = &Root;
    while (*cur) {
        TNode& node = **cur;
        if (x < node.Key) {
            cur = &node.Left;
        }
        else if (x > node.Key) {
            cur = &node.Right;
        }
        else {
            return;
        }
    }
    *cur = new TNode(x);
    */

    if ((*Tree) == NULL)
    {
        (*Tree) = new BinTree; //Выделить память
        (*Tree)->value = val;  //Поместить в выделенное место аргумент
        (*Tree)->left = (*Tree)->right = NULL;
        return;
    }
    if (val > (*Tree)->value) newBinTree(val, &(*Tree)->right); //Если аргумент больше чем текущий элемент, поместить его вправо
    else newBinTree(val, &(*Tree)->left);//Иначе поместить его влево
  }



//Для печати дерева
void Print(BinTree** Tree, int l)
{
    int i;

    if (*Tree != NULL)
    {
        Print(&((**Tree).right), l + 1);
        for (i = 1; i <= l; i++) cout << "   ";
        cout << (**Tree).value << endl;
        Print(&((**Tree).left), l + 1);
    }
}

void TreeTraversalAndPrint(BinTree* Root) {
    if (Root != NULL) {
        cout << Root->value << endl;
        TreeTraversalAndPrint(Root->left);
        TreeTraversalAndPrint(Root->right);

    }
}

void TreeTraversalAndPrint2(BinTree* Root) {
    if (Root != NULL) {
        TreeTraversalAndPrint2(Root->left);
        TreeTraversalAndPrint2(Root->right);
        cout << Root->value << endl;
    }
}
void TreeTraversalAndPrint3(BinTree* Root) {
    if (Root != NULL) {
        TreeTraversalAndPrint2(Root->left);
        cout << Root->value << endl;
        TreeTraversalAndPrint2(Root->right);
    }
}
//Так как в бинарном дереве поиска для каждого узла справедливо, что left < right,
//то соответственно для нахождения наименьшенго элемента
//надо топать от корня по левым веткам до упора - там и будет наименьший.
BinTree* MinValue(BinTree* Tree)
{
    if (Tree->left != NULL) {
        return MinValue(Tree->left);
    }
    else {
        return Tree;
    }
}
//Так как в бинарном дереве поиска для каждого узла справедливо, что left < right,
//то соответственно для нахождения наибольшего элемента
//надо топать от корня по правым веткам до упора - там и будет наибольший.
BinTree* MaxValue(BinTree* Tree)
{
    if (Tree->right != NULL) {
        return  MaxValue(Tree->right);
    }
    else {
        return Tree;
    }
}
int NumberOfNodes(BinTree* Tree) {
    if (Tree == NULL) return 0;
    return NumberOfNodes(Tree->left) + 1 + NumberOfNodes(Tree->right);
}

int ListCount(BinTree* node)
{
    if (!node)
        return 0;
    if (!node->left && !node->right)
        return 1;
    return  ListCount(node->left) + ListCount(node->right);
}

//Высота(максимальная глубина) дерева определяется количеством уровней,
//на которых располагаются его вершины.
//Высота пустого дерева равна нулю, высота дерева из одного корня – единице.
//На первом уровне дерева может быть только одна вершина – корень дерева,
//на втором – потомки корня дерева, на третьем – потомки потомков корня дерева и т.д.
int HeightBTree(BinTree* Tree) {
    int x = 0, y = 0;
    if (Tree == NULL) return 0;     //пустое дерево или дошли до листа
    if (Tree->left) x = HeightBTree(Tree->left); //высота левого поддерева
    if (Tree->right) y = HeightBTree(Tree->right);  //высота правого поддерева
    if (x > y) return x + 1;    //+1 от корня к левому поддереву
    else return y + 1;   //+1 от корня к правому поддереву
}
//поиск элемента в бинарном дереве поиска
BinTree* Search(BinTree* Tree, int key) {
    if (Tree == NULL) return NULL;
    if (Tree->value == key) return Tree;
    if (key < Tree->value) return Search(Tree->left, key);
    else
        return Search(Tree->right, key);
}


void DestroyBTree(BinTree* Tree) {
    if (Tree != NULL) {
        DestroyBTree(Tree->left);
        DestroyBTree(Tree->right);
        delete(Tree);
    }
}
void Menu() {
    BinTree* Tree = NULL;
    int command;
    int val;
    cout << "Для проверки дерева его необходимо создать" << endl;
    while (true) {
        cout << endl;
        cin >> command;
        if (command == 1)
        {
            while (_getch() != 27) {
                cout << "ведите значение (для завершения ввода нажмите ESC) ";
                cin >> val;
                newBinTree(val, &Tree);
            }
        }
        else {
            if (command == 2)
                Print(&Tree, 0);

            else {
                if (command == 3) {
                    cout << "Прямой обход дерева" << endl;
                    TreeTraversalAndPrint(Tree);
                }
                else
                    //cout << "Обратный обход дерева" << endl;
                    //TreeTraversalAndPrint2(Tree);
                {
                    if (command == 4)
                        cout << "Cимметричный обход дерева" << endl;
                    TreeTraversalAndPrint3(Tree);
                };
                /*cout << "Минимальный элемент дерева-> ";
                BinTree* min = MinValue(Tree);
                cout << min->value;
                cout << endl << "Максимальный элемент дерева-> ";
                BinTree* max = MaxValue(Tree);
                cout << max->value;*/
                cout << endl;
                cout << "Высота дерева-> ";
                int Heigh = HeightBTree(Tree);
                cout << Heigh;
                cout << endl;
                cout << "Количество элементов в дереве-> ";
                int a = NumberOfNodes(Tree);
                cout << a << endl;
                cout << "Количество листов в дереве-> ";
                int b = ListCount(Tree);
                cout << b << endl;
                cout << "Поиск элемента" << endl;
                int key;
                cout << "Введите значение элемента для поиска-> ";
                cin >> key;
                BinTree* Tree1 = Search(Tree, key);
                if (Tree1 == NULL)
                    cout << "Элемент не найден";
                else
                    cout << "Ваш элемент->" << Tree1->value;
                cout << endl;
                DestroyBTree(Tree);
            }
        }
    }
}

int main() {
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    Menu();
    system("pause");
    return 0;
}