Operation with a binary search tree

Discussion in 'C++' started by mathon@gmx.at, Nov 22, 2006.

  1. Guest

    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, 2006
    #1
    1. Advertising

  2. Guest

    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 23, 2006
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,136
  2. sharan
    Replies:
    4
    Views:
    693
    CBFalconer
    Oct 30, 2007
  3. sharan
    Replies:
    2
    Views:
    835
    SM Ryan
    Oct 31, 2007
  4. sharan
    Replies:
    1
    Views:
    693
    CBFalconer
    Oct 30, 2007
  5. Bogdan

    Binary tree search vs Binary search

    Bogdan, Oct 18, 2010, in forum: C Programming
    Replies:
    22
    Views:
    3,089
    Michael Angelo Ravera
    Oct 21, 2010
Loading...

Share This Page