typedef char TIP;
struct elem
{
    TIP vrij;
    int c, b;
};  //struct elem

class tr
{
    public:
        elem el[1000];
        int R;
        bool o;

        tr()
        {
            //potrebno za InitT(x, T)
            o = false;
        }
};  //class tr


int FirstChildT(int n, tr T)
{
    return T.el[n].c;
}  //int FirstChildT(int n, tr T)


int NextSiblingT(int n, tr T)
{
    return T.el[n].b;
}  //int NextSiblingT(int n, tr T)


void parentPomT(int &rod, int n, int r, int d, tr T)
{
    if(rod != -1) return;  //ako je rod drugaciji, znaci da je rod pronadjen pa prekini rekurzije
    if(d == n)
    {
        rod = r;
        return;
    }  //if(d == n)

    if(FirstChildT(d, T) != -1) parentPomT(rod, n, d, FirstChildT(d, T), T);
    if(rod != -1) return;  //ako je rod drugaciji, znaci da je rod pronadjen pa prekini rekurzije
    if(NextSiblingT(d, T) != -1) parentPomT(rod, n, r, NextSiblingT(d, T), T);
}  //void parentPomT(int &rod, int n, int r, int d, tr T)


int ParentT(int n, tr T)
{
    if(T.R == n || FirstChildT(T.R, T) == -1) return -1;  //ako je n cvor ili ako stablo ima samo cvor, javi gresku
    int rod = -1;
    parentPomT(rod, n, T.R, FirstChildT(T.R, T), T);

    return rod;
}  //int ParentT(int n, tr T)


TIP LabelT(int n, tr T)
{
    return T.el[n].vrij;
}  //TIP LabelT(int n, tr T)


int RootT(tr T)
{
    return T.R;
}  //int RootT(tr T)


void CreateT(TIP x, int n, tr &T)
{
    int pm = -1;
    for(int i = 0; pm == -1; i++)  //treba naci prazno mjesto u polju
        if(T.el[i].vrij == '\0') pm = i;

    T.el[pm].vrij = x;
    T.el[pm].c = -1;
    T.el[pm].b = -1;

    if(FirstChildT(n, T) == -1) T.el[n].c = pm;  //ako n nema djece, posao je kraci
    else  //ako ima... treba naci trenutno najmladje djete i reci mu da ima bracu
    {
        int t = FirstChildT(n, T);
        while(NextSiblingT(t, T) != -1) t = NextSiblingT(t, T);
        T.el[t].b = pm;
    }  //if(FirstChildT(n, T) == -1) : else
}  //void CreateT(elem x, int n, tr &T)


void ChangeLabelT(TIP x, int n, tr &T)
{
    T.el[n].vrij = x;
}  //void ChangeLabelT(TIP x, int n, tr &T)


void DeletePomT(int n, tr &T)
{
    if(FirstChildT(n, T) != -1) DeletePomT(FirstChildT(n, T), T);
    if(NextSiblingT(n, T) != -1) DeletePomT(NextSiblingT(n, T), T);
    T.el[n].vrij = '\0';
    T.el[n].c = -1;
    T.el[n].b = -1;
}  //void DeletePomT(int n, tr &T)


void DeleteT(int n, tr &T)
{
    //treba znati roditelja kako bi se braca mogla urediti
    int rod = -1;
    rod = ParentT(n, T);

    if(rod != -1)
    {
        //ako je zrtva prvo djete, onda samo postavimo adresu brata na kursor c
        //inace treba naci starijeg brata i dati mu adresu brata brisanog elementa
        if(FirstChildT(rod, T) == n) T.el[rod].c = NextSiblingT(n, T);
        else
        {
            int t = FirstChildT(rod, T);
            while(NextSiblingT(t, T) != n) t = NextSiblingT(t, T);
            T.el[t].b = NextSiblingT(n, T);
        }  //if(FirstChildT(rod, T) == n) : else
    }  //if(rod != -1)

    if(FirstChildT(n, T) != -1) DeletePomT(FirstChildT(n, T), T);
    T.el[n].vrij = '\0';
    T.el[n].c = -1;
    T.el[n].b = -1;
}  //void DeleteT(int n, tr &T)

void InitT(int x, tr &T)
{
    if(T.o) DeleteT(T.R, T);  //brisati stablo samo ako stablo nije prije deklarirano
    T.R = x;
    T.o = true;
}  //void InitT(int x, tr &T)