I'm trying to write a program that builds a full binary tree from an array containing an even number of sequential numbers. I know the memory allocation part, I'm just having trouble with how to pass the integers to act as array positions. This is what I've come up with so far:
tree root = maketree(a, 0, i) // a is an array of i elements, containing the
// numbers 1 to some multiple of 1000
...
tree maketree(int a[], int st, int max)
{
tree root = makenode(a, max/2 + (some number));
root->leftchild = maketree(a, 0, max/2 + (some number));
root->rightchild = maketree(a, max/2 + (some number), max);
}
tree makenode(int a[], int i)
{
tree t = newnode();
t->element = a[i];
t->leftchild = NULL;
t->rightchild = NULL;
}
tree newnode()
{
return malloc(sizeof(node));
}The three places I'm unsure about are the places I've written (some number). Obviously I know they might not need a number added at all, or maybe some need a number subtracted. But at this point, I've tried every combination I could think of and nothing is coming out as a full binary tree. I think the definition I've been given is universal, but just in case, what I mean by full binary tree is a binary tree where all elements to the left of a node have elements that are less than the current node's element, and every node has two children, except for leaves of the "lowest" depth of the tree.
If anyone has a tip for what I can fill in, or a preexisting example, it would be greatly appreciated.