ive implemented a couple of functions for an assignment for class. i have an add function which adds students, id's, and universitys and have "tried" to add a get id function which should search the list, find a specified id, then return it. unfortunately, when i try to run this program, it crashes. does anyone have any idea as to why? is my getid function wrong?
thanks.

////////////////
// A Binary Search Tree Data type
////////////////



#include <iostream>
#include <string>
using namespace std;

class treenode
{
      public:
             string data;
             treenode * left;
             treenode * right;
             int id;
             string university;
             
             treenode(string s, string univname, int stuid)
             { 
             data =s;
             left=NULL;
             right=NULL;
             university=univname;
             id=stuid;
                  }
};

class MyBST
{
private:      
     treenode * root;
     
	 //Insert item s into a tree rooted at r
     void recInsert(treenode * & r, string stu, string university, int id);


	 //Display all items in the tree in order (in-order traversal)
     void getid(treenode* r, int &stid);    
     
public: 
     MyBST();
     
	 //A wrapper for the recursiver insert routine
     void add(string s, string univname, int id);

	 //A wrapper for the recursive display routine
     void display( int stuid);    
};   

////private methods////
void MyBST::recInsert(treenode * & r, string stu, string university, int id)
{
    if( r == NULL ) //empty tree, easy case!!!!!!
    {
        //create a new node, point r at it
        r = new treenode(stu, university, id);    
    }
    else if( stu > r->data ) //go right!
    {
        recInsert( r->right, stu , university, id );     
    }
    else  // go left
    {
        recInsert( r->left, stu , university, id);      
    }
}




void MyBST::getid(treenode* r, int &stuid) 
{      
  
    if(stuid == r->id)	
       {	
          cout<<r->id <<endl;
    // return true if found	
       }
    // smaller than current - continue searching left node
       else if (stuid < r->id)   
         {	
            getid(r->left, stuid);
         }
    // not smaller, must be larger - continue searching right node
       else
         {	
             getid(r->right, stuid);
         }
 }


//public methods///
MyBST::MyBST()
{
    root = NULL;          
}

//wrapper for the recursive getid
void MyBST::display(int stuid)
{
     getid(root, stuid);
}

//wrapper for the recursive add
void MyBST::add(string stu, string university, int id)
{
     recInsert(root, stu, university, id);
}




int main()
{
    
    MyBST studentinfo;
    studentinfo.add("G", "UNIV", 123456);
    studentinfo.add("Ch","COLLEGE", 123547);   
    studentinfo.add("T","COLLEGE", 145236);
    studentinfo.add("W","U", 985621); 
    studentinfo.add("F","U", 547821);       
    studentinfo.add("M","UNIV", 456321); 
    studentinfo.add("W", "COLLEGE", 123569);
        
    studentinfo.display(456321);    
        
    while(true){}
    return 0;   
}

Recommended Answers

All 4 Replies

In getid, what happens when r is NULL?

well if r is NULL, then that means the tree should be empty and we are therefore unable to find the item on the list. i added:

void MyBST::getid(treenode* r, int &stuid) 
// added this part to the function. when i run it, i just get the message everytime.
{      
   if ( r == NULL)
   {
        cout<< "Specified ID could not be found" << endl;
        }
        
    else if(stuid == r->id)	
       {	
          cout<< stuid <<endl;
          cout << r->university<< endl;
          cout << r->data << endl;
    // return true if found	
       }
    // smaller than current - continue searching left node
       else if (stuid < r->id)   
         {	
            getid(r->left, stuid);
         }
    // not smaller, must be larger - continue searching right node
       else
         {	
             getid(r->right, stuid);
         }
 }

i got it to work! i added a case for when r=NULL as well as when stuid= to the information at the node pointed at. it works great now! thanks!

That would be correct if id were your key, but data is your key. getid will need to do a full traversal rather than a simple search, in which case r might be NULL several times before the correct node is found:

void MyBST::getid(treenode* r, int &stuid)
{
    if (r != NULL) {
        getid(r->left, stuid);

        if (r->id == stuid)
            cout<<"Found "<< r->id <<'\n';

        getid(r->right, stuid);
    }
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.