#include <cmath>
#include <clocale>
#include <iostream>
#include <conio.h>
#include <ctime> 
 
using namespace std;
 
struct poezd
{
    poezd* left;
    poezd* right;
    char station[50];
    
    int nomber_poezd;
    int Arrival_time_h;
    int Arrival_time_m;
    int Start;
 
};
int for_poizk = 1;
int dobavit_poezd(int n);
int zapusk_progaram(int Start);
void pushpoezd(poezd new_poezd, poezd** t);
void printpoezd(poezd* t, int u, int dlina_dereva);
void poiskpoezd(poezd* t, poezd* parent, poezd new_poezd);
int  dlina_dereva(poezd* g, int u);
poezd * Leftmost(poezd * t);
poezd * Rightmost(poezd * t);
 
poezd * tree = NULL; 
 
int _tmain(int argc, _TCHAR* argv[])
{
    int menu;
    setlocale(LC_ALL, "RUSSIAN");
 

    
    poezd new_poezd;
    new_poezd.nomber_poezd = 25;    new_poezd.Arrival_time_h = 12; new_poezd.Arrival_time_m = 30;   strcp_s(new_poezd.station, "Orel");
    pushpoezd(new_poezd, &tree);
    new_poezd.nomber_poezd = 85;    new_poezd.Arrival_time_h = 15;  new_poezd.Arrival_time_m = 45; strcp_s(new_poezd.station, "Moscow");
    pushpoezd(new_poezd, &tree); 
    new_poezd.nomber_poezd = 12;    new_poezd.Arrival_time_h = 21;  new_poezd.Arrival_time_m = 15; strcp_s(new_poezd.station, "Ulyanovsk");
    pushpoezd(new_poezd, &tree); 
    new_poezd.nomber_poezd = 36;    new_poezd.Arrival_time_h = 18;  new_poezd.Arrival_time_m = 10; strcpy_s(new_poezd.station, "Tolyati");
    pushpoezd(new_poezd, &tree); 
    new_poezd.nomber_poezd = 19;    new_poezd.Arrival_time_h = 14;  new_poezd.Arrival_time_m = 50; strcpy_s(new_poezd.station, "Perm'");
    pushpoezd(new_poezd, &tree); 
 
 
    int Start = 0;
    zapusk_progaram(Start);
    
    for (;;) {
 
        cout << endl;
        cout << "Меню программы:" << endl;
        cout << "1 - Вывести список поездов " << endl;
        cout << "2 - Добавить поез в базу " << endl;
        cout << "3 - Поиск поезда в базе " << endl;
        cout << "4 - Выход из программы" << endl;
        cout << endl;
        cout << "Выполнить действие # ";
 
        cin >> menu;
 
        switch (menu)
        {
        case 1:
            
            printpoezd(tree, 0, dlina_dereva(tree, 0));
        
            break;
            
        case 2:
            cout << "Добавляем новый поезд..." << endl;
 
            int n; 
            cout << "Кол-во добавляемых поездов =  ";
            cin >> n;
 
            for (int i = 0; i < n; i++) {
                
                poezd new_poezd;
               
                cout << "Введите номер поезда № " << i + 1 << " ";      cin >> new_poezd.nomber_poezd;
                cout << "Введите станцию (на латинице)№ " << i + 1 << " ";      cin >> new_poezd.station;
                cout << "Введите время отправления (час)№ " << i + 1 << " ";        cin >> new_poezd.Arrival_time_h;
                cout << "Введите время отправления (минуты)№ " << i + 1 << " ";     cin >> new_poezd.Arrival_time_m;
                
                printf("Поезд успешно добавлен с базу данных...");
                pushpoezd(new_poezd, &tree); 
 
            }
 
 
            break;
            
        case 3:
            cout << "Поиск поезда..." << endl;
        
            poezd enter_data_poezd;
          
            cout << "Введите номер поезда";     cin >> enter_data_poezd.nomber_poezd;
            
        
 
            poiskpoezd(tree, NULL, enter_data_poezd);
            break;
            
        case 4:
 
            exit(0);
            break;
        default:
            
            cout << "Нет такого действия" << endl;
            
            cout << endl;
            break;
        }
 
 
    }
 
    system("pause");
    return 0;
}
 
int zapusk_progaram(int Start)
{
    return Start;
}
 

int dlina_dereva(poezd* g, int u)
{
    int current_dlina_dereva = u,
        left_dlina_dereva = u,
        right_dlina_dereva = u;
    if (g == NULL) {
        return 0; 
    }
    else {
        u++;
        left_dlina_dereva = dlina_dereva(g->left, u);
        if (left_dlina_dereva >= current_dlina_dereva) {
            current_dlina_dereva = left_dlina_dereva;
        }
        u--;
    }
    u++;
    
    right_dlina_dereva = dlina_dereva(g->right, u);
    if (right_dlina_dereva >= current_dlina_dereva) {
        current_dlina_dereva = right_dlina_dereva;
    }
 
    return current_dlina_dereva;
}
 
void pushpoezd(poezd new_poezd, poezd **t)
{
    if ((*t) == NULL)           
    {
        (*t) = new poezd;           
        (*t)->nomber_poezd = new_poezd.nomber_poezd;
        (*t)->Arrival_time_h = new_poezd.Arrival_time_h;
        (*t)->Arrival_time_m = new_poezd.Arrival_time_m;
        strcpy_s((*t)->station, new_poezd.station);
        (*t)->left = NULL;          
        (*t)->right = NULL;
        return;
    }
 
    
    if (new_poezd.nomber_poezd > (*t)->nomber_poezd) {
        pushpoezd(new_poezd, &(*t)->right); 
    }
    else {
        pushpoezd(new_poezd, &(*t)->left); 
    }
}
 

void printpoezd(poezd *t, int u, int dlina_dereva)
{
    if (t == NULL) {
        return; 
    }
    else {
        u++;
        printpoezd(t->left, u, dlina_dereva);
        for (int i = 0; i < u; i++) {
            cout << "> ";
        }
        for (int i = u - 1; i < dlina_dereva; i++) {
 
            cout << "  ";
        }
       
        cout << "Номер поезда = " << t->nomber_poezd
            << " / Время = " << t->Arrival_time_h << ":" << t->Arrival_time_m 
            << " / Станция = " << t->station << endl;
 
        u--;
    }
    u++;
    printpoezd(t->right, u, dlina_dereva); 
}
 

void poiskpoezd(poezd* t, poezd* parent, poezd new_poezd)
{
 
 
    
    
    if (t == NULL) 
    {
        cout <<endl;
        cout << "Нет такого поезда"<<endl; 
        cout << "Повторите запрос..." << endl;
    }
    else {
        if (new_poezd.nomber_poezd < t->nomber_poezd) {
            return poiskpoezd(t->left, t, new_poezd);
        }
        else if (new_poezd.nomber_poezd > t->nomber_poezd) {
            return poiskpoezd(t->right, t, new_poezd);
 
        }
        else {
            
            if (t->left == NULL && t->right == NULL && strcmp(new_poezd.station, t->station) == 0) {
                if (parent->left == t) {
                    parent->left = NULL;
                }
                else {
                    parent->right = NULL;
                }
                delete t;
            }
            else if (t->left == NULL && t->right == NULL && strcmp(new_poezd.station, t->station) != 0) {
                
            }
 
            t->right = NULL;
            t->left = NULL;
 
            cout << "Поезд успешно найден... \n " << endl;
            cout << "Номер поезда = " << t->nomber_poezd
                << " / Время = " << t->Arrival_time_h << ":" << t->Arrival_time_m
                << " / Станция = " << t->station << endl;
        }
    }
 
}
    
 
 poezd * Leftmost(poezd * t) {
    if (t == NULL)
        return NULL;
    if (t->left != NULL) {
        return Leftmost(t->left);
    }
    return t;
}
poezd * Rightmost(poezd * t) {
    if (t == NULL)
        return NULL;
    if (t->right != NULL) {
        return Rightmost(t->right);
    }
    return t;
}