hi,
now i facing a problem which i do not know how to solve it...:(
My binary search tree structures stores a double number in every node,
whereby a higher number is appended as right child and a less or equal
number is appended as a left child. Now i want to write a function
which deletes the node with the highest number in the tree. I started
the function as follows:
[code]
template <class Item>
void bst_remove_max(binary_tree_node<Item>*& root_ptr, Item&
removed)
// Precondition: root_ptr is a root pointer of a non-empty binary
// search tree.
// Postcondition: The largest item in the binary search tree has
been
// removed, and root_ptr now points to the root of the new
(smaller)
// binary search tree. The reference parameter, removed, has been
set
// to a copy of the removed item.
{
binary_tree_node<Item*cursor;
cursor = root_ptr;
if(root_ptr != NULL)
{
if(cursor->right() == NULL)
{
root_ptr = root_ptr->left();
delete cursor;
}
else
{
bst_remove_max(cursor->right(), removed);
}
}
/** The base case occurs when there is no right child of the
** root_ptr node. In this case, the root_ptr should be moved
down
** to its left child and then the original root node must be
** deleted. There is also a recursive case, when the root does
** have a right child. In this case, a recursive call can be
made
** using root_ptr->right( ) as the first parameter. */
}
Unfortunately i do simply not know how i should complete this function
in oder that it would work correctly. Has probably anybody here some
hints for me..? :-/
matti |