#include <iostream>
using namespace std;

class node {
       public:
       int wartosc ;
       node  * lewy ;
       node  * prawy ;
       node(int x) {wartosc=x, lewy=NULL, prawy=NULL;}
 void      dodaj(int x);
 void      usun(int x);
 void      wypisz(node *wsk) ;

       };

node * root ;
/////////////////////////////////////////////
void node::dodaj (int x)
{
	if(root!=NULL) {
		node *q=root, *nowy;
		while(q) {
			if (q->wartosc < x) 
			{
				nowy=q->prawy;
				if(nowy==NULL) 
				{
					q->prawy=new node(x);
					return;
				}
			}
			else
			{
				nowy=q->lewy;
				if(nowy==NULL) 
				{
					q->lewy=new node(x);
					return;
				}
			}
			q=nowy;
			}
	}
	else root=new node(x);
}


////////////////////////////////////////
void node::usun(int x) {

if(root==NULL) {cout << "nie ma co usuwa&#263; - lista jest juz pusta" << endl;return ;}
node * q = root ;
node * rodzic = NULL;

while( (q != NULL) && (q->wartosc!=x)) { 
        cout << "petlu" << endl;
        if(q->wartosc > x )
        {
            rodzic = q ;
            q = q->lewy;
        }
        else if(q->wartosc < x )
        {
           rodzic = q ;
           q = q->prawy;  
        }
}
if(q==NULL)  { cout << "Nie znaleziono elementu do usuniecia" << endl; return ;}
else {
//mamy do czynienia z lisciem?  
if(q->lewy == NULL && q->prawy ==NULL) {
           if(rodzic==NULL) {root=NULL; return ;}
           if(rodzic->lewy==q) {
                               rodzic->lewy=NULL ;
                               delete q ;
                               }
           else {
                rodzic->prawy=NULL;
                delete q ;
                
                }
return ;
}     
//ma tylko lewego syna:
if(q->lewy!=NULL && q->prawy==NULL) {
                 if(rodzic==NULL) {root=q->lewy; return ;}
                 if(rodzic->lewy==q) {
                    rodzic->lewy=q->lewy ;
                    delete q ;
                    return ;
                 }
                 else {
                    rodzic->prawy=q->lewy ;
                    delete q ;
                    return ;  
                      }

}
///ma tylko prawego syna
else if (q->prawy!=NULL && q->lewy==NULL) {
                 if(rodzic==NULL) {root=q->prawy; return ;}
                 if(rodzic->lewy==q) {
                    rodzic->lewy=q->prawy ;
                    delete q ;
                    return ;
                 }
                 else {
                    rodzic->prawy=q->prawy;
                    delete q ;
                    return ;  
                      }

}
/////
else {
     node * wierzejski ;
     node * ojciec_z_wermachtu ;
     ojciec_z_wermachtu=q ; //q->prawy;
     wierzejski=q->prawy ;
     while(wierzejski->lewy!=NULL) {
                                   ojciec_z_wermachtu=wierzejski ;
                                   wierzejski=wierzejski->lewy ;
                                   }
     if(ojciec_z_wermachtu!=q && wierzejski->prawy!=NULL) ojciec_z_wermachtu->lewy=wierzejski->prawy; 
     if(rodzic==NULL) {
                      root=wierzejski;
                      wierzejski->lewy=q->lewy;
                      if(q->prawy!=wierzejski)
                            wierzejski->prawy=q->prawy ;
                         delete q ;
                      }
     else if(rodzic->prawy=q) {
                         rodzic->prawy=wierzejski ;
                         wierzejski->lewy=q->lewy;
                         if(q->prawy!=wierzejski)
                            wierzejski->prawy=q->prawy ;
                         
                         delete q ;
                         }
     else  {
                         rodzic->lewy=wierzejski ;
                         wierzejski->lewy=q->lewy;
                          if(q->prawy!=wierzejski)
                            wierzejski->prawy=q->prawy ;
                         delete q ;
           }
     
     }


}

};
////////////
void node::wypisz(node *wsk)
{
if(wsk) 
	{
	cout<<"(";
    wypisz(wsk->lewy);
	cout<<wsk->wartosc;
	wypisz(wsk->prawy);
	cout<<")";
	}
else cout<<"*";
}
////////////////////////////

/////////////////
int main() {
int x , a ; 
root->dodaj(7) ;
root->dodaj(8) ;
root->dodaj(6) ;
root->dodaj(4) ;
root->dodaj(5) ;
//root->dodaj(9) ;
while (a) {
cout << "implementacja drzewa bst, menu:\n\n" << endl ;
cout << "1 - dodaj element (wartosc)" << endl ;
cout << "2 - usun element (wartosc)" << endl ;    
cout << "3 - wyswietl drzewko" << endl ;
cout << "0 - wyjscie " << endl;
cin >> a ;
switch(a) {
    case 1:
               system("cls");    
               cout << "Podaj wartosc (nie powtarzaj sie:P)" << endl ;
               cin >> x ;
               root->dodaj(x) ;
               cout << "dodano" << endl ;
               system("Pause");    
               break ;
    case 2:
               system("cls");    
               cout << "Podaj wartosc do skasowania" << endl ;
               cin >> x ;
               root->usun(x) ;
               cout << "poszlo w kosmos" << endl ;
               system("Pause");    
               break ;
    case 3:
               system("cls");    
               cout << endl ;
               root->wypisz(root) ;
               cout << endl ;
               system("Pause");    
               break ;
    case 0:
         return 1;
    default:
            break ;
}
}
}