

#include 
#include 
#include 
#define ARRAYSIZE 10000
using namespace std;

/*ALGORITMI ZA MANIPULACIJU SA STABLIMA*/
/*REALIZACIJA PREKO POLJA*/

struct tdata{
  char label[20];
  int firstChild;
  int nextSibling;
};

struct tree{
  tdata data[ARRAYSIZE];
  int first;
};

void createChild(int x, tree *t){
    cout << "Uneiste ime djeteta: ";
    cin >> t->data[x].label;
    t->data[x].firstChild = -1;
    t->data[x].nextSibling = -1;
}

int Root(tree *t){
  return t->first;
}

tree* Init(int x, tree *t){
  t = new tree;
  t->first = x;
  createChild(x,t);
  for(int i=0; idata[i].label,"");
  t->data[i].firstChild = -1;
  t->data[i].nextSibling = -1;       
  }
  return t;
}

char* Label(int n, tree *t){
  return t->data[n].label;
}

void ChangeLabel(char *x, int n, tree *t){
  strcpy(t->data[n].label,x);
}

void Create(int x, int n, tree *t){
  if(t->data[n].firstChild==-1){
    t->data[n].firstChild = x;
    createChild(x,t);
    cout << "Djete " << t->data[x].label << " je pridruzeno roditelju " << t->data[n].label << endl;
    return;
  }
  int brother = t->data[n].firstChild;
  while(true)
    if(t->data[brother].nextSibling==-1)
      break;
    else
      brother = t->data[brother].nextSibling;
  t->data[brother].nextSibling = x;
  createChild(x,t);
  cout << "Djete " << t->data[x].label << " je pridruzeno roditelju " << t->data[n].label << endl;
}

int Parent(int n, tree *t){
  if(t->first==n)
    return -1;
  else
    for(int i=0; idata[i].firstChild==n)
        return i;
      else if(t->data[i].nextSibling==n)
        return Parent(i,t);
  return -1;
}

int FirstChild(int n, tree *t){
  return t->data[n].firstChild;
}

int NextSibling(int n, tree *t){
  return t->data[n].nextSibling;
}

void Delete(int n, tree *t, bool prvi=true){
  if(t->data[n].firstChild != -1){
    Delete(t->data[n].firstChild,t, false);
    t->data[n].firstChild = -1;
    strcpy(t->data[n].label,"");
  }
  if(t->data[n].nextSibling != -1){
    if(prvi){ // ukoliko je prvi krug
      if(t->data[Parent(n,t)].firstChild==n){ //ukoliko sam ja prvo djete, onda je moj brat sljedece djete
        t->data[Parent(n,t)].firstChild=t->data[n].nextSibling;
        t->data[n].nextSibling = -1;
        strcpy(t->data[n].label,"");
      } else {//Inace pronađi ko ima pokazivač na mene
          int brother = t->data[Parent(n,t)].firstChild; //Ovo je prvo djete mojeg roditelja
          while(true)
            if(t->data[brother].nextSibling==n)
              break;
            else
              brother = t->data[brother].nextSibling;
          t->data[brother].nextSibling = t->data[n].nextSibling;
          t->data[n].nextSibling = -1;
          strcpy(t->data[n].label,"");                 
      }
    } else {
        Delete(t->data[n].nextSibling,t, false);
        t->data[n].nextSibling = -1;
        strcpy(t->data[n].label,"");
    }
  }
  if(t->data[n].firstChild==t->data[n].nextSibling)
    strcpy(t->data[n].label,"");
}

/*ALGORITMI OBILASKA STABLA*/

void Preorder(tree *t, int n){
   if(n==-1) return;
   cout << t->data[n].label << endl;
   Preorder(t, FirstChild(n, t));
   Preorder(t, NextSibling(n, t));      
}

void Inorder(tree *t, int n){
   if(n==-1)return;
   Inorder(t, FirstChild(n, t));
   cout << t->data[n].label << endl;
   Inorder(t, NextSibling(n, t)); 
}

void Postorder(tree *t, int n){
   if(n==-1)return;
   Preorder(t, FirstChild(n, t));
   Preorder(t, NextSibling(n, t));
   cout << t->data[n].label << endl;     
}

/*ALGORITAM ZA CRTANJE STABLA*/
/*Napomena:
   -algoritam za iscrtavanje koji je naveden u ovom primjeru je prvi algoritam kojega sam napisao za ovu svrhu, te kao takav je dosta ne strukturiran. Ukoliko želite bolje strukturirani kod, pogledajte kod za iscrtavanje binarnog stabla
*/

int indeks_prepisa, num;

void pomCrtaj(tree *t, int m[][5]){
/*Iscrtavanje sadržaja na ekran prema prosljeđenim parametrima*/
    int gdrive = 9;
    int gmode = 2;
    initgraph(&gdrive, &gmode, "");
    setbkcolor(WHITE);
    setcolor(BLACK);
    cleardevice();    
    for(int i=0; idata[n].label,"")) p[indeks_prepisa++] = n;
   Prepisi(t, NextSibling(n,t),p);      
}

void Prebroji(tree *t, int n){
   if(n==-1) return;
   Prebroji(t, FirstChild(n,t));
   if(strcmp(t->data[n].label,"")) num++;
   Prebroji(t, NextSibling(n,t));      
}

void Poravnaj(int m[][5]){
/*Provjera koeficijenata smjera, ukoliko susjedi imaju isti koeficijent smjera
to znači da se nalaze na istom pravcu i to treba promjeniti*/
     for(int i=1; i