CS 153 Data Structures I
Program #11
Binary Search Tree - part 2

Due Date: November 9, 2000, during your teams scheduled time.  If you would Like to demo your program before Thursday, you can do so by scheduling an appointment with a TA.

Emphasis:

Discussion:  The BST for this assignment is a further enhancement of Program 10.  The only important new function will be Remove.  There is however an important difference in how the 'type of data' is specified for the BST.  In Program 10 you hard coded the Bnodes to contain an int.  For Program #11 this int m_data MUST be removed from the Bnode specification.  Your Bnode will look something like the following:

class Bnode
{
public:
    Bnode();
    virtual bool operator<( Bnode & rhs ) = 0;
    virtual bool operator==( Bnode & rhs ) = 0;
    virtual void Show(CListBox &) = 0;
    virtual ~Bnode() {};
    Bnode * LC;
    Bnode * RC;
};

Program Requirements:

  • Place buttons on your GUI to test Remove.
  • The data to be inserted into the BST must take the form of a class object derived from Bnode (perhaps called myData).  Your OnButtonInsert() needs to dynamically allocate a new myData object and pass the address of the new object to BST::Insert(Bnode * & a_node).  See below an example of what BST::Insert might look like.
  • The following are the required public functions:
  • void Insert(Bnode *);              //pass Insert a pointer to your new myData!!!
  • bool Find( Bnode *)const;      //pass Insert a pointer to a myData that matches what you are looking for
  • void Display(CListBox &);                       // NOTE: NO argument.
  • void HelpDisplay(CListBox & box, Bnode * cur)  //Recurs thru the tree INORDER calling Show(box)
    • A sample Insert function showing how to use a virtual function (in this case operator<).
    void CBst::Insert( Bnode *pNode )
    {
        Bnode *pTempNode = m_pRoot;
        if( m_pRoot == NULL )  // No Nodes
            m_pRoot = pNode;
        else      // More than one node find location
        {
            while( 1 )
            {
                if( *pTempNode < *pNode )  // Follow Right
                {
                    if( pTempNode->pRight == NULL )
                   {
                       pTempNode->pRight = pNode;
                       break;
                   }
                   pTempNode = pTempNode->pRight;
                }
                else       // Follow Left
                {
                    if( pTempNode->pLeft == NULL )
                    {
                        pTempNode->pLeft = pNode;
                        break;
                    }
                    pTempNode = pTempNode->pLeft;
                }
            }
        }
    }
    Make sure you have preconditions, post conditions and a one-line description of your program with every function prototype. (in the header file!)
    Make sure you comment variables which are not self explanatory.
    Make sure you comment logical blocks of code.
    Don't comment every line of your code.