#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <conio.h>
#include <cmath>
using namespace std;

// int licznik=0;

struct Wezel
{
    long double liczba;
    Wezel* lewy;
    Wezel* prawy;
};

Wezel* nowy(long double n)
{
    Wezel *tworz =  new Wezel;
    tworz->liczba = n;
    tworz->lewy = tworz->prawy = NULL;
    return tworz;
}

bool szukaj(Wezel* korzen, long double n, bool *wystepuje)
{
    if(korzen!=NULL)
    {
        if(korzen->liczba==n)
        {
            *wystepuje=true;
        }
        else
        {
            if(korzen->liczba<n)
            {
                szukaj(korzen->prawy, n, wystepuje);
            }
            else
            {
                szukaj(korzen->lewy, n, wystepuje);
            }
        }
    }
    return *wystepuje;
}

void calkowita(Wezel* korzen, long double n, int *ile)
{
    if(korzen!=NULL)
    {
        if((int)korzen->liczba==n)
        {
            *ile+=1;
        }
        calkowita(korzen->prawy, n, ile);
        calkowita(korzen->lewy, n, ile);
    }
}

void wypisz(Wezel* korzen, string odstep, string strona)
{
    if(korzen!=NULL)
    {
        if(strona=="")
        {
            cout<<"K: "<<korzen->liczba<<endl;
            odstep=odstep+"    ";
        }
        else
        {
            if(strona=="l")
            {
                cout<<odstep+"     L: "<<korzen->liczba<<endl;
                odstep=odstep+"        ";
            }
            else
            {
                if(strona=="p")
                {
                    cout<<odstep+"     P: "<<korzen->liczba<<endl;
                    odstep=odstep+"        ";
                }
            }
        }

        strona='p';
        wypisz(korzen->prawy, odstep, strona);
        strona='l';
        wypisz(korzen->lewy, odstep, strona);
    }
}

Wezel* wstaw(Wezel* korzen, long double n)
{
    if(korzen==NULL)
    {
        return nowy(n);
    }

    if (n<korzen->liczba)
    {
        korzen->lewy = wstaw(korzen->lewy, n);
    }
    else
    {
        if (n>korzen->liczba)
        {
            korzen->prawy = wstaw(korzen->prawy, n);
        }
    }

    return korzen;
}

Wezel* nastepnik(Wezel* korzen)
{
    Wezel* pom = korzen;

    while (pom && pom->lewy != NULL)
    {
        pom = pom->lewy;
    }

    return pom;
}

Wezel* usun(Wezel* korzen, long double n)
{
    if(korzen==NULL)
    {
        return korzen;
    }

    if(n<korzen->liczba)
    {
        korzen->lewy = usun(korzen->lewy, n);
    }
    else
    {
        if(n>korzen->liczba)
        {
            korzen->prawy = usun(korzen->prawy, n);
        }
        else
        {
            // 1 dziecko lub bez
            if(korzen->lewy == NULL)
            {
                Wezel* pom = korzen->prawy;
                delete korzen;
                return pom;
            }
            else
            {
                if(korzen->prawy == NULL)
                {
                    Wezel* pom = korzen->lewy;
                    delete korzen;
                    return pom;
                }
            }

            // 2 dzieci
            Wezel* pom = nastepnik(korzen->prawy);
            korzen->liczba = pom->liczba;
            korzen->prawy = usun(korzen->prawy, pom->liczba);
        }
    }

    return korzen;
}


int main()
{
    ifstream wej("inm.txt");
    ofstream wyj("out.txt");

    int x, ileLiczb=0;
    int *ile=&ileLiczb;
    bool wyst=false;
    bool *wystepuje=&wyst;
    char znak, f;
    string odstep="", t="", strona="";
    long double n;
    Wezel* korzen = NULL;
    Wezel* pom = korzen;

//    cout<<setw(16);
    cout<<setprecision(16);

    cout<<"\n\n  [1]";
    cout<<"      SZUKAJ LICZBE\n\n\n";
    cout<<"  [2]";
    cout<<"      WSTAW LICZBE\n\n\n";
    cout<<"  [3]";
    cout<<"      USUN LICZBE\n\n\n";
    cout<<"  [4]";
    cout<<"      ILE LICZB POSIADA CZESC CALKOWITA ROWNA X\n\n\n";
    cout<<"  [5]";
    cout<<"      WYPISZ DRZEWO\n\n\n";
    cout<<"  [6]";
    cout<<"      WCZYTAJ SKRYPT\n\n\n";
    cout<<"  [7]";
    cout<<"      KONIEC\n\n\n";

    do{
        switch (f=getch())
        {

        case '1':
            system("cls");
            cout<<"PODAJ SZUKANA LICZBE:  ";
            cin>>n;

            szukaj(korzen, n, wystepuje);

            if(*wystepuje==true)
            {
                cout<<"TAK"<<endl;
            }
            else
            {
                cout<<"NIE"<<endl;
            }

            *wystepuje=false;

            system("pause");
            system("cls");
            cout<<"\n\n  [1]";
            cout<<"      SZUKAJ LICZBE\n\n\n";
            cout<<"  [2]";
            cout<<"      WSTAW LICZBE\n\n\n";
            cout<<"  [3]";
            cout<<"      USUN LICZBE\n\n\n";
            cout<<"  [4]";
            cout<<"      ILE LICZB POSIADA CZESC CALKOWITA ROWNA X\n\n\n";
            cout<<"  [5]";
            cout<<"      WYPISZ DRZEWO\n\n\n";
            cout<<"  [6]";
            cout<<"      WCZYTAJ SKRYPT\n\n\n";
            cout<<"  [7]";
            cout<<"      KONIEC\n\n\n";
            break;

        case '2':
            system("cls");
            cout<<"PODAJ LICZBE DO WSTAWIENIA:  ";
            cin>>n;

            korzen=wstaw(korzen, n);
            cout<<endl;

            //system("pause");
            system("cls");
            cout<<"\n\n  [1]";
            cout<<"      SZUKAJ LICZBE\n\n\n";
            cout<<"  [2]";
            cout<<"      WSTAW LICZBE\n\n\n";
            cout<<"  [3]";
            cout<<"      USUN LICZBE\n\n\n";
            cout<<"  [4]";
            cout<<"      ILE LICZB POSIADA CZESC CALKOWITA ROWNA X\n\n\n";
            cout<<"  [5]";
            cout<<"      WYPISZ DRZEWO\n\n\n";
            cout<<"  [6]";
            cout<<"      WCZYTAJ SKRYPT\n\n\n";
            cout<<"  [7]";
            cout<<"      KONIEC\n\n\n";
            break;

        case '3':
            system("cls");
            cout<<"PODAJ LICZBE DO USUNIECIA:  ";
            cin>>n;

            korzen=usun(korzen, n);
            cout<<endl;

            //system("pause");
            system("cls");
            cout<<"\n\n  [1]";
            cout<<"      SZUKAJ LICZBE\n\n\n";
            cout<<"  [2]";
            cout<<"      WSTAW LICZBE\n\n\n";
            cout<<"  [3]";
            cout<<"      USUN LICZBE\n\n\n";
            cout<<"  [4]";
            cout<<"      ILE LICZB POSIADA CZESC CALKOWITA ROWNA X\n\n\n";
            cout<<"  [5]";
            cout<<"      WYPISZ DRZEWO\n\n\n";
            cout<<"  [6]";
            cout<<"      WCZYTAJ SKRYPT\n\n\n";
            cout<<"  [7]";
            cout<<"      KONIEC\n\n\n";
            break;

        case '4':
            system("cls");
            cout<<"PODAJ CZESC CALKOWITA:  ";
            cin>>n;

            *ile=0;
            calkowita(korzen, n, ile);
            cout<<endl<<"ILE LICZB: "<<*ile<<endl<<endl;

            system("pause");
            system("cls");
            cout<<"\n\n  [1]";
            cout<<"      SZUKAJ LICZBE\n\n\n";
            cout<<"  [2]";
            cout<<"      WSTAW LICZBE\n\n\n";
            cout<<"  [3]";
            cout<<"      USUN LICZBE\n\n\n";
            cout<<"  [4]";
            cout<<"      ILE LICZB POSIADA CZESC CALKOWITA ROWNA X\n\n\n";
            cout<<"  [5]";
            cout<<"      WYPISZ DRZEWO\n\n\n";
            cout<<"  [6]";
            cout<<"      WCZYTAJ SKRYPT\n\n\n";
            cout<<"  [7]";
            cout<<"      KONIEC\n\n\n";
            break;

        case '5':
            system("cls");

            if(korzen==NULL)
            {
                cout<<"*BRAK DRZEW*"<<endl;
            }

            strona="";
            odstep="";
            wypisz(korzen, odstep, strona);
            cout<<endl;

            system("pause");
            system("cls");
            cout<<"\n\n  [1]";
            cout<<"      SZUKAJ LICZBE\n\n\n";
            cout<<"  [2]";
            cout<<"      WSTAW LICZBE\n\n\n";
            cout<<"  [3]";
            cout<<"      USUN LICZBE\n\n\n";
            cout<<"  [4]";
            cout<<"      ILE LICZB POSIADA CZESC CALKOWITA ROWNA X\n\n\n";
            cout<<"  [5]";
            cout<<"      WYPISZ DRZEWO\n\n\n";
            cout<<"  [6]";
            cout<<"      WCZYTAJ SKRYPT\n\n\n";
            cout<<"  [7]";
            cout<<"      KONIEC\n\n\n";
            break;

        case '6':
            system("cls");
            korzen=pom;
            cout<<"*WCZYTANO POMYSLNIE*"<<endl<<"--------------------"<<endl<<endl;
            wej>>x;

            while(!wej.eof())
            {
                wej>>znak>>t;

                replace( t.begin(), t.end(), ',', '.');
                n=atof(t.c_str());
                n=rint(n*100000000)/100000000;


//                cout<<znak<<" "<<n<<endl;

                if(znak=='S')
                {
                    szukaj(korzen, n, wystepuje);

                    if(*wystepuje==true)
                    {
                        cout<<"TAK"<<endl;
                    }
                    else
                    {
                        cout<<"NIE"<<endl;
                    }

                    *wystepuje=false;
                }
                else
                {
                    if(znak=='W')
                    {
                        korzen=wstaw(korzen, n);
                    }
                    else
                    {
                        if(znak=='U')
                        {
                            korzen=usun(korzen, n);
                        }
                        else
                        {
                            if(znak=='L')
                            {
                                *ile=0;
                                calkowita(korzen, n, ile);
                                cout<<*ile<<endl;
                            }
                            else
                            {
                                cout<<"*NIEPRAWIDLOWE POLECENIE W PLIKU*"<<endl;
                            }
                        }
                    }
                }
            }

            system("pause");
            system("cls");
            cout<<"\n\n  [1]";
            cout<<"      SZUKAJ LICZBE\n\n\n";
            cout<<"  [2]";
            cout<<"      WSTAW LICZBE\n\n\n";
            cout<<"  [3]";
            cout<<"      USUN LICZBE\n\n\n";
            cout<<"  [4]";
            cout<<"      ILE LICZB POSIADA CZESC CALKOWITA ROWNA X\n\n\n";
            cout<<"  [5]";
            cout<<"      WYPISZ DRZEWO\n\n\n";
            cout<<"  [6]";
            cout<<"      WCZYTAJ SKRYPT\n\n\n";
            cout<<"  [7]";
            cout<<"      KONIEC\n\n\n";
            break;

        case '7':
            system("cls");
            break;

        default:
            break;
        }
    }while(f!='7');

    korzen=pom;
    delete korzen;

//    system("pause");
//
//    strona="";
//    odstep="";
//    wypisz(korzen, odstep, strona);

    return 0;
}