#include <iostream>
#include <fstream>
#include <ctime>
#include <windows.h>
#include <limits>

using namespace std;

struct Node
{
    int x;
    Node *l,*r;
};

void show_a_b(Node *&Tree, int a, int b, int *i)
{

    if (Tree != NULL)
    {
        show_a_b(Tree->l, a, b, i);

        if (Tree->x > a && Tree->x < b)
        {
            (*i)++;
            cout << "  " << Tree->x << "  ";
        }

        show_a_b(Tree->r, a, b, i);
    }
}
void show_inx(Node *&Tree)
{
    if (Tree != NULL)
    {
        show_inx(Tree->l);
            cout << Tree->x << '\t';
        show_inx(Tree->r);
    }
}

void show_psf(Node *&Tree)
{
    if (Tree != NULL)
    {
        cout << Tree->x <<'\t';
        show_psf(Tree->l);
        show_psf(Tree->r);
    }
}
void del(Node *&Tree){
    if (Tree != NULL)
    {
        del(Tree->l);
        del(Tree->r);
        delete Tree;
        Tree = NULL;
    }

}
void show_Tree(Node * Tree,int level = 1)
{
    if(Tree)
    {
        show_Tree(Tree->r,level + 1);
        for(int i = 0;i< level;i++)
            cout <<"   ";
        cout << Tree->x << endl;
        show_Tree(Tree->l,level + 1);
    }
}

void add_node(int x,Node *&MyTree)
{
    if (NULL == MyTree)
    {
        MyTree = new Node;
        MyTree->x = x;
        MyTree->l = MyTree->r = NULL;
        return;
    }
    if (x <= MyTree->x)
    {
        if (MyTree->l != NULL)
            add_node(x, MyTree->l);
        else
        {
            MyTree->l = new Node;
            MyTree->l->l = MyTree->l->r = NULL;
            MyTree->l->x = x;
        }
        return;
    }
    if (MyTree->r != NULL)
        add_node(x, MyTree->r);
    else
    {
        MyTree->r = new Node;
        MyTree->r->l = MyTree->r->r = NULL;
        MyTree->r->x = x;
    }
}
void add_cin(Node *&MyTree, int N)
{
    int wh_0;

    cin.clear();
    cin.ignore( numeric_limits<streamsize>::max() , '\n') ;
    for(int i = 1; i <= N; i++)
    {
        cout << "|  [" << i << "] : ";
        cin >> wh_0;
        add_node(wh_0, MyTree);
    }
}
void add_rand(Node *&MyTree, int count)
{

    if(count <= 0)
        return;
    srand(time(NULL));
    int a;
    for (int i = 0; i < count; ++i)
    {
        a = -50 + rand() % 100;
        add_node(a, MyTree);
    }
}
bool add_f(Node *&MyTree, const char * const f_name)
{
    int a;
    ifstream myfile (f_name);
    if (!myfile)
    {
        cout << "|  Ошибка при открытии файла или такого файла нет" << endl;
        return false;
    }
    while (myfile)
    {
        myfile >> a;
        add_node(a, MyTree);
    }
    return true;
}
int UI_s()
{
    int tmp;
    setlocale(LC_ALL, "Russian");
    system("cls");
    cout << endl;
    cout << "\t+--------------------------------------------------------------+" << endl;
    cout << "\t|       Выберете, каким оброзом нужно заполнять дерево?        |" << endl;
    cout << "\t+--------------------+--------------------+--------------------+" << endl;
    cout << "\t|         1.         |          2.        |         3.         |" << endl;
    cout << "\t|                    |                    |                    |" << endl;
    cout << "\t|       Ввести       |      Используя     |         Из         |" << endl;
    cout << "\t|         в          |     псевдорандом   |    *.txt файла     |" << endl;
    cout << "\t|       ручную       |                    |                    |" << endl;
    cout << "\t|                    |                    |                    |" << endl;
    cout << "\t+--------------------+--------------------+--------------------+" << endl << endl;
    cout << "\t                                          +--------------------+" << endl;
    cout << "\t                                          |   4.    Выход      |" << endl;
    cout << "\t                                          +--------------------+" << endl << endl << endl << endl;
    cout << "|  Ввод >> ";
    cin >> tmp;
    while(!cin.good())
    {
        cin.clear();
        cin.ignore( numeric_limits<streamsize>::max() , '\n') ;
        cout << "|  Вы ввели неправильное значение!" << endl << "|  Повторите ввод " << endl << "|  Ввод >> ";
        cin >> tmp;

    }
    cin.clear();
    cin.ignore( numeric_limits<streamsize>::max() , '\n') ;
    return tmp;

}
int UI_e()
{
    int tmp;
    setlocale(LC_ALL, "Russian");
    system("cls");
    cout << endl;
    cout << "\t+--------------------------------------------------------------+" << endl;
    cout << "\t|        Выберете, каким оброзом нужно вывести дерево?         |" << endl;
    cout << "\t+--------------------+--------------------+--------------------+" << endl;
    cout << "\t|         1.         |          2.        |         3.         |" << endl;
    cout << "\t|                    |                    |                    |" << endl;
    cout << "\t|         В          |          В         |         В          |" << endl;
    cout << "\t|     инфиксной      |     префиксной     |        виде        |" << endl;
    cout << "\t|       форме        |        форме       |       дерева       |" << endl;
    cout << "\t|                    |                    |                    |" << endl;
    cout << "\t+--------------------+--------------------+--------------------+" << endl << endl;
    cout << "\t                                          +--------------------+" << endl;
    cout << "\t                                          |   4.    Выход      |" << endl;
    cout << "\t                                          +--------------------+" << endl << endl << endl << endl;
    cout << "|  Ввод >> ";
    cin >> tmp;
    while(!cin.good())
    {
        cin.clear();
        cin.ignore( numeric_limits<streamsize>::max() , '\n') ;
        cout << "|  Вы ввели неправильное значение!" << endl << "|  Повторите ввод " << endl << "|  Ввод >> ";
        cin >> tmp;

    }
    cin.clear();
    cin.ignore( numeric_limits<streamsize>::max() , '\n') ;
    return tmp;

}

int main(int argc, char const *argv[])
{
    Node* Tree = NULL;
    int con = 0, how_i = 0;
    bool how_b = false;
    char st, trash;
start:
    do{
        how_i = UI_s();
        switch (how_i) {
            case 1: {

                cout << "|  Введите сколько цифр вы хотите" << endl << "|  Ввод >> ";
                int a;
                cin >> a;
                while(!cin.good())
                {
                    cin.clear();
                    cin.ignore( numeric_limits<streamsize>::max() , '\n') ;
                    cout << "|  Вы ввели неправильное значение!" << endl << "|  Повторите ввод " << endl << "|  Ввод >> ";
                    cin >> a ;


                }
                if (a < 0) a = -a;
                add_cin(Tree, a);
                how_b = true;
                break;
            }
            case 2: {
                cout << "|  Введите сколько цифр вы хотите" << endl << "|  Ввод >> ";
                int a;
                cin >> a;
                while(!cin.good())
                {
                    cin.clear();
                    cin.ignore( numeric_limits<streamsize>::max() , '\n') ;
                    cout << "|  Вы ввели неправильное значение!" << endl << "|  Повторите ввод " << endl << "|  Ввод >> ";
                    cin >> a ;

                }
                cin.clear();
                cin.ignore( numeric_limits<streamsize>::max() , '\n') ;
                if (a < 0) a = -a;
                add_rand(Tree, a);
                how_b = true;
                break;
            }
            case 3: {
                char text[255];
                add_f_m:
                cout << endl << "|  Введите относительный путь к файлу" << endl << "|  Ввод >> ";
                scanf("%s", &text);
                if(!add_f(Tree, text)) goto add_f_m;
                how_b = true;
                break;
            }
            case 4: {
                cout << "|  Вы уверены? " << endl << "|  [y/n] >> ";
                cin >> st;
                while ((st != 'n' && st != 'y') ||  !cin.good())
                {
                    cin.clear();
                    cin.ignore( numeric_limits<streamsize>::max() , '\n');
                    cout << "|  Некорректный ввод" << endl << "|  [y/n] >> ";
                    cin >> st;
                }
                cin.clear();
                cin.ignore( numeric_limits<streamsize>::max() , '\n');
                if (st == 'n') goto start;
                del(Tree);
                system("cls");
                return 1;
            }
            default : break;

        }
    }while(!how_b);

    cout << "|  [";
    for (int i = 0; i < 50; ++i)
    {
        cout << "=";
        Sleep(15);
    }
    cout << "] Done";
    Sleep(400);

s_ui:
    how_b = false;
    do{
        how_i = UI_e();
        switch (how_i) {
            case 1: {
                cout << "|  << ";
                show_inx(Tree);
                cout << endl;
                how_b = true;
                break;
            }
            case 2: {
                cout << "|  << ";
                show_psf(Tree);
                cout << endl;
                how_b = true;
                break;
            }
            case 3: {
                show_Tree(Tree);
                //cout << endl;
                how_b = true;
                break;
            }
            case 4: {
                cout << "|  Вы уверены? " << endl << "|  [y/n] >> ";
                cin >> st;
                while ((st != 'n' && st != 'y') ||  !cin.good())
                {
                    cin.clear();
                    cin.ignore( numeric_limits<streamsize>::max() , '\n');
                    cout << "|  Некорректный ввод" << endl << "|  [y/n] >> ";
                    cin >> st;
                }
                cin.clear();
                cin.ignore( numeric_limits<streamsize>::max() , '\n');
                if (st == 'n') goto start;
                del(Tree);
                system("cls");
                return 1;
            }
            default : {
                cin.clear();
                cin.ignore( numeric_limits<streamsize>::max() , '\n');
                break;
            }

        }
    }while(!how_b);
    int a, b, col = 0;
    cout << "|  Введите интервал (a, b)" << endl << "|  a >> ";
    cin >> a;
    while(!cin.good())
    {
        cin.clear();
        cin.ignore( numeric_limits<streamsize>::max() , '\n') ;
        cout << "|  Вы ввели неправильное значение!" << endl << "|  Повторите ввод " << endl << "|  a >> ";
        cin >> a;

    }
    cin.clear();
    cin.ignore( numeric_limits<streamsize>::max() , '\n') ;
    cout << "|  b >> ";
    cin >> b;
    while(!cin.good())
    {
        cin.clear();
        cin.ignore( numeric_limits<streamsize>::max() , '\n') ;
        cout << "|  Вы ввели неправильное значение!" << endl << "|  Повторите ввод " << endl << "|  b >> ";
        cin >> b;

    }
    cin.clear();
    cin.ignore( numeric_limits<streamsize>::max() , '\n') ;

    cout << "|  Числа в интервале ("<< a << ", " << b <<") : ";
    if (a <= b)
        show_a_b(Tree, a, b, &col);
    else
        show_a_b(Tree, b, a, &col);
    cout << endl << "|  Чисел в вашем интервале : " << col << endl << endl;

    cout << "Запустить заново? [y/n] ";
    cin >> st;
    while ((st != 'n' && st != 'y') ||  !cin.good())
    {
        cin.clear();
        cin.ignore( numeric_limits<streamsize>::max() , '\n');
        cout << "|  Некорректный ввод" << endl << "|  [y/n] >> ";
        cin >> st;
    }
    cin.clear();
    cin.ignore( numeric_limits<streamsize>::max() , '\n');
    if (st == 'y') {
        del(Tree);
        goto start;
    }
    system("pause && cls");
    return 0;
}