Thread: binarySearchTree delete function problem

When I try to use the deletePerson() function, it deletes the same node every time (I actually think its the root node). I'm thinking that the string I'm trying to delete isn't getting passed through to my interface file, because the function (in binarySearchTree class) itself works fine when called directly. Here is my code:

Code:

#ifndef person_h
#define person_h
#include <iostream>
#include <string>
#include "binarySearchTree.h"

using namespace std;

class person: public binarySearchTree
{
	friend ostream& operator<<(ostream&, const person&);
	 
public:
    void setPersonalInfo(treeNode *&root, string name, string address, 
					  string phoneNum);
	//Function to set the details of a video. 
    //The private data members are set according to the 
    //parameters.
	//Postcondition:  personName = name;
	//		personAddress = address;
	//		personPhoneNum = phoneNum;
	//		numInBook = setNumInBook;
					
   	void printName(treeNode *&root) const;
	//Function to print the names located in the address book; 

    void printInfo() const;
	//Function to print the name and addresses in the address book;

    bool checkName(string name);
	//Function to check if the name is already in the address book;

	string getName();
	//Function to return a name from the address book;
	
    person(string name = "" , string address = "", 
			  string phoneNum = "");
	//constructor
	//The private data members are set according to the incoming parameters;
	//If no values are specified the default values are assigned.
	//Postcondition: personName = name;
	//		personAddress = address;
	//		personPhoneNum = phoneNum;
	
	void addPerson(treeNode *&root, string name); //, string address, string phoneNum);
	//Function to add a name and info to the address book;

	void deletePerson(treeNode *&root, string name);
	//Function to delete a name from the address book;

	void findPerson(treeNode *&root, string name);
	//Function to find a name located in the address book;

	void modifyPerson(string name, string address, string phoneNum);
	//Function to modify an entry in the address book;

	//overload relational operators:
    bool operator==(const person&) const;
    bool operator!=(const person&) const;
	bool operator<(const person&) const;
	bool operator<=(const person&) const;
	bool operator>(const person&) const;
	bool operator>=(const person&) const;

private:
    string personName;			//variable to store the name;
    string personAddress;		//variable to store the address;	
    string personPhoneNum;		//variable to store the phone number;	
    				
};

#endif
#include <iostream>
#include <string>
#include "person.h"

using namespace std;

/**Function to set the details of an entry.  Private members are 
   set according to the parameters.
   Postcondition: personName = name;
		personAddress = address;
		personPhoneNum = phoneNum;
		numInBook = setNumInBook;
  */
void person::setPersonalInfo(treeNode *&root, string name, string address, 
							 string phoneNum)
{
	
	personName = name;
	personAddress = address;
	personPhoneNum = phoneNum;
}


/**Function to print the names located in the address book; */
void person::printName(treeNode *&root) const
{
	
	binarySearchTree tmp;

	tmp.inOrderPrint(root);
}

/**Function to print the name and addresses in the address book;*/
void person::printInfo() const
{
	cout<<"Name: "<< personName<<endl;
	cout<<"Address: "<< personAddress <<endl;
	cout<<"Phone Number: "<< personPhoneNum<<endl;	
}

/** Function to check if the name is already in the address book;  */
bool person::checkName(string name)
{
	return(personName == name);
}

/** Function to return a name from the address book;  */
string person::getName()
{
	return personName;
}

/** constructor
	The private data members are set according to the incoming parameters;
	If no values are specified the default values are assigned.
	Postcondition: personName = name;
			personAddress = address;
			personPhoneNum = phoneNum;
			numInBook = setNumInBook;  */
person::person(string name, string address, 
					 string phoneNum)
{
	setPersonalInfo(root, name, address, phoneNum);
}

/**Function to add a name and info to the address book; */
void person::addPerson(treeNode *&root, string name)
{
	binarySearchTree tmp;
	
	tmp.treeInsert(root, name);
}

/**Function to delete a name from the address book; */
void person::deletePerson(treeNode *&root, string name)
{
	binarySearchTree tmp;
		
	tmp.treeDelete(root, name);
}

/**Function to find a name located in the address book;  */
void person::findPerson(treeNode *&root, string name)
{
	binarySearchTree tmp;
	
	if(!tmp.treeContains(root, name))
	{
		cout<<name<<" not found"<<endl;
	}
	else
		cout << name << " found" <<endl;
}

/**Function to modify an entry in the address book;  */
void person::modifyPerson(string name, string address, string phoneNum)
{
	//to be added later
}

/** overload the relational operators */
bool person::operator==(const person& right) const
{
	return (personName == right.personName);
}

bool person::operator!=(const person& right) const
{
	return (personName != right.personName);
}

bool person::operator<(const person& right) const
{
	return (personName < right.personName);
}

bool person::operator<=(const person& right) const
{
	return (personName <= right.personName);
}

bool person::operator>(const person& right) const
{
	return (personName > right.personName);
}

bool person::operator>=(const person& right) const
{
	return (personName >= right.personName);
}

ostream& operator<<(ostream& os, const person &person)
{
	os<<endl;
	os<<"Name: "<< person.personName <<endl;
	os<<"Address: "<< person.personAddress << endl;
	os<<"_____________________________________"<<endl;
	return os;
}

#ifndef binarySearchTree_h
#define binarySearchTree_h

#include <string>
#include <iostream>

using namespace std;

//Define the node
struct treeNode
//An object of type TreeNode 
{
	string data;
	treeNode *left;
	treeNode *right;

treeNode(string str)
		//constructor: Make a node containing str.
{
	data = str;
	left = NULL;
	right = NULL;
}

};

//define the class
class binarySearchTree
{
public:
	binarySearchTree(); 
		//constructor
	void treeInsert(treeNode *&root, string newItem);
		//Add an item to the binary sort tree
		//to which the parameter 'root' refers.
	void treeDelete(treeNode *&root, string deleteItem);
		//Delete an item from the binary sort tree
		//to which the parameter 'root' refers.
	void inOrderPrint(treeNode *&root);
		//Print all the items in the tree to which
		//the tree points
	int countNodes(treeNode *root);
		//count the nodes in the binary tree
		//and return the answer
	bool isEmpty() const;
	    //returns true if tree is empty
	bool treeContains(treeNode *root, string data);
		//return true if item is one of the items in the 
		//binary sort tree to which root points. Return
		//false if not


protected:
	treeNode *root;
	
};
#endif

#include "binarySearchTree.h"

#include <string>
#include <iostream>

using namespace std;

binarySearchTree::binarySearchTree() :root(NULL)
{
}
void binarySearchTree::treeInsert(treeNode *&root, string newItem)
		//Add an item to the binary sort tree
		//to which the parameter 'root' refers.
{
	if(root == NULL)
	{
		//the tree is empty.  Set root to point to a new node containing
		//the new item.  This becomes the only  node in the tree.

		root = new treeNode(newItem);
		//left and right subtrees of root are automatically set to NULL by 
		//the constructor
		return;
	}
	else if(newItem < root->data)
	{
		treeInsert(root->left, newItem);
	}
	else
	{
		treeInsert(root->right, newItem);
	}
}//end treeInsert

void binarySearchTree::treeDelete(treeNode *&root, string deleteItem)
	//Delete an item from the binary sort tree
	//to which the parameter 'root' refers.
{

	treeNode *previous, *tmp = root;

	if(root == NULL)
	{
		//the tree is empty
		cout << "The tree is empty, can't delete from an empty tree" << endl;
	}
	else if(root->right == NULL)
	{
		root = root->left;
	}
	else if(root->left == NULL)
	{
		root = root->right;
	}
	else
	{
		tmp = root->left;
		previous = root;
		while(tmp->right !=NULL)
		{
			previous = tmp;
			tmp = tmp->right;
		}
		root->data = tmp->data;
		if(previous == root)
			previous->left = tmp->left;
		else previous->right = tmp->left;
	}
	delete tmp;
}//end deleteNode

void binarySearchTree::inOrderPrint(treeNode *&root)
	//Print all the items in the tree to which
	//the tree points
{
	if(root !=NULL)
			//otherwise, there is nothing to print
	{
		inOrderPrint(root->left); //prints items in left subtree
		cout << root->data << " ";//print the root item
		cout << endl;
		inOrderPrint(root->right);//print the items in rigth subtree;
	}

}//end inOrderPrint()
int binarySearchTree::countNodes(treeNode *root)
	//count the nodes in the binary tree
	//and return the answer
{
	if(root==NULL)
		return 0;  //the tree is empty
	else
	{
		int count = 1;  //start by counting the root
		count += countNodes(root->left);  //add the number of nodes
										  //in the left subtree
		count += countNodes(root->right); //add the number of nodes
										  //in the right subtree
		return count;  //return the total
	}
}//end countNodes

bool binarySearchTree::isEmpty() const
		//return true if tree is empty
{
	return (root == NULL);
} 

bool binarySearchTree::treeContains(treeNode *root, string data)     
		//return true if item is one of the items in the 
		//binary sort tree to which root points. Return
		//false if not
	{
		if(root==NULL)
			//tree is empty
		{
			cout << "Can't search an empty tree " << endl;
				return false;
		}
		if(data==root->data)
			//item has been found
		{
			return true;
		}
		
		if(data < root->data)
			//item is in left subtree
		{
			return treeContains(root->left, data);
		}
		else
			//item is in right subtree
		{
			return treeContains(root->right, data);
		} 
	
	} //end treeContains()

#include "binarySearchTree.h"
#include "person.h"

#include <iostream>

using namespace std;

int main()
{
	person myList;
	binarySearchTree list;
	treeNode *root;  //pointer to the root noode in the tree
	root = NULL;  //start with an empty tree
	string someName;
	int choice;
	int num = 0;
	
	cout << "What would you like to do? "<< endl;
	cout << "1=insert" << endl;
	cout << "2=count the nodes" << endl;
	cout << "3=print the nodes" << endl; 
	cout << "4=delete a node" << endl;
	cout << "5=find a name" << endl;
	cout << "9=exit "<< endl;
	cout << endl;
	cin >> choice;
	cin.ignore(100, '\n');
	while(choice !=9)
	{
		switch (choice)
		{
		case 1: cout << "Enter a name for the list: " ;
				getline(cin, someName);
				myList.addPerson(root, someName);
				break;

		case 2: cout << "The number of nodes in the tree are: ";
				num =  list.countNodes(root);
				cout << num ; 
				break;

		case 3: cout << "Here is the list: " << endl;
				myList.inOrderPrint(root);
				break;

		case 4: cout << "What item to delete? ";
				getline(cin, someName);
				myList.deletePerson(root, someName);
				cout << someName << "is deleted." << endl;
				list.inOrderPrint(root);
				break;
		case 5: cout << "What name are you searching for? ";
				getline(cin, someName);
				myList.findPerson(root, someName);
				break;

		default: cout << "Invalid selection" << endl;
		
		} //end switch

	cout << endl;
	cout << "What would you like to do? "<< endl;
	cout << "1=insert" << endl;
	cout << "2=count the nodes" << endl;
	cout << "3=print the nodes" << endl; 
	cout << "4=delete a node" << endl;
	cout << "9=exit "<< endl;
	cout << endl;
	cin >> choice;
	cin.ignore(100, '\n');
	cout << endl;
	}//end while
	

	cout << endl;
	return 0;
}

main() is simply a test. My teacher will use a driver file, so I haven't put much effort into making main very pretty

If I enter a list of names as follows:

fred
barney
wilma
dino

and I try to delete dino, fred gets deleted. I assume its simply deleting the root node?

Thanks for your help.

Originally Posted by vart

There is a very clear algorithm in the treeContains (of course it uses recursion but for the start it's OK)

And what about delete? How it supposes to find the node to be deleted if it does not even uses the data to be deleted?

Do you always ignore the compiler warnings? Or your compiler does not warn you if the parameter is not used?

There are no warnings. I blew up my Linux (Ubuntu 6.02) when I tried to update the distribution to the new 6.10. So, I'm using (cough cough) Visual C++.

My confusion is just what you asked. I'm not sure how to pass what I want to be deleted over to the person class. I tried a couple of things, but that is when I started getting errors.

[QUOTE=Prelude]>Its called "delete by copy" and is very elegant, I think.
I know what it is. What you don't seem to understand is that you've implemented it incorrectly. Rather, you've missed a step. Your algorithm does indeed delete a node, and as long as you pass the node you want to delete, all is well. However, first you do this:

Code:

myList.deletePerson(root, someName);

And then you do this:

Code:

tmp.treeDelete(root, name);

There's never a search for someName. You always delete the root of the tree. That's why a deletion algorithm typically includes a search for the data first, then deletes it using a process such as the one you're using. Your code is broken, and it can be easily and repeatedly proven even when you "call it directly" as you claim works:

Code:

int main()
{
  binarySearchTree treeHandler;
  treeNode *root = 0;
  string a[] = {"This", "is", "a", "test"};

  for ( int i = 0; i < 4; i++ )
    treeHandler.treeInsert ( root, a[i] );

  treeHandler.inOrderPrint ( root );
  cout<<"==================\n";
  treeHandler.treeDelete ( root, "a" );
  treeHandler.inOrderPrint ( root );
}

OK, now I see what you were saying. It wasn't clear the first time. So, I need to search for the item first (thought that was happening, now I see the hole), then do the delete. I am not bright enough to follow the code you wrote however. At least I'm not clever enough to figure out how to convert it to strings and use it in my program without big changes.

I suppose I will keep at it until I figure it out.

thanks

Nope, I didn't ignore you. The delete function I am using was proposed by Thomas Hibbard and Donald Knuth. Its called "delete by copy" and is very elegant, I think. It works very well, when I call it directly.

The reason you felt like I was ignoring you, is because I don't want to solve my problem by using your code. My code works, but its in the interface I'm having problems.

I have to restructure everything anyway, because my teacher reminded me there will be a driver he uses (I still don't have access to it) and I can't use the treeNode *&root in the file. SO, back to the drawing board.

I did go to the web site, and it is very well done. If I'm in a test, do you think my teacher would mind if I refer to your web site? Or would it be better for me to use what I know? LOL

You are absolutely right, and, as I mentioned at the end of my first post, I'm passing the root, and that is all that is deleting. I can't seem to figure out how to access the item I'm trying to delete, which is what your response reiterated also. But thank you for your input.

TMS