#include <iostream>
using namespace std;


//charmap w uruchom
//  \xDB  -> zamalowany kwadracik
//  \xC4  -> kreska pozioma
//  \xB3  -> kreska pionowa
//  \xC0  -> kolanko dół,prawo
//  \xDA  -> kolanko góra,prawo

class Drzewo
  {
   private:
   class Wezel
     {
      public:
      double Dane;
      unsigned licznik;
      Wezel *L,*P;
      Wezel(double Dane):Dane(Dane),L(0),P(0), licznik(0) {}
     };
   Wezel *K;
   void __clear(Wezel *); //  __  <- bardzo niebezpieczna funkcja - uwaga z wywołaniami etć etć etć ;
                          // tutaj np - nie ma sprawdzania poprawności danych (W == 0 też zwalniane);
   void _clear() {if (K) __clear(K);}
   void _show(unsigned short how) { if (how == 0) {if(K) __show(K);} else if (how == 1) {if(K) __show_tree(K,0);} else if (how == 2) {if(K) __show_tree_graphic(K,0,0);} }
   void __show(Wezel *tmp); // bardzo niebiezpieczne nie sprawdza tmp==0
   void __show_tree(Wezel *tmp,unsigned deep); // bardzo niebiezpieczne nie sprawdza tmp==0
   void __show_tree_graphic(Wezel *tmp,unsigned deep,unsigned long long path); //znowu nic nie sprawdza...
   public:
   Drzewo():K(0) {}
   ~Drzewo() { _clear(); }
   bool Add(double Dane);
   bool Find(double s);
   void Show() { _show(0); }
   void ShowTree() { _show(1); }
   void ShowTreeGraphic () { _show(2); }
   //   Wezel Szukaj(double s);
  };


//dodajemy poziomiki
//dwa poprzednie takie same - nic, różne - kreska.
void Drzewo::__show_tree_graphic(Wezel *tmp,unsigned deep,unsigned long long path)
  {
     if (tmp->Dane == 5)
        {
                   cout<<"... deep="<<deep<<" path=";
                   for (int i = 4; i >= 0; i--)
                       {
                            if (path>>i & 1 == 1) cout <<"1"; else cout <<"0";
                       }
                   cout<<endl;
        }

   if(tmp->L) __show_tree_graphic(tmp->L,deep+1,path<<1);
   //jeżeli dwa poprzednie są takie same to puste, inaczej - kreska
   unsigned long long int d;
   for (unsigned i=deep; i > 0; i--)
   {
//       if (path & 1 == 1 || path == 0)
       {
           d = (path >> (i-1)) & 3; //nie do końca wiem--_--'
//  if (path == 14)        cout<<"d="<<d;
           if ( (deep == 1 || d == 1) && path != 1) {cout<<" ";}
           else
           {
                         if (d == 0 || d == 3) cout<<" "; else cout<<"\xB3";
           }
           cout<<" ";
       }
   }
   
   if (deep)
   {
         if(path&1) cout<<"\xC0"; else cout<<"\xDA";
         cout<<"\xC4";
   }
   cout << "\xDB "<<tmp->Dane;// << " " << tmp->licznik;
//   cout << " : " << path;
   cout <<endl;
   if(tmp->P) __show_tree_graphic(tmp->P,deep+1,(path<<1)|1);
    
  }


void Drzewo::__show(Wezel *tmp) //inorder
  {
   if(tmp->L) __show(tmp->L);
   cout<<tmp->Dane << " " << tmp->licznik <<endl;
   if(tmp->P) __show(tmp->P);
  }
  
void Drzewo::__show_tree(Wezel *tmp,unsigned deep) //inorder
  {
   if(tmp->L) __show_tree(tmp->L,deep+1);
   for (unsigned d=deep; d > 0; d--)
       cout << "   ";
   cout<<tmp->Dane << ":" << tmp->licznik+1 <<endl;
   if(tmp->P) __show_tree(tmp->P,deep+1);
  }

//Liści jest zawsze 2*elementy + 1 - nie zależnie od wyglądu drzewa.
void Drzewo::__clear (Wezel *W) //przegladanie preorder
  { //uzasadnienie użycia metody z __
    if (W->L) __clear (W->L); // sprawdziłem przed wywołaniem - czego ta funkcja sama z siebie nie robi
    if (W->P) __clear (W->P); // sprawdziłem przed wywołaniem - czego ta funkcja sama z siebie nie robi
    delete W;
    
  }
     

bool Drzewo::Find(double s)
  {
     Wezel *Now = K;
     ;
     while (Now)
     {
           if (Now -> Dane == s)   return true;
           else if (Now->Dane < s) Now = Now->P;
           else Now = Now->L;
     }
     return false;
  }

bool Drzewo::Add(double Dane)
  {
   Wezel *R=0,*tmp=K;
   bool F=false;
   while(tmp)
     {
      R=tmp;
      
      //if(tmp->Dane==Dane) return false;
      //F=tmp->Dane>Dane;
      //tmp=F?tmp->L:tmp->P;

      if(tmp->Dane>Dane) { tmp=tmp->L; F=true; }
      else if(tmp->Dane<Dane) { tmp=tmp->P; F=false; }
      else 
       {
           tmp->licznik++;
           return false;
       }
     }
   if(!R) K=new Wezel(Dane);
   else (F?R->L:R->P)=new Wezel(Dane);
  }

int main()
  {
   Drzewo D;
   bool Find = false;
   D.Add(3);
   D.Add(1);
   D.Add(5);
   D.Add(0);
   D.Add(2);
   D.Add(4);
   D.Add(6);
   D.Add(-1);
   D.Add(8);
   D.Add(-2);
   D.Add(7);
   D.Add(0);
   D.Add(2);
   cout<<"Szukaj(4)="<<(D.Find(4)?"T":"F")<<endl;
   cout<<"Szukaj(7)="<<(D.Find(7)?"T":"F")<<endl;
cout<<endl<<endl<<endl;
   cout<<"Szukaj(2.5)="<<(D.Find(2.5)?"T":"F")<<endl;
   D.Show();
   D.ShowTree();
   D.ShowTreeGraphic();
   system("Pause");
   return 0;
  }