If I want to make a binary tree from an array in the following order:
Example: for the following array: { -1, 17, -1, 3, -1, -1, -1, 55, -1, 4, -1, 15, 11, 2, 3 } the following tree is created:
55
15 3
2 4 * 17
3 11 * * * *
The function is recursive and returns a Tree input: the array and it's size. The tree nodes can only receive positive values from the array so -1 wont be considered. * means NULL prototype: Tree BuildTreeFromArray(int *arr, int size).
Would very much appreciate the help.
This is what I had so far and it's working but I don't really like it.
Tree BuildTreeFromArray(int *arr, int size)
{
Tree resTree;
Tree right;
Tree left;
resTree.root = (TreeNode*)malloc(sizeof(TreeNode));
checkMemoryAllocation(resTree.root);
int halfSize;
if (size == 1)
{
resTree.root->data = arr[0];
resTree.root->left = NULL;
resTree.root->right = NULL;
}
else
{
halfSize = size / 2;
resTree.root->data = arr[halfSize];
if (arr[halfSize/2] != -1)
{//we check if there's a valid array data we can input to the tree
left = BuildTreeFromArray(arr, halfSize);
resTree.root->left = left.root;
}
else
resTree.root->left = NULL;
if (arr[halfSize + (halfSize / 2) + 1] != -1)
{
right = BuildTreeFromArray(arr + halfSize + 1, halfSize);
resTree.root->right = right.root;
}
else
resTree.root->right = NULL;
}
return resTree;
}
Could this be written in a different version?