struct element
{
	labeltype label;
    int left, right, available;
};
 
typedef struct bt
{
    element data [10000];
    int current;
} *bTree;
 
typedef int node;
 
int ExistsLeftChild(node n, bTree tTree)
{
    if (tTree->data[n].left == -1)
        return 0;
    else
        return 1;
}
 
int ExistsRightChild(node n, bTree tTree)
{
    if (tTree->data[n].right == -1)
        return 0;
    else
        return 1;
}
 
void InitB(labeltype tElem, bTree tTree)
{
    tTree->data[0].label = tElem;
    tTree->data[0].available = 0;
    tTree->data[0].left = -1;
    tTree->data[0].right = -1;
    for (int i = 1; i<10000; i++)
    {
        tTree->data[i].available = 1;
        tTree->data[i].left = -1;
        tTree->data[i].right = -1;
    }
    tTree->current = 1;
}
 
labeltype LabelB(node n, bTree tTree)
{
    return tTree->data[n].label;
}
 
node RootB(bTree tTree)
{
    if (tTree->data[0].available == 1)
        return -1;
    else
        return 0;
}
 
node LeftChildB(node n, bTree tTree)
{
	return tTree->data[n].left;
}
 
node RightChildB(node n, bTree tTree)
{
    return tTree->data[n].right;
}
 
void ChangeLabelB(labeltype x, node n, bTree tTree)
{
    tTree->data[n].label = x;
}
 
node ParentB(node n, bTree tTree)
{
    int pronadjen = 0, i = 0;
    if (n == RootB(tTree))
        return -1;
    else
    {
        while (pronadjen == 0)
        {
			if (tTree->data[i].left == n)
            {
                return i;
                pronadjen = 1;
            }
            else if (tTree->data[i].right == n)
            {
                return i;
                pronadjen = 1;
            }
            i++;
        }
    }
}
 
void CreateLeftB(labeltype x, node n, bTree tTree)
{
    tTree->current = 1;
    while (tTree->data[tTree->current].available == 0)
    {
        tTree->current++;
    }
    if (tTree->data[n].available == 1)
    {
        cout << "Cvor ne postoji te mu ne mozemo dodati djecu.\n" << endl;
    }
    else
    {
        tTree->data[n].left = tTree->current;
        tTree->data[tTree->current].label = x;
        tTree->data[tTree->current].available = 0;
    }
}
 
void CreateRightB(labeltype x, node n, bTree tTree)
{
    tTree->current = 1;
    while (tTree->data[tTree->current].available == 0)
    {
        tTree->current++;
    }
    if (tTree->data[n].available == 1)
    {
        cout << "Cvor ne postoji te mu ne mozemo dodati djecu.\n" << endl;
    }
    else
    {
        tTree->data[n].right = tTree->current;
        tTree->data[tTree->current].label = x;
        tTree->data[tTree->current].available = 0;
    }
}
 
void DeleteB(node n, bTree tTree)
{
    node pNode;
 
    if (ExistsLeftChild(n, tTree) == 1)
        DeleteB(LeftChildB(n, tTree), tTree);
    if (ExistsRightChild(n, tTree) == 1)
        DeleteB(RightChildB(n, tTree), tTree);
    pNode = ParentB(n, tTree);
 
    if (tTree->data[pNode].left == n)
        tTree->data[pNode].left = -1;
    else
        tTree->data[pNode].right = -1;
 
    if ((tTree->data[n].left == -1) && (tTree->data[n].right == -1))
        tTree->data[n].available = 1;
}