#include <iostream>
using namespace std;
 
struct elem {
	char oznaka;
	int dijete,brat;
};
struct tr {
	elem polje[1000];
	int korijen;
};
 
typedef struct tr tree;
char pomoz='A';
 
tree *InitT(int x,tree *T){
 
	for(int i=0;i<1000;i++){
		T->polje[i].oznaka= '0';
		T->polje[i].dijete= -1;
		T->polje[i].brat= -1;
	}
	T->polje[x].oznaka=pomoz++;
	T->korijen=x;        	
	return T;
}
 
int ParentT(int n, tree *T){
	if (n==T->korijen){
		cout<<"Korijen nema roditelja!";
		return -1;
	}
	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);
	}
}
 
int FirstChildT(int n, tree *T){
	return T->polje[n].dijete;	
}
 
int NextSiblingT(int n, tree *T){
	return T->polje[n].brat;	
}
 
char LabelT(int n,tree *T){
	return T->polje[n].oznaka;	
}
 
int RootT(tree *T){
	return T->korijen;	
}
 
void CreateT(char x, int n,tree *T){
	if (T->polje[n].oznaka=='0') cout<<"Cvor ne postoji!"<<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].dijete=-1;
		T->polje[x].brat=-1;
		T->polje[x].oznaka=pomoz++;	
	}
}
 
void ChangeLabelT(char x,int n, tree *T){
	if (T->polje[n].oznaka=='0') cout<<"Cvor ne postoji!"<<endl; 
	else 
		T->polje[n].oznaka=x;
}
 
void DeleteT(int n, tree *T){
	if(FirstChildT(n,T)!=-1) DeleteT(T->polje[n].dijete,T);	
	if(NextSiblingT(n,T)!=-1) DeleteT(T->polje[n].brat,T);
	T->polje[n].dijete=-1;
	T->polje[n].brat=-1;
	T->polje[n].oznaka = '0';
}