#include <iostream>
using namespace std;

struct elementi{
  char oznaka[10];
  int firstchild, nextsibling;
  bool root;
};

struct treet{
  elementi elements[1000];
  int first;
};

void InitT(int korijen, treet *stablo){
  for(int i=0; i<1000; i++){
    stablo->elements[i].firstchild = -1;
    stablo->elements[i].nextsibling = -1;
    stablo->elements[i].root = 0;
  }
  stablo->first = korijen;
  stablo->elements[korijen].root = 1;
  cout << "Unesite labelu korijena stabla: ";
  cin >> stablo->elements[korijen].oznaka;
}

int RootT(treet *stablo){
  return stablo->first;
}

int FirstChildT(int cvor, treet *stablo){
  return stablo->elements[cvor].firstchild;
}

int NextSiblingT(int cvor, treet *stablo){
   return stablo->elements[cvor].nextsibling;
}

int ParentT(int cvor, treet *stablo){
  for(int i=0; i<1000; i++){
    if(stablo->elements[i].firstchild == cvor)
      return i;
    else if(stablo->elements[i].nextsibling == cvor)
      ParentT(i, stablo);
  }
  return -1;
}

void LabelT(int cvor, treet *stablo){
  if(stablo->elements[cvor].root == 0){
    cout << "-1";
  }
  else{
    cout << stablo->elements[cvor].oznaka;
  }
}


void CreateT(int dijete, int cvor, treet *stablo){
  if(stablo->elements[cvor].root == 0)
    cout << "Cvor kojem stvarate djete ne postoji te djete nije stvoreno" << endl;
  else if(stablo->elements[cvor].firstchild == -1){  //lijevo dijete
    stablo->elements[cvor].firstchild = dijete;
    stablo->elements[dijete].root = 1;
    cout << "Unesite labelu cvora: ";
    cin >> stablo->elements[dijete].oznaka;
  }
  else{  // desno dijete
    int brat;
    bool ima = true;
    brat = stablo->elements[cvor].firstchild;
    do{
      if(stablo->elements[brat].nextsibling==-1) ima = false;
      else brat = stablo->elements[brat].nextsibling;
    }while(ima);
   
    stablo->elements[brat].nextsibling = dijete;
    stablo->elements[dijete].root = 1;
    cout << "Unesite labelu cvora: ";
    cin >> stablo->elements[dijete].oznaka;
  }
}

void ChangeLabelT(char x[10], int cvor, treet *stablo){
  if(stablo->elements[cvor].root == 1)
    strcpy(stablo->elements[cvor].oznaka, x);
  else cout << "Zadani cvor ne postoji. " << endl;
}

void brisi(int cvor, treet *stablo){
  if(stablo->elements[cvor].nextsibling == -1 && stablo->elements[ParentT(cvor,stablo)].firstchild == cvor){
    stablo->elements[ParentT(cvor,stablo)].firstchild = -1;
    stablo->elements[ParentT(cvor,stablo)].root = 0;
    strcpy(stablo->elements[cvor].oznaka,"-1");
   
  }
 
  else if(stablo->elements[cvor].nextsibling != -1 && stablo->elements[ParentT(cvor,stablo)].firstchild == cvor)
    stablo->elements[ParentT(cvor,stablo)].firstchild = stablo->elements[cvor].nextsibling;
   
  else{
    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;
  }
}

void DeleteT(int cvor, treet *stablo){
  if(stablo->elements[cvor].root == 0)
    cout << "Uneseni cvor ne postoji" << endl;
  else 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);
}