Thread: Binary Search Tree - one last question

  1. #1
    Registered User
    Join Date
    Nov 2006
    Posts
    34

    Cool Binary Search Tree - one last question

    The final function (method) needed to make my Address Book complete is a modify function. One that modifies the data in the address book. Right now I've done a rather 'sloppy' version, by deleting the found entry, and adding a new one. That works fine if every time the user wants to change the data they want to change all of it. It won't work in this case:
    The user wants to change the address and not the phone number,
    or
    The user wants to change the phone number and not the address.

    Here is the call from my test:

    Code:
    case 6: cout << "Enter the name of the entry you wish to modify: " << endl;
    				getline(cin, someName);
    				getline(cin, someAddress);
    				getline(cin, somePhone);
    				entry.modifyPerson(someName, someAddress, somePhone);
    				break;
    Here is the function it calls:

    Code:
    void AddressBook::modifyPerson(string name, string address, string phoneNum)
    {
    	
    	if(addressTree->personSearch(name))
    	{
    		addressTree->deleteNode(name);
    
    		const Person *newPerson = new Person(name, address, phoneNum);
    
    		addressTree->insertNode(*newPerson);
    	}
    	else
    	{
    		cout << name <<" was not found in the address book." << endl;
    	}
    
    }//end modify person
    The functions (methods) personSearch(name), the deleteNode(name) and the insertNode(*newPerson), work fine and are here:

    Code:
    //function to perform a search
    template< typename NODETYPE >
    bool Tree< NODETYPE >::personSearch( string name)
    {
    	bool found = false;
    	TreeNode <NODETYPE> *location;
    
    	searchPersonList(name, found, location);
    
    	return found;
    }//end personSearch
    template< typename NODETYPE >
    void Tree< NODETYPE >::searchPersonList(string name, bool& found, TreeNode< NODETYPE >* &ptr)
    {
    	found = false;
    
    	if (rootPtr == NULL) //the tree is empty
    		cout << "Can't search an empty list. " << endl;
    	else
    	{
    		ptr = rootPtr;   //set p pointer to point to the root node of btree
    		found = false;  //set found to false
    
    		while(ptr != NULL && !found)  //search the tree
    		{
    			if(ptr->data == name)
    				found = true;
    			else
    				if(ptr->data > name)
    					ptr = ptr->leftPtr;
    				else
    					ptr = ptr->rightPtr;
    		}
    	}// end else
    }//end searchPersonList
    
    //  function to perform deleteFromTree
    template< typename NODETYPE >
    void Tree< NODETYPE >::deleteFromTree(TreeNode<NODETYPE>* &ptr)
    {
    	TreeNode <NODETYPE> *current;  //pointer to traverse the tree
    	TreeNode <NODETYPE> *trailCurrent;  //pointer behind current
    	TreeNode <NODETYPE> *temp;
    
    	if(ptr == NULL)
    	{
    		cerr<<"Error:  The node to be deleted is NULL.";
    		cout << endl;
    	}
    	else if(ptr->leftPtr == NULL && ptr->rightPtr == NULL)
    	{
    		temp = ptr;
    		ptr = NULL;
    		delete temp;
    	}
    	else if(ptr->leftPtr == NULL)
    	{
    		temp = ptr;
    		ptr = temp->rightPtr;
    		delete temp;
    	}
    	else if(ptr->rightPtr == NULL)
    	{
    		temp = ptr;
    		ptr = temp->leftPtr;
    		delete temp;
    	}
    	else
    	{
    		current = ptr->leftPtr;
    		trailCurrent = NULL;
    		while(current->rightPtr != NULL)
    		{
    			trailCurrent = current;
    			current = current->rightPtr;
    		}//end while
    
    		ptr->data = current->data;
    		if(trailCurrent == NULL)  //current did not move;
    		{
    			ptr->leftPtr = current->leftPtr;
    		}
    		else 
    		{
    			trailCurrent->rightPtr = current->leftPtr;
    		}
    		cout << "success" << endl;
    		delete current;
    	}//end else
    	
    } // end function deleteFromTree
    
    //  function to perform delete node
    template< typename NODETYPE >
    void Tree< NODETYPE >::deleteNode(const NODETYPE &deleteValue)
    {
    	TreeNode <NODETYPE> *current;  //pointer to traverse the tree
    	TreeNode <NODETYPE> *trailCurrent;  //pointer behind current
    	bool found = false;
    
    	if(rootPtr == NULL)
    		cerr<<"Error:  The node to be deleted is NULL.";
    	else 
    	{
    		current = rootPtr;
    		trailCurrent = rootPtr;
    
    		while(current != NULL && !found)
    		{
    			if(current->data == deleteValue)
    				found = true;
    			else
    			{
    				trailCurrent = current;
    				if(current->data > deleteValue)
    					current =  current->leftPtr;
    				else
    					current = current->rightPtr;
    			}//end else
    		}//end while
    
    		if(current == NULL)
    			cout << "The delete item is not in the list." <<endl;
    		else
    			if(found)
    			{
    				if(current == rootPtr)
    					deleteFromTree(rootPtr);
    				else
    					if(trailCurrent->data > deleteValue)
    						deleteFromTree(trailCurrent->leftPtr);
    					else
    						deleteFromTree(trailCurrent->rightPtr);
    			}//end if
    	}
    }//end deleteNode
    // insert node in Tree
    template< typename NODETYPE >
    void Tree< NODETYPE >::insertNode(const NODETYPE &value )
    { 
       insertNodeHelper( &rootPtr, value ); 
    } // end function insertNode
    
    // utility function called by insertNode; receives a pointer
    // to a pointer so that the function can modify pointer's value
    template< typename NODETYPE >
    void Tree< NODETYPE >::insertNodeHelper( 
       TreeNode< NODETYPE > **ptr, const NODETYPE &value )
    {
       // subtree is empty; create new TreeNode containing value
       if ( *ptr == 0 )  
          *ptr = new TreeNode< NODETYPE >( value );
       else // subtree is not empty
       {
          // data to insert is less than data in current node
          if ( value < ( *ptr )->data )
             insertNodeHelper( &( ( *ptr )->leftPtr ), value );
          else
          {
             // data to insert is greater than data in current node
             if ( value > ( *ptr )->data )
                insertNodeHelper( &( ( *ptr )->rightPtr ), value );
             else // duplicate data value ignored
                cout << value << " dup" << endl;
          } // end else
       } // end else
    } // end function insertNodeHelper
    The one thing wrong with the personSearch() and searchPersonList() is that the searchPersonList() has a *location, but the personSearch() returns a bool instead of the pointer to the location. I have tried all afternoon to write a function that returns the location so that I can simply change the address or the phone number but I can't get it to work.

    I'm hoping someone could help me go in the right direction.
    1st. What return type would the location be? When I make it a NODETYPE I get errors when passing a PERSON pointer to it from the modify function.
    2nd. How do I use the pointer? location->setPersonalInfo(name, address, phone)? I have a function that does that for insert(), but so far I can't get it to work in this case because I don't understand the previous question.

    Thanks for your insight. I'm almost done with this assignment, and I've learned a lot thanks to those helping on this web site.

    TMS

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318

    Lightbulb

    Something's not right here.
    You have presented fairly well written code that has some const-correctness, uses templates, and is doing other things that are beyond most beginners.
    Yet you are stumbling on what return type something should be, when it looks fairly obvious.

    You sure you wrote all that?
    Shouldn't you be passing your std::strings by const reference?

  3. #3
    Registered User
    Join Date
    Nov 2006
    Posts
    34
    yeah, its the pointer thing that confuses me as well as the interaction with the binary tree. I'm sure it seems obvious, but everything I've done (by instinct) has been wrong. I am simply stuck. Believe me, its taken me 2 weeks to get this far, with lots of mistakes (aka, lots of learning). I get that I need to search the tree, find the node where the person and information is, then change it. But, in order to do that, I have to return the location (pointer) and thats something I can't seem to do. I'm probably making it harder than it is.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. arrays vs lists? And containers in general!
    By clegs in forum C++ Programming
    Replies: 22
    Last Post: 12-03-2007, 02:02 PM
  2. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  3. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 09:11 AM
  4. problem in storing data in a binary search tree
    By alavardi in forum C Programming
    Replies: 5
    Last Post: 02-13-2005, 03:20 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM