#include <iostream>
#include <fstream>
#include <ctime>
#include <windows.h>
#include <clocale>
using namespace std;

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

void show_n_l(Node *&Tree, int *sum, int n, int k = 1)
{

    if (Tree != NULL)
    {
        if( n < k)
            return;
        if (n == k)
        {
            (*sum)++;
            cout << Tree->x << ' ' << endl;
        }

        show_n_l(Tree->l, sum, n, ++k);
        k--;
        if (n == k)
        {
            (*sum)++;
            cout << Tree->x << ' ' << endl;
        }

        show_n_l(Tree->r, sum, n, k++);
    }
}

int tree_count(std::ostream& _out, const Node* tr, int level, int i = 0){
    int n = 0;
    if(tr != NULL){
        if(i == level){
            ++n;
            _out << tr->x << ' ';
        }
        if(tr->l != NULL)
            n += tree_count(_out, tr->l,  level, i + 1);
        if(tr->r != NULL)
            n += tree_count(_out, tr->r, level, i + 1);
    }
    return n;
}

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 = 0)
{
    if(Tree)
    {
        show_Tree(Tree->r,level + 1);
        for(int i = 0;i< level;i++)
            cout <<"    ";
        printf("% 4d\n",Tree->x);
        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;
        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;
    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;
    return tmp;

}
int main(int argc, char const *argv[])
{
    setlocale( LC_ALL,"Rus" );
    system("chcp 1251");
    Node* Tree = NULL;
    int con = 0, how_i = 0;
    bool how_b = false;
    char st;
start:
    do{
        how_i = UI_s();
        switch (how_i) {
            case 1: {
                cout << "|  Введите сколько цифр вы хотите" << endl << "|  Ввод >> ";
                int a;
                cin >> a;
                if (a < 0) a = -a;
                add_cin(Tree, a);
                how_b = true;
                break;
            }
            case 2: {
                cout << "|  Введите сколько цифр вы хотите" << endl << "|  Ввод >> ";
                int a;
                cin >> a;
                if (a < 0) a = -a;
                add_rand(Tree, a);
                how_b = true;
                break;
            }
            case 3: {
                char text[20];
                    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;
                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;
                if (st == 'n') goto s_ui;
                del(Tree);
                system("cls");
                return 1;
            }
            default : break;

        }
    }while(!how_b);
    int n;
    cout << "Введите уровень, на котором ъотите подсчитать кол-во элементов" << endl << "|  Ввод >> ";
    cin >> n;
    cout << endl;
    int Sum = tree_count(std::cout, Tree, n);
    cout << endl << "На " << n << " уровне - " << Sum << " элементов" << endl;

    cout << "Запустить заново? [y/n] ";
    cin >> st;
    if (st == 'y') { del(Tree); goto start;}
    system("pause && cls");
    return 0;
}