#include<iostream>
using namespace std;

struct element{
       int vrijednost;
       int koristeno;
};
struct bstablo{
       element polje[10000];
};
int trazi(int n, bstablo *B) {
        return n;
}
void InitB(int x, bstablo *B){
     for(int i=0;i<10000;i++){
             B->polje[i].vrijednost=-1;
             B->polje[i].koristeno=0;
     }
     B->polje[1].vrijednost=x;
     B->polje[1].koristeno=1; 
}
element *ParentB(int n,bstablo *B){
        element *roditelj=new element;
        roditelj->vrijednost=-1;
        roditelj->koristeno=0;
        if(n<=1){
                 cout<<"Korijen stabla nema roditelja jer je on prvi cvor u stablu."<<endl;
                 return roditelj;
        }
        else{
             n/=2;
             roditelj->vrijednost=B->polje[n].vrijednost;
             roditelj->koristeno=B->polje[n].koristeno;
             return roditelj;
        }
       
}
element *LeftChildB(int n, bstablo *B){
        element *novo=new element;
        if(B->polje[n*2].koristeno==0){
                                       cout<<"Lijevo dijete ne postoji"<<endl;
                                       novo->vrijednost=-1;
                                       novo->koristeno=0;
                                       return novo;
        }
        else{
            novo->vrijednost=B->polje[n*2].vrijednost;
            novo->koristeno=B->polje[n*2].koristeno;
            return novo;
            }
}
element *RightChildB(int n, bstablo *B){
        element *novo=new element;
        if(B->polje[n*2+1].koristeno==0){
                                       cout<<"Desno dijete ne postoji"<<endl;
                                       novo->vrijednost=-1;
                                       novo->koristeno=0;
                                       return novo;
        }
        else{
            novo->vrijednost=B->polje[n*2+1].vrijednost;
            novo->koristeno=B->polje[n*2+1].koristeno;
            return novo;
            }
}
int LabelB(int n, bstablo *B){
    return B->polje[n].vrijednost;
}
void ChangeLabelB(int x, int n, bstablo *B){
     if(B->polje[n].koristeno==1){
                                  B->polje[n].vrijednost=x;
                                  }
     else
          cout<<"Taj cvor ne postoji"<<endl;
}
element *RootB(bstablo *B){
        element *novi=new element;
        if(B->polje[1].koristeno==1){
                                     novi->vrijednost=B->polje[1].vrijednost;
                                     novi->koristeno=1;
                                     return novi;
        }
        else
             cout<<"Stablo je prazno"<<endl;
             novi->vrijednost=B->polje[1].vrijednost;
             novi->koristeno=B->polje[1].koristeno;
             return novi;
}
void CreateLeftB(int x, int n, bstablo *B){
     if(B->polje[n*2].koristeno==1){
                                    cout<<"Taj cvor vec ima lijevo dijete."<<endl;
     }
     else{
          B->polje[n*2].koristeno=1;
          B->polje[n*2].vrijednost=x;
     }
}
void CreateRightB(int x, int n, bstablo *B){
     if(B->polje[n*2+1].koristeno==1){
                                    cout<<"Taj cvor vec ima desno dijete."<<endl;
     }
     else{
          B->polje[n*2+1].koristeno=1;
          B->polje[n*2+1].vrijednost=x;
     }
}
void DeleteB(int n, bstablo *B){
     if(B->polje[n].koristeno==0){
                                  cout<<"Taj cvor ne postoji"<<endl;
     }
     else{
          B->polje[n].koristeno=0;
          B->polje[n].vrijednost=-1;
          n*=2;                               
     while(B->polje[n].koristeno==1 || B->polje[n+1].koristeno==1){
                                     B->polje[n].koristeno=0;
                                     B->polje[n].vrijednost=-1;
                                     B->polje[n+1].koristeno=0;
                                     B->polje[n+1].vrijednost=-1;                               
                                     n*=2;
     }
     }
}