#include<iostream>
using namespace std;
 
struct element{
    char label;
    int dijete,brat;
};
 
struct tree{
    element polje[1000];
    int korijen;
};
 
tree *InitT(int k,tree *T){
    T = new tree;
    for(int i=0;i<1000;i++){
        T->polje[i].label = '0';
        T->polje[i].dijete = T->polje[i].brat = -1;
        }
    T->polje[k].label = 'A';
    T->korijen = k;
    return T;
    }
 
void ChangeLabelT(char x,int n,tree *T){
    T->polje[n].label = x;
    }
 
int RootT(tree *T){
    return T->korijen;
    }
 
char LabelT(int n,tree *T){
    return T->polje[n].label;
    }
 
void CreateT(int x,int n,tree *T){
    if(T->polje[n].label=='0') cout << "Ne postoji cvor " << n << " !" << endl;
    else{
        if(T->polje[n].dijete==-1) T->polje[n].dijete = x;
        else if(T->polje[T->polje[n].dijete].brat==-1) T->polje[T->polje[n].dijete].brat = x;
        else{
            n = T->polje[n].dijete;
            while(T->polje[n].brat!=-1) n = T->polje[n].brat;
            T->polje[n].brat = x;
            }
        T->polje[x].label = T->polje[n].label+1;
        T->polje[x].dijete = T->polje[x].brat = -1;
        }
    }
 
int FirstChildT(int n,tree *T){
    return T->polje[n].dijete;
    }
 
int NextSiblingT(int n,tree *T){
    return T->polje[n].brat;
    }
 
int ParentT(int n,tree *T){
    for(int i=0;i<1000;i++){
        if(T->polje[i].dijete==n) return i;
        if(T->polje[i].brat==n) return ParentT(i,T);
        }
    }
 
void DeleteT(int n,tree *T){
    if(T->polje[n].dijete!=-1) DeleteT(T->polje[n].dijete,T);
    if(T->polje[n].brat!=-1) DeleteT(T->polje[n].brat,T);
    T->polje[n].dijete = T->polje[n].brat = -1;
    T->polje[n].label = '0';
    if(T->polje[ParentT(n,T)].brat!=-1) T->polje[ParentT(n,T)].dijete = T->polje[ParentT(n,T)].brat;
    else T->polje[ParentT(n,T)].dijete = -1;
    }