0

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;   
}
2
Contributors
4
Replies
5
Views
6 Years
Discussion Span
Last Post by Narue
0

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);
         }
 }
0

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!

0

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);
    }
}
This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.