Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Operation with a binary search tree

Reply
Thread Tools

Operation with a binary search tree

 
 
mathon@gmx.at
Guest
Posts: n/a
 
      11-22-2006
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

 
Reply With Quote
 
 
 
 
mathon@gmx.at
Guest
Posts: n/a
 
      11-23-2006

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...??

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Binary tree search vs Binary search Bogdan C Programming 22 10-21-2010 09:46 PM
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 2 10-31-2007 02:58 AM
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 1 10-30-2007 11:01 PM
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 4 10-30-2007 08:21 PM
B tree, B+ tree and B* tree Stub C Programming 3 11-12-2003 01:51 PM



Advertisments