By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
426,165 Members | 1,916 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 426,165 IT Pros & Developers. It's quick & easy.

Operation with a binary search tree

P: n/a
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

Nov 22 '06 #1
Share this Question
Share on Google+
1 Reply


P: n/a

the problem is i do not exactly know for what do i need the removed
parameter, because i only delete the node with the highest number...??

Nov 22 '06 #2

This discussion thread is closed

Replies have been disabled for this discussion.