// polje.h
 
typedef int cijeli;
typedef int funkcija;
struct pom {
	cijeli element;
	cijeli iskoristen;
}; 
 
struct stablo_polje {
	pom elementi[10000];
};
 
typedef stablo_polje bs;
typedef int cvor;
 
funkcija ParentB(cvor n,bs *stablo)
{
	if (n==1)
	{
		return -1;
	}
	else if ((n%2)==0)
	{
		return n/2;
	}
	else
	{
		return (n-1)/2;
	}
}
 
funkcija LeftChildB(cvor n,bs *stablo)
{
	n=2*n;
	if (stablo->elementi[n].iskoristen==0)
	{
		return -1;
	}
	else 
		return  n;
}
 
funkcija RightChildB(cvor n,bs *stablo)
{
	n=2*n+1;
	if (stablo->elementi[n].iskoristen==0)
	{
		return -1;
	}
	else 
		return  n;
}
 
cijeli LabelB(cvor n,bs *stablo)
{
	return stablo->elementi[n].element;
}
 
void ChangeLabelB(cijeli x,cvor n,bs *stablo)
{
	stablo->elementi[n].element=x;
}
 
funkcija RootB(bs stablo)
{
	return 1;
}
 
void CreateLeftB(cijeli x,cvor n,bs *stablo)
{
	n=n*2;
	if (stablo->elementi[n].iskoristen)
	{
		cout<<"postoji ljevo dijete!!!!";
	}
	else 
	{
		stablo->elementi[n].element=x;
		stablo->elementi[n].iskoristen=1;
	}
}
 
 
void CreateRightB(cijeli x,cvor n,bs *stablo)
{
	n=n*2+1;
	if (stablo->elementi[n].iskoristen)
	{
		cout<<"postoji desno dijete!!!!";
	}
	else 
	{
		stablo->elementi[n].element=x;
		stablo->elementi[n].iskoristen=1;
	}
}
 
void DeleteB(cvor n,bs *stablo)
{
	cijeli i=n*2,j=n*2+1;
	if (stablo->elementi[i].iskoristen)
		DeleteB (i,stablo);
	if (stablo->elementi[j].iskoristen)
		DeleteB (j,stablo);
	stablo->elementi[n].iskoristen=0;
}
 
void InitB(cijeli x,bs *stablo)
{
	for (cijeli i=0;i<9999;i++)
		stablo->elementi[i].iskoristen=0;
	stablo->elementi[1].iskoristen=1;
	stablo->elementi[1].element=x;
}
 
 
//main polje
 
#include <iostream>
using namespace std;
#include "polja.h"
 
 
int main()
{
	cijeli x,j;
	bs stablo;
 
	InitB(2,&stablo);
 
	//dodavanje startnog lijevog djeteta
	cout << "Kreiram lijevo pocetno stablo sa vrijednoscu 22" <<endl;
	CreateLeftB(22,1,&stablo);
	cout << "Brisem korijen na lokaciji 1" <<endl;
	DeleteB(1,&stablo );
	//generiranje ostatka stabla brojeva, koristenje ostalih imoplementiranih funkcija
	for (int i=1;i<10;i++)
	{
		x=rand()%100;
		j=1;
		do 
		{
			if (LabelB(j,&stablo)>=x)
			{
				if (LeftChildB(j,&stablo)==-1)
				{
					CreateLeftB(x,j,&stablo);
					cout<<"ljevo "<<x;
					break;
				}
				else
				{
					j=j*2;
					cout<<"ljevo ";
				}
			}
			else if(LabelB(j,&stablo)<x)
			{
				if (RightChildB(j,&stablo)==-1)
				{
					CreateRightB(x,j,&stablo);
					cout<<"desno "<<x;
					break;
				}
				else
				{
					j=j*2+1;
					cout<<"desno ";
				}
			}	
		}while(1);	
	}
   int a;
   cin >> a;
 
   return 0;
}
 
 
// pokazivaci.h
 
 
typedef int cijeli;
struct stablo_pok {
	cijeli element;
	struct stablo_pok *ljevo,*desno;
}; 
typedef stablo_pok *funkcija;
typedef stablo_pok *cvor;
typedef stablo_pok bs;
 
funkcija ParentB(cvor n,bs *stablo)
{
	static bs *trazeni=n;
	bs *i;
	if (stablo->ljevo!=NULL)
	{
		if (stablo->ljevo==n)
			return stablo;
		else 
			i=ParentB(trazeni,stablo->ljevo);
	}
	else
	{
		if (stablo->desno!=NULL)
		{
			if (stablo->desno==n)
				return stablo;
			else
				i=ParentB(trazeni,stablo->desno);
		}
	}
	return i;
}
 
funkcija LeftChildB(bs *stablo)
{
	return stablo->ljevo;
}
 
funkcija RightChildB(bs *stablo)
{
	return stablo->desno;
}
 
cijeli LabelB(bs *stablo)
{
	return stablo->element;
}
 
void ChangeLabelB(cijeli x,bs *stablo)
{
	stablo->element=x;
}
 
funkcija RootB(bs *stablo)
{
	return stablo;
}
 
void CreateLeftB(cijeli x,bs *stablo)
{
	if (stablo->ljevo!=NULL)
		cout<<"postoji ljevo djete!!";
	else
	{
		bs *novi=new bs;
		novi->element=x;
		stablo->ljevo=novi;
		novi->desno=NULL;
		novi->ljevo=NULL;
	}
}
 
 
void CreateRightB(cijeli x,bs *stablo)
{
	if (stablo->desno!=NULL)
		cout<<"postoji desno djete!!";
	else
	{
		bs *novi=new bs;
		novi->element=x;
		stablo->desno=novi;
		novi->desno=NULL;
		novi->ljevo=NULL;
	}
}
 
void DeleteB(bs *stablo)
{
	if (stablo->ljevo!=NULL)
		DeleteB(stablo->ljevo); 
	if (stablo->desno!=NULL)
		DeleteB(stablo->desno);
	delete stablo;
}
 
void InitB(cijeli x,bs *stablo)
{
 
	stablo->element=x;
	stablo->ljevo=NULL;
	stablo->desno=NULL;
}
 
 
// pokazivaci main
 
#include <iostream>
using namespace std;
#include "pokazivaci.h"
 
int main()
{
 
	bs stablo;
	cout << "Inicijaliziram korijen" <<endl;
	InitB(2,&stablo);
 
	CreateLeftB(22,&stablo);
	CreateRightB(23,&stablo);
	cout << "Lijevi korijen: " << LeftChildB(&stablo)->element <<endl;
    cout << "Desni korijen: " << RightChildB(&stablo)->element <<endl;
    cout << "Labela korijena: " << LabelB(&stablo) <<endl;   
    cout << "Brisem korijen" <<endl;
	DeleteB(&stablo );
	int a;
	cin>>a;
	return 0;
}