9 Replies - 2719 Views - Last Post: 09 June 2009 - 02:00 PM Rate Topic: -----

#1 Nec  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 09-June 09

Is there anyone has the template binary search tree class or header fi

Posted 09 June 2009 - 11:51 AM

Hi everyone, i need template binary search tree, but i cannot find it that work.I found several one but they are for specific type(int string etc.), i try to convert them to template class but it gave many error and ı cannot solve.Since if someone has a template binary search tree class which works, can he/she share? thnx
Is This A Good Question/Topic? 0
  • +

Replies To: Is there anyone has the template binary search tree class or header fi

#2 apw5020  Icon User is offline

  • D.I.C Addict

Reputation: 78
  • View blog
  • Posts: 666
  • Joined: 26-March 09

Re: Is there anyone has the template binary search tree class or header fi

Posted 09 June 2009 - 12:08 PM

[rules][/rules]




I made a working one for my class last semester, but I am not willing to just give it to you without you doing some work on your own.

This post has been edited by apw5020: 09 June 2009 - 12:12 PM

Was This Post Helpful? 0
  • +
  • -

#3 computerfox  Icon User is offline

  • straight vegetarian kid

Reputation: 50
  • View blog
  • Posts: 3,772
  • Joined: 29-January 09

Re: Is there anyone has the template binary search tree class or header fi

Posted 09 June 2009 - 12:38 PM

yeah, of course. here ya go!

void yourAnswer(){
while(0==0){
cout<<"So what seems to be the problem...\n";
cout<<"We here at DIC don't do your work for you...\n";
cout<<"We only help with code presented...\n";
cout<<"Please edit your post with your code and specific question...\n";
cout<<"Thank you...\n";
}
return;
}



A+++++++++++++++++ worthy code :D
Was This Post Helpful? 0
  • +
  • -

#4 Nec  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 09-June 09

Re: Is there anyone has the template binary search tree class or header fi

Posted 09 June 2009 - 12:42 PM

then I combine things which is written in Lectures but it is not work.I try to solve errors, but I couldn't.I use dev c++ as compiler.


#include <iostream>
using namespace std;

template <class T>
struct node
{
	   T info;
	   node<T> *llink;
	   node<T> *rlink;
};

template<class T>
class BinaryTree
{
	  public:
			 const BinaryTree<T>& operator=(const BinaryTree<T>&);
			 bool isEmpty();
			 void inordert();
			 void preordert();
			 void postordert();
			 int treeHeight();
			 int treeNodeCount();
			 int treeLeavesCount();
			 void destroyTree();
			 BinaryTree(const BinaryTree<T>& otherTree);
			 BinaryTree();
			 ~BinaryTree();
			 node<T> *root;
	  private:
			  void copyTree(node<T>* &copiedTreeRoot, node<T>* otherTreeRoot);
			  void destroy(node<T>* &p);
			  void inorder(node<T>* p);
			  void preorder(node<T>* p);
			  void postorder(node<T>* p);  
			  int height(node<T> *p);
			  int max(int x,int y);
			  int nodeCount(node<T> *p);
			  int leavesCount(node<T> *p);
};

template<class T>
bool BinaryTree<T>::isEmpty()
{
	 return(root==NULL);
}
template<class T>
BinaryTree<T>::BinaryTree()
{
	root=NULL;
}
template<class T>
void BinaryTree<T>::inordert()
{
	 inorder(root);
}
template<class T>
void BinaryTree<T>::preordert()
{
	 preorder(root);
}
template<class T>
void BinaryTree<T>::postordert()
{
	 postorder(root);
}
template<class T>
int BinaryTree<T>::treeHeight()
{
	return height(root);
}
template<class T>
int BinaryTree<T>::treeNodeCount()
{
	return nodeCount(root);
}
template<class T>
int BinaryTree<T>::treeLeavesCount()
{
	return leavesCount(root);
}
template<class T>
void BinaryTree<T>::inorder(node<T> *p)
{
	 if(p!=NULL)
	 {
				inorder(p->llink);
				cout<<p->info<<" ";
				inorder(p->rlink);
	 }
}
template<class T>
void BinaryTree<T>::preorder(node<T> *p)
{
	 if(p!=NULL)
	 {
				cout<<p->info<<" ";
				preorder(p->llink);
				preorder(p->rlink);
	 }
}
template<class T>
void BinaryTree<T>::postorder(node<T> *p)
{
	 if(p!=NULL)
	 {
				postorder(p->llink);
				postorder(p->rlink);
				cout<<p->info<<" ";
	 }
}
template<class T>
int BinaryTree<T>::height(node<T> *p)
{
	if(p==NULL)
	return 0;
	else
	return (1+max(height(p->llink), height(p->rlink)));
}
template<class T>
int BinaryTree<T>::max(int x, int y)
{
	if(x>=y)
	return x;
	else
	return y;
}
template<class T>
void BinaryTree<T>::copyTree(node<T>* &copiedTreeRoot,node<T>* otherTreeRoot)
{
	 if(otherTreeRoot==NULL)
	 copiedTreeRoot=NULL;
	 else
	 {
		 copiedTreeRoot=new node<T>;
		 copiedTreeRoot->info=otherTreeRoot->info;
		 copyTree(copiedTreeRoot->llink,otherTreeRoot->llink);
		 copyTree(copiedTreeRoot->rlink,otherTreeRoot->rlink);
	 }
}
template<class T>
void BinaryTree<T>::destroy(node<T>* &p)
{
	 if(p!=NULL)
	 {
				destroy(p->llink);
				destroy(p->rlink);
				delete p;
				p=NULL;
	 }
}
template<class T>
void BinaryTree<T>::destroyTree()
{
	 destroy(root);
}
template<class T>
BinaryTree<T>::BinaryTree(const BinaryTree<T>& otherTree)
{
	if(otherTree.root==NULL)
	root=NULL;
	else
	copyTree(root,otherTree.root);
}
template<class T>
BinaryTree<T>::~BinaryTree()
{
  destroy(root);
}
template<class T>
const BinaryTree<T>& BinaryTree<T>::operator=(const BinaryTree<T>& otherTree)
{
	  if(this!=&otherTree)
	  {
		 if(root!=NULL)
		 destroy(root);
		 if(otherTree.root==NULL)
		 root=NULL;
		 else
		 copyTree(root,otherTree.root);
	  }
	  return *this;
}

template<class T>
class bSearchTree:public BinaryTree<T>
{
	  public:
			 bool search(T& searchItem);
			 void insert(T& insertItem);
			 void deleteNode(T& deleteItem);
			 void deleteFromTree(node<T>* &p);
			 node<T>* root;
			 
};
template<class T>
bool bSearchTree<T>::search(T& searchItem)
{
	 node<T> *current;
	 bool found=false;
	 if(root==NULL)
	 cerr<<"cannot search an empty tree."<<endl;
	 else
	 {
		 current=root;
		 while(current!=NULL&&!found)
		 {
			if(current->info==searchItem)
			found=true;
			else
				if(current->info>searchItem)
				current=current->llink;
				else
				current=current->rlink;
				
		 }
	 }
}
template<class T>
void bSearchTree<T>::insert(T& insertItem)
{
	 node<T> *current;
	 node<T> *trailCurrent;
	 node<T> *newNode;
	 newNode=new node<T>;
	 assert(newNode!=NULL);
	 newNode->info=insertItem;
	 newNode->llink=NULL;
	 newNode->rlink=NULL;
	 if(root=NULL)
	 root=newNode;
	 else
	 {
		 current=root;
		 while(current!=NULL)
		 {
			trailCurrent=current;
			if(current->info==insertItem)
			{
			   cerr<<"the insert item is already in the list";
			   return;
			}
			else
			if(current->info>insertItem)
			current=current->llink;
			else
			current=current->rlink;
		 }
		 if(trailCurrent->info>insertItem)
		 trailCurrent->llink=newNode;
		 else
		 trailCurrent->rlink=newNode;
	 }
}

template<class T>
void bSearchTree<T>::deleteFromTree(node<T>* &p)
{
	 node<T> *trailCurrent;
	 node<T> *current;
	 node<T> *temp;
	 if(p==NULL)
	 cerr<<"error: the node to be deleted is NULL."<<endl;
	 else if(p->llink==NULL&&p->rlink==NULL)
	 {
		  temp=p;
		  p=NULL;
		  delete temp;
	 }
	 else if(p->llink==NULL)
	 {
		  temp=p;
		  p=temp->rlink;
		  delete temp;
	 }
	 else if(p->rlink==NULL)
	 {
		  temp=p;
		  p=temp->llink;
		  delete temp;
	 }
	 else
	 {
		 current=p->llink;
		 trailCurrent=NULL;
		 while(current->rlink!=NULL)
		 {
		   trailCurrent=current;
		   current=current->rlink;
		 }
		 p->info=current->info;
		 if(trailCurrent==NULL)
		 p->llink=current->llink;
		 else
		 trailCurrent->rlink=current->llink;
		 delete current;
	 }
}
template<class T>
void bSearchTree<T>::deleteNode(T& deleteItem)
{
	 node<T> *current;
	 node<T> *trailCurrent;
	 bool found=false;
	 if(root==NULL)
	 cerr<<"cannot delete from empty tree."<<endl;
	 else
	 {
		 current=root;
		 trailCurrent=root;
		 while(current!=NULL&&!found)
		 {
		   if(current->info==deleteItem)
		   found=true;
		   else
		   {
			   trailCurrent=current;
			   if(current->info>deleteItem)
			   current=current->rlink;
			   else
			   current=current->rlink;
		   }
		 }
		 if(current==NULL)
		 cout<<"the delete item is not in the list."<<endl;
		 else
		 if(found)
		 {
			if(current==root)
			deleteFromTree(root);
			else
				if(trailCurrent->info>deleteItem)
				deleteFromTree(trailCurrent->llink);
				else
				deleteFromTree(trailCurrent->rlink);
		 }
	 }
}	  

	 
				
		 

 

Was This Post Helpful? 0
  • +
  • -

#5 computerfox  Icon User is offline

  • straight vegetarian kid

Reputation: 50
  • View blog
  • Posts: 3,772
  • Joined: 29-January 09

Re: Is there anyone has the template binary search tree class or header fi

Posted 09 June 2009 - 12:43 PM

do you understand what's going on or did you just take the code your professor gave you?
Was This Post Helpful? 0
  • +
  • -

#6 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Is there anyone has the template binary search tree class or header fi

Posted 09 June 2009 - 12:57 PM

it seems to compile for me... what problems are you having?

Are you receiving any errors? Does this code not work that way you intended it? When asking for help there are a couple items that are vital in order for someone to properly help you:
  • Post the code you're having problems with
  • Post the exact error you're receiving, if you are receiving one
  • If no error explain what the code is doing versus what you want it to do
  • Post your question in the body of your post, not the description field

Was This Post Helpful? 0
  • +
  • -

#7 Nec  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 09-June 09

Re: Is there anyone has the template binary search tree class or header fi

Posted 09 June 2009 - 01:07 PM

of course, I understand but i cannot solve the errors
Was This Post Helpful? 0
  • +
  • -

#8 Nec  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 09-June 09

Re: Is there anyone has the template binary search tree class or header fi

Posted 09 June 2009 - 01:21 PM

ok i solve errors I write a simple program to check the header file.it didnt do anything. Normally this program the number from 0 to 9 insert to tree and print preorder but open screen and there is no anything


#include <iostream>
#include "bst.h"
using namespace std;

main()
{
	  bSearchTree<int> a;
	  
	  for(int i=0;i<10;i++)
	  a.insert(i);
	  a.preordert();
	  int k;
	  cin>>k;
}

This post has been edited by Nec: 09 June 2009 - 01:23 PM

Was This Post Helpful? 0
  • +
  • -

#9 apw5020  Icon User is offline

  • D.I.C Addict

Reputation: 78
  • View blog
  • Posts: 666
  • Joined: 26-March 09

Re: Is there anyone has the template binary search tree class or header fi

Posted 09 June 2009 - 01:55 PM

Try debugging your code. It's too difficult for us to help you unless you ask a specific question.
Was This Post Helpful? 0
  • +
  • -

#10 Nec  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 09-June 09

Re: Is there anyone has the template binary search tree class or header fi

Posted 09 June 2009 - 02:00 PM

i understood anyway :-)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1