#include <cstring>
#include <iostream>
using namespace std;
struct elem{
string label;
int firstchild;
int nextsibling;
bool flag;
};
struct tr{
struct elem elements[10000];     
int first;
};
typedef struct tr tree;
typedef int node;
 
void InitT(int korijen, tree *stablo){
 stablo->first=korijen;
 stablo->elements[korijen].firstchild=-1;
 stablo->elements[korijen].nextsibling=-1;
}
 
int ParentT(int cvor, tree *stablo){
  if(stablo->first==cvor){
   return -1;
   cout<<"Cvor je korijen\n";                       
   }  
   for (int i=0;i<10000;i++){
   if(stablo->elements[i].firstchild==cvor)
   return i;
   else if(stablo->elements[i].nextsibling==cvor){
        ParentT(i,stablo);
   }
   }
   return -1;
   cout<<"Cvor ne postoji...\n";
}
int FirstChildT(int cvor, tree *stablo){
 if(stablo->elements[cvor].firstchild==-1) {
 cout<<"Zadani cvor je list...\n";
 return -1;
 }
 else
 return stablo->elements[cvor].firstchild;  
}
int NextSiblingT(int cvor, tree *stablo){
if(stablo->elements[cvor].nextsibling==-1){
 cout<<"Cvor je najdesnije dijete...\n";
 return -1;                                          
}
else
return stablo->elements[cvor].nextsibling;
}
 
void LabelT(int cvor, tree *stablo){
if(stablo->elements[cvor].flag==false)
{
cout<<"Taj cvor ne postoji...\n";
return;
}
else
 cout<<"Label na cvoru "<<cvor<<" je: "<<stablo->elements[cvor].label<<endl;     
}
int RootT(tree *stablo){
 return stablo->first;   
}
 
void CreateT(int dijete, int cvor, tree *stablo){
 if(stablo->elements[cvor].firstchild==-1){
 stablo->elements[cvor].firstchild=dijete;
 stablo->elements[dijete].firstchild=-1;
 stablo->elements[dijete].nextsibling=-1;
 stablo->elements[dijete].flag=true;
 cout<<"\nKoju vrijednost zelite unijeti za LABEL: ";
 getline(cin,stablo->elements[dijete].label);
}
 else{
  int Brat;
  bool imaBrata=true;
  //" "brute force" rekurzija" 
  Brat=stablo->elements[cvor].firstchild;
  do{
      //ako ne postoji sljedeci brat onda ga dodaj tj izbij iz do while
      if(stablo->elements[Brat].nextsibling==-1)
       imaBrata=false;
      else{
          //ako ima brata onda preskoci na njega u testiranju
          Brat=stablo->elements[Brat].nextsibling;
}//else
  }while(imaBrata);
  //dodaj brata
  stablo->elements[Brat].nextsibling=dijete;  
  stablo->elements[dijete].firstchild=-1;
  stablo->elements[dijete].nextsibling=-1;  
  stablo->elements[dijete].flag=true;
  cout<<"\nKoju vrijednost zelite unijeti za LABEL: ";
 getline(cin,stablo->elements[dijete].label);
 }//else
}//CreateT
 
void ChangeLabelT(string x, int cvor, tree *stablo){
 stablo->elements[cvor].label=x; 
}
 
void brisi(int cvor, tree *stablo){
 
     if(stablo->elements[cvor].nextsibling==-1&&stablo->elements[ParentT(cvor,stablo)].firstchild==cvor){//ako ima samo 1 dijete
          stablo->elements[ParentT(cvor,stablo)].firstchild=-1;
         stablo->elements[cvor].flag=false;     
            }
     else if(stablo->elements[cvor].nextsibling!=-1&&stablo->elements[ParentT(cvor,stablo)].firstchild==cvor){//ako ima vise djece a brisemo prvo
         stablo->elements[ParentT(cvor,stablo)].firstchild=stablo->elements[cvor].nextsibling;
         stablo->elements[cvor].flag=false;   
          }
     else{//brisanje u sred djece
        int brat=stablo->elements[ParentT(cvor,stablo)].firstchild;
        while(stablo->elements[brat].nextsibling!=cvor){
        brat=stablo->elements[brat].nextsibling;                                                
        }
        stablo->elements[brat].nextsibling=stablo->elements[cvor].firstchild;
        stablo->elements[cvor].flag=false;
          }
}
void DeleteT(int cvor,tree *stablo){
 if(stablo->elements[cvor].firstchild!=-1){
 while(stablo->elements[cvor].firstchild!=-1){
 brisi(stablo->elements[cvor].firstchild,stablo);
  }
 brisi(cvor,stablo);                                        
 }    
else
brisi(cvor,stablo);
}