#include <iostream>
 
#define LAMBD 0
#define POGRESKA -1
#define M_ELE 200
#define PUNO 1
#define NISTA 0
typedef int labeltype;
 
//#include "bin_stablo_pokazivac.h"
#include "bin_stablo_polje.h"
 
using namespace std;
 
#ifdef BSTABLO_POLJE_H
void ispisi(btree t){
    if(t==NULL) return;
    node n;
    for(n=0; n<M_ELE;n++)
       if(t->elements[n].used==1) 
           cout << n << " :: " << LabelB(n,t) << endl;
}
#endif
 
void DodajElement(labeltype vrijednost,node n,btree T){
    if(T==NULL) return; 
    if(vrijednost < LabelB(n,T)){
         if(ExistsLeftChildB(n,T))
              DodajElement(vrijednost,LeftChildB(n,T),T);
         else
              if(CreateLeftB(vrijednost,n,T)==POGRESKA) cout << "Pogreska" << endl;
    }
    else if(vrijednost > LabelB(n,T)){
         if(ExistsRightChildB(n,T))
              DodajElement(vrijednost,RightChildB(n,T),T);
         else
              if(CreateRightB(vrijednost,n,T)==POGRESKA) cout << "Pogreska" << endl;
    }
}
void IspisiStabla(node n,btree T){
   if(T==NULL) return;
   cout << " " << n <<  "  :  " << LabelB(n,T) << endl;
   if(ExistsLeftChildB(n,T)){
       IspisiStabla(LeftChildB(n,T),T);
   }
   if(ExistsRightChildB(n,T)){
       IspisiStabla(RightChildB(n,T),T);
   }   
}
node VratiAdresu(labeltype v,node n,btree T){
  if(T==NULL) return NULL;
  while(n != LAMBD){
       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 BrisiVrijednost(labeltype vrijednost,node n,btree T){
   if(T==NULL) return;
   if(vrijednost == LabelB(n,T)) DeleteB(n,T);
   else{
       if(ExistsLeftChildB(n,T)){
           BrisiVrijednost(vrijednost,LeftChildB(n,T),T);
       }
       if(ExistsRightChildB(n,T)){
           BrisiVrijednost(vrijednost,RightChildB(n,T),T);
       }   
   }
}
void PremjestiZapis(node n,btree T,btree pom){
   if(T==NULL || pom==NULL) return;
   DodajElement(LabelB(n,T),RootB(pom),pom);
   if(ExistsLeftChildB(n,T))
          PremjestiZapis(LeftChildB(n,T),T,pom);
   if(ExistsRightChildB(n,T))
          PremjestiZapis(RightChildB(n,T),T,pom);
}
 
int main(){
    int root,vrj,bri,mj1,mj2;
    btree stablo,pom;
    stablo = NULL;
    pom = NULL;
    int izb;
    node adr1,adr2;
    bool jep;
 
    do{
        system("cls");
        printf(" 1. Funkcija Root\n");
        printf(" 2. Funkcija Dodaj element\n ");
        printf("3. Funkcija Ispis stabla\n");
        printf(" 4. Funkcija Brisi vrijednost\n ");
        printf("5. Funkcija roditelj\n");
        printf(" 6. Funkcija ChangeLabelB\n ");
        printf("9. Exit");
        printf("\n--------------------\n Izbor : ");
        cin >> izb;
        printf("\n\n");
        switch(izb){
            case 1: if(ExistsLeftChildB(RootB(stablo),stablo) || ExistsRightChildB(RootB(stablo),stablo)) break;
                    cout << "Vrijednost korijena: "; cin >> root;
                    stablo = InitB(root,stablo);
                    break;
 
            case 2: printf(" # Za prekid unosa koristiti -1 #\n");
                    do{
                       cout << "Vrijednost: "; cin >> vrj;
                       if(vrj!=-1) DodajElement(vrj,RootB(stablo),stablo);
                       printf("\n*****************\n");
                       IspisiStabla(RootB(stablo),stablo);
                       printf("\n*****************\n");
                    }while(vrj != -1);
                    break;
 
           case 3: IspisiStabla(RootB(stablo),stablo);
                   #ifdef BSTABLO_POLJE_H
                   printf("\n\n -- polje --\n\n");
                   ispisi(stablo);
                   #endif
                   break;
 
           case 4: printf("Brisi vrijednost: "); scanf("%d",&bri);
                   jep=false;
                   if(bri==LabelB(RootB(stablo),stablo)) jep=true;
                   BrisiVrijednost(bri,RootB(stablo),stablo);
                   if(jep){
                       cout << "Vrijednost korijena: "; cin >> root;
                       stablo = InitB(root,stablo);                                                              
                   }
                   IspisiStabla(RootB(stablo),stablo);
                   break;
           case 5: cout << "Roditelj od: "; cin >> vrj;
                   adr1 = VratiAdresu(vrj,RootB(stablo),stablo);
                   cout << "Adresa trazenog:  " << adr1 << endl;
                   adr2 = ParentB(adr1,stablo);
                   cout << "Adresa roditelja: " << adr2 << endl;
                   if(adr1 == 0){
                         printf("Nema tog elementa\n"); 
                         break;
                   }
                   if(adr2 == 0){
                         printf("Korijen\n");
                         break;
                   }
                   printf("   je ->  %d\n",LabelB(adr2,stablo));
                   break;
           case 6: if(stablo==NULL) break;
                   IspisiStabla(RootB(stablo),stablo);
                   cout << "\nPromjeniti vrijednost: "; cin >> mj1; 
                   cout << "Na vrijednost: "; cin >> mj2;
                   adr1 = VratiAdresu(mj1,RootB(stablo),stablo);
                   if(adr1==NULL){
                        printf("Nema te vrijednosti\n");
                        break;
                   }
                   ChangeLabelB(mj2,VratiAdresu(mj1,RootB(stablo),stablo),stablo);
                   if(pom!=NULL) BrisiVrijednost(LabelB(RootB(pom),pom),RootB(pom),pom);
                   pom = InitB(LabelB(RootB(stablo),stablo),pom);
                   PremjestiZapis(RootB(stablo),stablo,pom);
                   BrisiVrijednost(LabelB(RootB(stablo),stablo),RootB(stablo),stablo);
                   stablo = InitB(LabelB(RootB(pom),pom),stablo);
                   PremjestiZapis(RootB(pom),pom,stablo);
        } /*switch*/
        printf("\n\n--------------------\n");
        system("pause>NUL");
    }while(izb!=9);
}