#include <iostream>
#include <ctime>
#include <time.h>


using namespace std;

class drzewo
{
    struct wezel
    {
        int klucz;
        char tab[10];
        wezel* lewy;
        wezel* prawy;
        wezel(int wartosc)
        {
            klucz = wartosc;
            lewy = NULL;
            prawy = NULL;
        }
    };

public:
    wezel* korzen;
    int counter;

void inorder(wezel* IT)
    {
        if(korzen!=NULL)
        {
            if(IT->lewy != NULL)
            {
                inorder(IT->lewy);
            }
            counter++;
            cout<<IT->klucz<< " ";

            if(IT->prawy != NULL)
            {
                inorder(IT->prawy);
            }
        }

    }

    void preorder(wezel* IT)
    {
        if(korzen!=NULL)
        {
            cout<<IT->klucz<< " ";
            if(IT->lewy != NULL)
            {
                preorder(IT->lewy);
            }


            if(IT->prawy != NULL)
            {
                preorder(IT->prawy);
            }
        }

    }

    void postorder(wezel* IT)
    {
        if(korzen!=NULL)
        {

            if(IT->lewy != NULL)
            {
                postorder(IT->lewy);
            }


            if(IT->prawy != NULL)
            {
                postorder(IT->prawy);
            }
            cout<<IT->klucz<< " ";
        }

    }


void wstawianie(int _klucz)
{
  if (korzen==NULL)
  {
      wezel* nowy;
      nowy = new wezel(_klucz);
      korzen = nowy;
  }
   else
   {
       wezel* IT = korzen;
       bool powtarzanie=false;

       while ((IT->lewy!=NULL || IT->prawy!=NULL) && powtarzanie==false) //Sprawdzanie czy klucze sie powtarzaja
       {
        if(_klucz==IT->klucz)
        {
            powtarzanie=true;
            cout << "klucz sie powtarza";
            break;
        }
       if (IT > korzen)
       {
           if(IT->prawy == NULL) break;
           IT = IT->prawy;
       }
       else
       {
           if(IT->lewy == NULL) break;
           IT = IT->lewy;
       }

       }
       if (powtarzanie==false) //czy klucze sie powtarzaja
       {
           if(_klucz>IT->klucz)
           {
               wezel* nowy_wezel = new wezel(_klucz);
               IT->prawy=nowy_wezel;
           }
           else
           {
               wezel* nowy_wezel = new wezel(_klucz);
               IT->lewy=nowy_wezel;
           }
       }

   }
}

    void generowanie(int liczba)
    {
        for(int i=0; i<liczba; i++)
        {
            this->wstawianie(rand() % 10000);
        }
    }

void wyszukaj(int _klucz)
    {
        if(korzen!=NULL)
        {
            if(korzen->klucz==_klucz)
            {
                cout<<"Klucz zostal znaleziony w korzeniu!"<<endl;
            }
            else
            {
                bool czy_znal = false;

                wezel* IT = korzen;
                while(IT!=NULL)
                {
                    if (IT->klucz==_klucz)
                    {
                        czy_znal=true;
                        cout<<"Znalezlismu klucz"<<endl;
                        break;
                    }
                    else
                    {
                        if(_klucz<IT->klucz)
                        {
                         IT = IT->lewy;
                        }
                        else
                        {
                          IT = IT->prawy;
                        }
                    }
                }
                if (czy_znal==false)
                {
                    cout<<"Nie znaleziono takiego klucza"<<endl;
                }
            }

        }
    }

    wezel *nastepnik(wezel* IT)
    {
        wezel* znaleziony = IT;
        if(znaleziony->prawy == NULL)
        {
            return znaleziony;
        }

        znaleziony = znaleziony->prawy;
        while (znaleziony->lewy!=NULL)
        {
            znaleziony = znaleziony->lewy;
        }

        return znaleziony;
    }

    wezel *znajdz_rodzica(wezel* IT)
    {
        wezel*  rodzic = IT;
        if (IT==korzen)
        {
            return korzen;
        }
        else{
            while(rodzic->lewy!=NULL || rodzic->prawy!=NULL)
            {
                if(rodzic->lewy!=NULL)
                    if (rodzic->lewy->klucz==IT->klucz)
                        break;
                if(rodzic->prawy!=NULL)
                    if(rodzic->prawy->klucz==IT->klucz)
                        break;
                if(rodzic->klucz>IT->klucz)
                    rodzic = rodzic->lewy;
                else
                    rodzic = rodzic->prawy;
            }
        }
        return rodzic;
    }


    void usuwanie(int _klucz)
    {
        if(korzen!=NULL)
        {
            if(_klucz==korzen->klucz) //Usuwanie klucza w korzeniu
            {
                wezel* do_usuniecia = korzen;

                if(korzen->prawy!=NULL) //usuwanie poprzez nastepnika
                {
                    wezel* nast = nastepnik(korzen);
                    wezel* rodzic = znajdz_rodzica(nast);
                    if(rodzic!=korzen)
                    {
                        rodzic->lewy = nast->prawy;
                    }
                    nast->lewy = rodzic->lewy;
                    if(korzen->prawy==nast)
                    {
                        nast->prawy = korzen->prawy->prawy;
                    }
                    else
                    {
                        nast->prawy = korzen->prawy;
                    }
                    korzen = nast;
                    delete do_usuniecia;
                }
                else if (korzen->lewy!=NULL) //brak nastepnika
                {
                    korzen = korzen->lewy;
                    delete do_usuniecia;
                }
                else
                {
                    korzen = NULL;
                    delete do_usuniecia;
                }
            }
            else
            {
                wezel* IT = korzen;
                bool czyjest = false;
                while(IT->lewy!=NULL || IT->prawy!=NULL)
                {
                    if (IT->klucz==_klucz)
                    {
                        czyjest = true;
                        break;
                    }
                    else
                    {
                        if(_klucz<IT->klucz)
                        {
                            IT = IT->lewy;
                        }
                        else
                        {
                            IT = IT->prawy;
                        }
                    }
                }
                if(czyjest == true)
                {
                    wezel* rodzic = znajdz_rodzica(IT);
                    if(IT->prawy!=NULL)
                    {
                        wezel* nast = nastepnik(IT);
                        if (IT->prawy == nast)
                        {
                            nast->lewy = IT->lewy;
                            if(rodzic->lewy == IT)
                            {
                                rodzic->lewy = nast;
                            }
                            else
                            {
                                rodzic->prawy = nast;
                            }

                        }
                        else
                        {
                            IT->prawy->lewy = nast->prawy;
                            nast->prawy = IT->prawy;
                            nast->lewy = IT->lewy;
                            if (rodzic->lewy == IT)
                            {
                                rodzic->lewy = nast;

                            }
                            else
                            {
                                rodzic->prawy = nast;
                            }
                        }
                        delete IT;
                    }
                    else if (IT->lewy!=NULL)
                    {
                        wezel* rodzic = znajdz_rodzica(IT);
                        if (rodzic->lewy==IT)
                        {
                            rodzic->lewy = IT->lewy;

                        }
                        else
                        {
                            rodzic->prawy = IT->lewy;
                        }
                        delete IT;
                    }
                    else
                    {
                        wezel* rodzic = znajdz_rodzica(IT);
                        if (rodzic->prawy==IT)
                        {
                            rodzic->prawy = NULL;
                        }
                        else
                        {
                            rodzic->lewy = NULL;
                        }
                        delete IT;
                    }
                }
                else
                {
                    cout<<"Nie mozna usunac klucza, który nie istnieje"<<endl;
                }

            }


        }
    }
};



int main()
{
    clock_t begin, end;
    double time_spent;
    begin = clock();
    srand(time(NULL));

    ifstream plik;
    plik.open("inlab03.txt");

    if (plik.good() == true)
    {
        cout << "Plik jest dostepny" <<endl;
        plik.close();
    }

    else cout << "Nie mozna otworzyć pliku" <<endl;
    drzewo *mojedrzewo = new drzewo();
    mojedrzewo->counter=0;
    mojedrzewo->generowanie(1000);
    mojedrzewo->inorder(mojedrzewo->korzen);
    cout << endl << mojedrzewo->counter << endl;


    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    cout << "Program wykonal sie w czasie: " << time_spent<<endl;
    system("PAUSE");
    return 0;
}