Binary search tree help

characters in binary search tree

Page 1 of 1

7 Replies - 2453 Views - Last Post: 16 March 2009 - 08:38 AM Rate Topic: -----

#1 abbyadnez  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 16-March 09

Binary search tree help

Post icon  Posted 16 March 2009 - 05:36 AM

hello,
pls i would need all help u can render in this program. I have a program that implements the basic operations of a binary search tree. But my professor said i should edit and make it in a way that, the nodes would contain characters instead of integers.
heres the code i have, how do i make it accept characters.. thanks :)
#include <iostream>
#include <cstdlib>
using namespace std;

class BinarySearchTree
{
	private:
		struct tree_node
		{
		   tree_node* left;
		   tree_node* right;
		   int data;
		};
		tree_node* root;
	public:
		BinarySearchTree()
		{
		   root = NULL;
		}
		bool isEmpty() const { return root==NULL; }
		void print_inorder();
		void inorder(tree_node*);
		void print_preorder();
		void preorder(tree_node*);
		void print_postorder();
		void postorder(tree_node*);
		void insert(int);
		void remove(int);
};

// Smaller elements go left
// larger elements go right
void BinarySearchTree::insert(int d)
{
	tree_node* t = new tree_node;
	tree_node* parent;
	t->data = d;
	t->left = NULL;
	t->right = NULL;
	parent = NULL;
  // is this a new tree?
  if(isEmpty()) root = t;
  else
  {
	//Note: ALL insertions are as leaf nodes
	tree_node* curr;
	curr = root;
	// Find the Node's parent
	while(curr)
	{
		parent = curr;
		if(t->data > curr->data) curr = curr->right;
		else curr = curr->left;
	}

	if(t->data < parent->data)
	   parent->left = t;
	else
	   parent->right = t;
  }
}

void BinarySearchTree::remove(int d)
{
	//Locate the element
	bool found = false;
	if(isEmpty())
	{
		cout<<" This Tree is empty! "<<endl;
		return;
	}
	tree_node* curr;
	tree_node* parent;
	curr = root;
	while(curr != NULL)
	{
		 if(curr->data == d)
		 {
			found = true;
			break;
		 }
		 else
		 {
			 parent = curr;
			 if(d>curr->data) curr = curr->right;
			 else curr = curr->left;
		 }
	}
	if(!found)
		 {
		cout<<" Data not found! "<<endl;
		return;
	}


		 // 3 cases :
	// 1. We're removing a leaf node
	// 2. We're removing a node with a single child
	// 3. we're removing a node with 2 children

	// Node with single child
	if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
&& curr->right == NULL))
	{
	   if(curr->left == NULL && curr->right != NULL)
	   {
		   if(parent->left == curr)
		   {
			 parent->left = curr->right;
			 delete curr;
		   }
		   else
		   {
			 parent->right = curr->right;
			 delete curr;
		   }
	   }
	   else // left child present, no right child
	   {
		  if(parent->left == curr)
		   {
			 parent->left = curr->left;
			 delete curr;
		   }
		   else
		   {
			 parent->right = curr->left;
			 delete curr;
		   }
	   }
	 return;
	}

		 //We're looking at a leaf node
		 if( curr->left == NULL && curr->right == NULL)
	{
		if(parent->left == curr) parent->left = NULL;
		else parent->right = NULL;
		 		 delete curr;
		 		 return;
	}


	//Node with 2 children
	// replace node with smallest value in right subtree
	if (curr->left != NULL && curr->right != NULL)
	{
		tree_node* chkr;
		chkr = curr->right;
		if((chkr->left == NULL) && (chkr->right == NULL))
		{
			curr = chkr;
			delete chkr;
			curr->right = NULL;
		}
		else // right child has children
		{
			//if the node's right child has a left child
			// Move all the way down left to locate smallest element

			if((curr->right)->left != NULL)
			{
				tree_node* lcurr;
				tree_node* lcurrp;
				lcurrp = curr->right;
				lcurr = (curr->right)->left;
				while(lcurr->left != NULL)
				{
				   lcurrp = lcurr;
				   lcurr = lcurr->left;
				}
		 		 		 		 curr->data = lcurr->data;
				delete lcurr;
				lcurrp->left = NULL;
		   }
		   else
		   {
			   tree_node* tmp;
			   tmp = curr->right;
			   curr->data = tmp->data;
		 		 			curr->right = tmp->right;
			   delete tmp;
		   }

		}
		 return;
	}

}

void BinarySearchTree::print_inorder()
{
  inorder(root);
}

void BinarySearchTree::inorder(tree_node* p)
{
	if(p != NULL)
	{
		if(p->left) inorder(p->left);
		cout<<" "<<p->data<<" ";
		if(p->right) inorder(p->right);
	}
	else return;
}

void BinarySearchTree::print_preorder()
{
  preorder(root);
}

void BinarySearchTree::preorder(tree_node* p)
{
	if(p != NULL)
	{
		cout<<" "<<p->data<<" ";
		if(p->left) preorder(p->left);
		if(p->right) preorder(p->right);
	}
	else return;
}

void BinarySearchTree::print_postorder()
{
  postorder(root);
}

void BinarySearchTree::postorder(tree_node* p)
{
	if(p != NULL)
	{
		if(p->left) postorder(p->left);
		if(p->right) postorder(p->right);
		cout<<" "<<p->data<<" ";
	}
	else return;
}

int main()
{
	BinarySearchTree b;
	int ch,tmp,tmp1;
	while(1)
	{
	   cout<<endl<<endl;
	   cout<<" Binary Search Tree Operations "<<endl;
	   cout<<" ----------------------------- "<<endl;
	   cout<<" 1. Insertion/Creation "<<endl;
	   cout<<" 2. In-Order Traversal "<<endl;
	   cout<<" 3. Pre-Order Traversal "<<endl;
	   cout<<" 4. Post-Order Traversal "<<endl;
	   cout<<" 5. Removal "<<endl;
	   cout<<" 6. Exit "<<endl;
	   cout<<" Enter your choice : ";
	   cin>>ch;
	   switch(ch)
	   {
		   case 1 : cout<<" Enter Number to be inserted : ";
					cin>>tmp;
					b.insert(tmp);
					break;
		   case 2 : cout<<endl;
					cout<<" In-Order Traversal "<<endl;
					cout<<" -------------------"<<endl;
					b.print_inorder();
					break;
		   case 3 : cout<<endl;
					cout<<" Pre-Order Traversal "<<endl;
					cout<<" -------------------"<<endl;
					b.print_preorder();
					break;
		   case 4 : cout<<endl;
					cout<<" Post-Order Traversal "<<endl;
					cout<<" --------------------"<<endl;
					b.print_postorder();
					break;
		   case 5 : cout<<" Enter data to be deleted : ";
					cin>>tmp1;
					b.remove(tmp1);
					break;
		   case 6 : system("pause");
					return 0;
					break;
	   }
	}
}


This post has been edited by abbyadnez: 16 March 2009 - 05:47 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Binary search tree help

#2 tjust80  Icon User is offline

  • D.I.C Head

Reputation: 11
  • View blog
  • Posts: 73
  • Joined: 01-December 08

Re: Binary search tree help

Posted 16 March 2009 - 05:48 AM

u can use
char data;
void insert(char);
void remove(char);



nested of this
int data;
void insert(int);
void remove(int);


Was This Post Helpful? 0
  • +
  • -

#3 abbyadnez  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 16-March 09

Re: Binary search tree help

Posted 16 March 2009 - 05:57 AM

View Posttjust80, on 16 Mar, 2009 - 04:48 AM, said:

u can use
char data;
void insert(char);
void remove(char);



nested of this
int data;
void insert(int);
void remove(int);



i already did, it compiled but doesnt work

This post has been edited by abbyadnez: 16 March 2009 - 06:05 AM

Was This Post Helpful? 0
  • +
  • -

#4 tjust80  Icon User is offline

  • D.I.C Head

Reputation: 11
  • View blog
  • Posts: 73
  • Joined: 01-December 08

Re: Binary search tree help

Posted 16 March 2009 - 06:22 AM

it works fine, but u need to handle the input parameters
Was This Post Helpful? 0
  • +
  • -

#5 abbyadnez  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 16-March 09

Re: Binary search tree help

Posted 16 March 2009 - 06:28 AM

View Posttjust80, on 16 Mar, 2009 - 05:22 AM, said:

it works fine, but u need to handle the input parameters

which ones shuld i edit?
Was This Post Helpful? 0
  • +
  • -

#6 tjust80  Icon User is offline

  • D.I.C Head

Reputation: 11
  • View blog
  • Posts: 73
  • Joined: 01-December 08

Re: Binary search tree help

Posted 16 March 2009 - 06:32 AM

u need to handle the length of input characters

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

class BinarySearchTree
{
	private:
		struct tree_node
		{
		   tree_node* left;
		   tree_node* right;
		   char data;
		};
		tree_node* root;
	public:
		BinarySearchTree()
		{
		   root = NULL;
		}
		bool isEmpty() const { return root==NULL; }
		void print_inorder();
		void inorder(tree_node*);
		void print_preorder();
		void preorder(tree_node*);
		void print_postorder();
		void postorder(tree_node*);
		void insert(char);
		void remove(char);
};

// Smaller elements go left
// larger elements go right
void BinarySearchTree::insert(char d)
{
	tree_node* t = new tree_node;
	tree_node* parent;
	t->data = d;
	t->left = NULL;
	t->right = NULL;
	parent = NULL;
  // is this a new tree?
  if(isEmpty()) root = t;
  else
  {
	//Note: ALL insertions are as leaf nodes
	tree_node* curr;
	curr = root;
	// Find the Node's parent
	while(curr)
	{
		parent = curr;
		if(t->data > curr->data) curr = curr->right;
		else curr = curr->left;
	}

	if(t->data < parent->data)
	   parent->left = t;
	else
	   parent->right = t;
  }
}

void BinarySearchTree::remove(char d)
{
	//Locate the element
	bool found = false;
	if(isEmpty())
	{
		cout<<" This Tree is empty! "<<endl;
		return;
	}
	tree_node* curr;
	tree_node* parent;
	curr = root;
	while(curr != NULL)
	{
		 if(curr->data == d)
		 {
			found = true;
			break;
		 }
		 else
		 {
			 parent = curr;
			 if(d>curr->data) curr = curr->right;
			 else curr = curr->left;
		 }
	}
	if(!found)
		 {
		cout<<" Data not found! "<<endl;
		return;
	}


		 // 3 cases :
	// 1. We're removing a leaf node
	// 2. We're removing a node with a single child
	// 3. we're removing a node with 2 children

	// Node with single child
	if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
&& curr->right == NULL))
	{
	   if(curr->left == NULL && curr->right != NULL)
	   {
		   if(parent->left == curr)
		   {
			 parent->left = curr->right;
			 delete curr;
		   }
		   else
		   {
			 parent->right = curr->right;
			 delete curr;
		   }
	   }
	   else // left child present, no right child
	   {
		  if(parent->left == curr)
		   {
			 parent->left = curr->left;
			 delete curr;
		   }
		   else
		   {
			 parent->right = curr->left;
			 delete curr;
		   }
	   }
	 return;
	}

		 //We're looking at a leaf node
		 if( curr->left == NULL && curr->right == NULL)
	{
		if(parent->left == curr) parent->left = NULL;
		else parent->right = NULL;
				  delete curr;
				  return;
	}


	//Node with 2 children
	// replace node with smallest value in right subtree
	if (curr->left != NULL && curr->right != NULL)
	{
		tree_node* chkr;
		chkr = curr->right;
		if((chkr->left == NULL) && (chkr->right == NULL))
		{
			curr = chkr;
			delete chkr;
			curr->right = NULL;
		}
		else // right child has children
		{
			//if the node's right child has a left child
			// Move all the way down left to locate smallest element

			if((curr->right)->left != NULL)
			{
				tree_node* lcurr;
				tree_node* lcurrp;
				lcurrp = curr->right;
				lcurr = (curr->right)->left;
				while(lcurr->left != NULL)
				{
				   lcurrp = lcurr;
				   lcurr = lcurr->left;
				}
									curr->data = lcurr->data;
				delete lcurr;
				lcurrp->left = NULL;
		   }
		   else
		   {
			   tree_node* tmp;
			   tmp = curr->right;
			   curr->data = tmp->data;
							  curr->right = tmp->right;
			   delete tmp;
		   }

		}
		 return;
	}

}

void BinarySearchTree::print_inorder()
{
  inorder(root);
}

void BinarySearchTree::inorder(tree_node* p)
{
	if(p != NULL)
	{
		if(p->left) inorder(p->left);
		cout<<" "<<p->data<<" ";
		if(p->right) inorder(p->right);
	}
	else return;
}

void BinarySearchTree::print_preorder()
{
  preorder(root);
}

void BinarySearchTree::preorder(tree_node* p)
{
	if(p != NULL)
	{
		cout<<" "<<p->data<<" ";
		if(p->left) preorder(p->left);
		if(p->right) preorder(p->right);
	}
	else return;
}

void BinarySearchTree::print_postorder()
{
  postorder(root);
}

void BinarySearchTree::postorder(tree_node* p)
{
	if(p != NULL)
	{
		if(p->left) postorder(p->left);
		if(p->right) postorder(p->right);
		cout<<" "<<p->data<<" ";
	}
	else return;
}

int main()
{
	BinarySearchTree b;
	char tmp,tmp1;
	int ch;
	while(1)
	{
	   cout<<endl<<endl;
	   cout<<" Binary Search Tree Operations "<<endl;
	   cout<<" ----------------------------- "<<endl;
	   cout<<" 1. Insertion/Creation "<<endl;
	   cout<<" 2. In-Order Traversal "<<endl;
	   cout<<" 3. Pre-Order Traversal "<<endl;
	   cout<<" 4. Post-Order Traversal "<<endl;
	   cout<<" 5. Removal "<<endl;
	   cout<<" 6. Exit "<<endl;
	   cout<<" Enter your choice : ";
	   cin>>ch;
	   switch(ch)
	   {
		   case 1 : cout<<" Enter Number to be inserted : ";
					cin>>tmp;
					b.insert(tmp);
					break;
		   case 2 : cout<<endl;
					cout<<" In-Order Traversal "<<endl;
					cout<<" -------------------"<<endl;
					b.print_inorder();
					break;
		   case 3 : cout<<endl;
					cout<<" Pre-Order Traversal "<<endl;
					cout<<" -------------------"<<endl;
					b.print_preorder();
					break;
		   case 4 : cout<<endl;
					cout<<" Post-Order Traversal "<<endl;
					cout<<" --------------------"<<endl;
					b.print_postorder();
					break;
		   case 5 : cout<<" Enter data to be deleted : ";
					cin>>tmp1;
					b.remove(tmp1);
					break;
		   case 6 : system("pause");
					return 0;
					break;
	   }
	}
}



Was This Post Helpful? 0
  • +
  • -

#7 abbyadnez  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 16-March 09

Re: Binary search tree help

Posted 16 March 2009 - 07:09 AM

The problem is when comparing the characters
Was This Post Helpful? 0
  • +
  • -

#8 abbyadnez  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 16-March 09

Re: Binary search tree help

Posted 16 March 2009 - 08:38 AM

i alredy modified, but how do i compare the characters so as to knw wat side of the node to insert it
heres the code
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;


class Map
{
//private:
public:
	struct tree_node
	{
		tree_node* left;
		tree_node* right;
		double data;
		char * key;
	};
	tree_node* root;

//public:
	Map()
	{
		root = NULL;
	}

	bool isEmpty() const { return root==NULL; }
	void print_inorder();
	void inorder(tree_node*);
	void print_preorder();
	void preorder(tree_node*);
	void print_postorder();
	void postorder(tree_node*);
	void find(char * ch);	
	void insert(char * ch, double d);
	void remove(char * dkey);
};

// Smaller elements go left
// larger elements go right

void Map::find(char * ch)
{
	bool isfind = false;
	tree_node* curr;
	curr = root;
	while(curr)
	{
		if(strcmp(ch, curr->key)==0)
		{
			cout << "found\n";
			isfind = true;
			break;
		}
		else if(strcmp(ch, curr->key)>0)
			curr = curr->right;
		else if(strcmp(ch, curr->key)<0)
			curr = curr->left;
	}

	if(!isfind)
		cout << "data not found\n";
}

void Map::insert(char * ch, double d)
{
	tree_node* t = new tree_node;
	tree_node* parent;
	t->key = ch;
	t->data = d;
	t->left = NULL;
	t->right = NULL;
	parent = NULL;

	// is this a new tree?
	if(isEmpty()) 
		root = t;
	else
	{
		//Note: ALL insertions are as leaf nodes
		tree_node* curr;
		curr = root;
		// Find the Node's parent
		while(curr)
		{
			parent = curr;
			if(strcmp(t->key, curr->key)) 
				curr = curr->right;
			else 
				curr = curr->left;
		}

		if(strcmp(t->key, parent->key))
			parent->right = t;
		else
			parent->left = t;
	}
}

void Map::remove(char * dkey)
{
	//Locate the element
	bool found = false;
	if(isEmpty())
	{
		cout<<" This Tree is empty! "<<endl;
		return;
	}

	tree_node* curr;
	tree_node* parent;
	curr = root;

   while(curr != NULL)
	{
		if(strcmp(curr->key,dkey)==0)
		{
			found = true;
			break;
		}
		else
		{
			parent = curr;
			if(strcmp(curr->key, dkey))
				curr = curr->right;
			else 
				curr = curr->left;
		}
	}
	if(!found)
	{
		cout<<" Data not found! "<<endl;
		return;
	}


	// 3 cases :
	// 1. We're removing a leaf node
	// 2. We're removing a node with a single child
	// 3. we're removing a node with 2 children

	// Node with single child
	if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL && curr->right == NULL))
	{
		if(curr->left == NULL && curr->right != NULL)
		{
			if(parent->left == curr)
			{
				parent->left = curr->right;
				delete curr;
			}
			else
			{
				parent->right = curr->right;
				delete curr;
			}
		}
		else // left child present, no right child
		{
			if(parent->left == curr)
			{
				parent->left = curr->left;
				delete curr;
			}
			else
			{
				parent->right = curr->left;
				delete curr;
			}
		}
		return;
	}

	//We're looking at a leaf node
	if( curr->left == NULL && curr->right == NULL)
	{
		if(parent->left == curr)//////////error///////////////////
			parent->left = NULL;
		else 
			parent->right = NULL;
		delete curr;
		return;
	}


	//Node with 2 children
	// replace node with smallest value in right subtree
	if (curr->left != NULL && curr->right != NULL)
	{
		tree_node* chkr;
		chkr = curr->right;
		if((chkr->left == NULL) && (chkr->right == NULL))
		{
			curr = chkr;
			delete chkr;
			curr->right = NULL;
		}
		else // right child has children
		{
			//if the node's right child has a left child
			// Move all the way down left to locate smallest element

			if((curr->right)->left != NULL)
			{
				tree_node* lcurr;
				tree_node* lcurrp;
				lcurrp = curr->right;
				lcurr = (curr->right)->left;
				while(lcurr->left != NULL)
				{
					lcurrp = lcurr;
					lcurr = lcurr->left;
				}
				curr->key = lcurr->key;
				delete lcurr;
				lcurrp->left = NULL;
			}
			else
			{
				tree_node* tmp;
				tmp = curr->right;
				curr->key = tmp->key;
				curr->right = tmp->right;
				delete tmp;
			}

		}
		return;
	}

}


void Map::print_inorder()
{
	inorder(root);
}

void Map::inorder(tree_node* p)
{
	if(p != NULL)
	{
		if(p->left) inorder(p->left);
			cout <<" Salary[\""<<p->key <<"\"]="; cout <<p->data<<endl;
		if(p->right) inorder(p->right);
	}
	else return;
}
void Map::print_preorder()
{
  preorder(root);
}

void Map::preorder(tree_node* p)
{
	if(p != NULL)
	{
		cout<<"salary "<<p->data<<" ";
		if(p->left) preorder(p->left);
		if(p->right) preorder(p->right);
	}
	else return;
}
void Map::print_postorder()
{
  postorder(root);
}

void Map::postorder(tree_node* p)
{
	if(p != NULL)
	{
		if(p->left) postorder(p->left);
		if(p->right) postorder(p->right);
		cout<<" salary"<<p->data<<" ";
	}
	else return;
}
int main()
{
	Map b;
	string temp, ftarget, dtarget;
	int ch,tmp,tmp1,size;
	double data;
	while(1)
	{
		cout<<endl<<endl;
		cout<<" Binary Search Tree Operations "<<endl;
	   cout<<" ----------------------------- "<<endl;
	   cout<<" 1. Insertion/Creation "<<endl;
	   cout<<" 2. In-Order Traversal "<<endl;
	   cout<<" 3. Pre-Order Traversal "<<endl;
	   cout<<" 4. Post-Order Traversal "<<endl;
	   cout<<" 5. Removal "<<endl;
	   cout<<" 6. Find "<<endl;
	   cout<<" 7. Exit "<<endl;
	   cout<<" Enter your choice : ";
	   cin>>ch;
		char * pch;
		switch(ch)
		{
			case 1 : cout<<" Enter key: ";
				cin>>temp;
				pch = (char *) malloc(sizeof(char)*temp.size()); 
				strcpy(pch, temp.c_str());				
				break;
			case 2 : cout<<endl;
				cout<<" In-Order Traversal "<<endl;
			   
				b.print_inorder();
				break;		

			case 3 : cout<<endl;
				cout<<" Pre-Order Traversal "<<endl;
				cout<<" -------------------"<<endl;
				b.print_inorder();
				break;
				
			case 4 : cout<<endl;
				cout<<" Post-Order Traversal "<<endl;
				cout<<" --------------------"<<endl;
				b.print_postorder();
				break;
				
			case 5 : cout<<" Enter key to be deleted : ";
				cin >> temp;
				pch = (char *) malloc(sizeof(char)*temp.size()); 
				strcpy(pch, temp.c_str());
				b.remove(pch);
				break;
			case 6: cout << "Enter key: ";
				cin >> temp;
				pch = (char *) malloc(sizeof(char)*temp.size()); 
				strcpy(pch, temp.c_str());
				b.find(pch);
				break;
			case 7 : system("pause");
				   
					break;

		}
	}

	return 0;
	
}


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1