Why does
(start+last)/2
work to calculate the midpoint while
start+(last-start)/2
does?
To be more specific, I put the contents of a binary tree into an array, sorted it, destroyed the old tree, and plan to rebuild the new one. I know that start+(last-start)/2 as a midpoint calculation works correctly. My problem is that I don't actually know WHY it works. I need to know for a test I have tomorrow. Here's the code for the rebuildTree function.
binaryTreeNodePtrType BinaryTree::rebuildTree(int* &a, int start, int last)
{
binaryTreeNodePtrType ptr = new binaryTreeNodeType; //create new node
if (start <= last) {
/* Had to find out a new way to calculate midpoint.
The "average" way [(start+last)/2] did not work
correctly. This new way of calculating a midpoint
works. It's hard to explain, but drawing out the
process helps to understand it.
*/
int mid = start+(last-start)/2; //calculate midpoint
ptr->key = a[mid]; //set pointer's key value to the midpoint value
ptr->leftchild = rebuildTree(a, start, mid-1); //continue to the left
ptr->rightchild = rebuildTree(a, mid+1, last); //cotinue to the right
}
else {
return NULL;
}
return ptr;
}
