#include <iostream>
 
#define IZLAZ    0
#define GRESKA   -1
#define MAX_EL  200
#define PUNO      1
#define PRAZNO    0
typedef int labeltype;
 
 
#include "bstablo_polje.h"
//#include "bstablo_pokazivac.h"
using namespace std;
 
 
void Dodaj_element(labeltype vrijednost,node n,btree T){
    if(T==NULL) return; 
    if(vrijednost < LabelB(n,T)){
         if(ExistsLeftChildB(n,T))
              Dodaj_element(vrijednost,LeftChildB(n,T),T);
         else
              if(CreateLeftB(vrijednost,n,T)==GRESKA) cout << "Greska" << endl;
    }
    else if(vrijednost > LabelB(n,T)){
         if(ExistsRightChildB(n,T))
              Dodaj_element(vrijednost,RightChildB(n,T),T);
         else
              if(CreateRightB(vrijednost,n,T)==GRESKA) cout << "Greska" << endl;
    }
}
void Ispis_stabla(node n,btree T){
   if(T==NULL) return;
   cout << " " << n <<  "  :  " << LabelB(n,T) << endl;
   if(ExistsLeftChildB(n,T)){
       Ispis_stabla(LeftChildB(n,T),T);
   }
   if(ExistsRightChildB(n,T)){
       Ispis_stabla(RightChildB(n,T),T);
   }   
}
node Vrati_adresu(labeltype v,node n,btree T){
  if(T==NULL) return NULL;
  while(n != IZLAZ){
       if(v == LabelB(n,T)) return n;
       else if(v < LabelB(n,T)){
            if(ExistsLeftChildB(n,T))
                 n = LeftChildB(n,T);
            else return 0;
       }
       else if(v > LabelB(n,T)){
            if(ExistsRightChildB(n,T))
                 n = RightChildB(n,T);    
            else return 0;
       }
  }
  return 0;
}
void Obrisi_vrijednost(labeltype vrijednost,node n,btree T){
   if(T==NULL) return;
   if(vrijednost == LabelB(n,T)) DeleteB(n,T);
   else{
       if(ExistsLeftChildB(n,T)){
           Obrisi_vrijednost(vrijednost,LeftChildB(n,T),T);
       }
       if(ExistsRightChildB(n,T)){
           Obrisi_vrijednost(vrijednost,RightChildB(n,T),T);
       }   
   }
}
void Premjesti_zapis(node n,btree T,btree pom){
   if(T==NULL || pom==NULL) return;
   Dodaj_element(LabelB(n,T),RootB(pom),pom);
   if(ExistsLeftChildB(n,T))
          Premjesti_zapis(LeftChildB(n,T),T,pom);
   if(ExistsRightChildB(n,T))
          Premjesti_zapis(RightChildB(n,T),T,pom);
}
 
int main(){
    int korijen,vrijednost,brisi,mj1,mj2;
    btree stablo,pom;
    stablo = NULL;
    pom = NULL;
    int izbor;
    node adr1,adr2;
    bool jep;
 
    do{
        system("cls");
        cout<<"-----------------------------------"<<endl;
        cout<<" 1. korijen stabla (root)"<<endl;
        cout<<" 2. dodaj element"<<endl;
        cout<<" 3. ispis stabla"<<endl;
        cout<<" 4. obrisi vrijednost"<<endl;
        cout<<" 5. roditelj"<<endl;
        cout<<" 6. promijeni vrijednost"<<endl;
        cout<<" 9. izlaz"<<endl;;
        cout<<"-----------------------------------"<<endl;
        cin >> izbor;
        cout<<"\n\n";
        switch(izbor){
            case 1: if(ExistsLeftChildB(RootB(stablo),stablo) || ExistsRightChildB(RootB(stablo),stablo)) break;
                    cout << "Vrijednost korjena: "; cin >> korijen;
                    stablo = InitB(korijen,stablo);
                    break;
            case 2: 
                    do{
                       cout << "Vrijednost: "; cin >> vrijednost;
                       if(vrijednost!=-1) Dodaj_element(vrijednost,RootB(stablo),stablo);
                       cout<<"---"<<endl;
                       Ispis_stabla(RootB(stablo),stablo);
                       cout<<"---"<<endl;
                    }while(vrijednost != -1);
                    break;
           case 3: Ispis_stabla(RootB(stablo),stablo);
                   break;
           case 4: printf("Brisi vrijednost: "); scanf("%d",&brisi);
                   jep=false;
                   if(brisi==LabelB(RootB(stablo),stablo)) jep=true;
                   Obrisi_vrijednost(brisi,RootB(stablo),stablo);
                   if(jep){
                       cout << "Vrijednost korijena: "; cin >> korijen;
                       stablo = InitB(korijen,stablo);                                                              
                   }
                   Ispis_stabla(RootB(stablo),stablo);
                   break;
           case 5: cout << "Roditelj od: "; cin >> vrijednost;
                   adr1 = Vrati_adresu(vrijednost,RootB(stablo),stablo);
                   cout << "Adresa trazenog:  " << adr1 << endl;
                   adr2 = ParentB(adr1,stablo);
                   cout << "Adresa roditelja: " << adr2 << endl;
                   if(adr1 == 0){
                         cout<<"Nema tog elementa\n"; 
                         break;
                   }
                   if(adr2 == 0){
                         cout<<"Korijen\n";
                         break;
                   }
                   printf("   je ->  %d\n",LabelB(adr2,stablo));
                   break;
           case 6: if(stablo==NULL) break;
                   Ispis_stabla(RootB(stablo),stablo);
                   cout << "\nPromjeniti vrijednost: "; cin >> mj1; 
                   cout << "Na vrijednost: "; cin >> mj2;
                   adr1 = Vrati_adresu(mj1,RootB(stablo),stablo);
                   if(adr1==NULL){
                        cout<<"Nema te vrijednosti\n";
                        break;
                   }
                   ChangeLabelB(mj2,Vrati_adresu(mj1,RootB(stablo),stablo),stablo);
                   if(pom!=NULL) Obrisi_vrijednost(LabelB(RootB(pom),pom),RootB(pom),pom);
                   pom = InitB(LabelB(RootB(stablo),stablo),pom);
                   Premjesti_zapis(RootB(stablo),stablo,pom);
                   Obrisi_vrijednost(LabelB(RootB(stablo),stablo),RootB(stablo),stablo);
                   stablo = InitB(LabelB(RootB(pom),pom),stablo);
                   Premjesti_zapis(RootB(pom),pom,stablo);
        } 
        cout<<"\n\n--------------------\n";
        system("pause");
    }while(izbor!=9);
}