please help???

rawah's Avatar, Join Date: Apr 2008
Light Poster
hello,

i use tree ADt to do my program, but i can not find function search(),

i need it,

i do one but it shows error

could u help????

thank u very much
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
Can you please clarify which ADT and why you are looking for the function search?
rawah's Avatar, Join Date: Apr 2008
Light Poster
my problem is to insert the employee and search about key= 1 (busy employee)
or key= 0 (not busy)

when i find the employee who is not busy i will set the key to 1 because the employee will be busy and vice versa

i use AVL ADT :

Code:
#include <iostream>
#include<cstdio>
#include <string>

using namespace std;


//==================== MACROS ====================
#define LH +1	// Left High
#define EH 0	// Even High
#define RH -1	// Right High

// NODE Definitions
template <class TYPE>
struct NODE
{
	TYPE data;
	NODE *left;
	int bal;
	NODE *right;
} ; // NODE

// Class Declaration
template <class TYPE, class KTYPE>
class AvlTree
{
private:
	int count;
	NODE<TYPE> *_insert(NODE<TYPE> *root,NODE<TYPE> *newPtr,bool& taller);
	NODE<TYPE> *leftBalance 	(NODE<TYPE> *root,bool& taller);
	NODE<TYPE> *rotateLeft		(NODE<TYPE> *root);
	NODE<TYPE> *rightBalance 	(NODE<TYPE> *root,bool& taller); 
	NODE<TYPE> *rotateRight 	(NODE<TYPE> *root);
	NODE<TYPE> *_delete			(NODE<TYPE> *root,KTYPE dltKey, bool& shorter, bool& seccess);
	NODE<TYPE> *dltLeftBalance	(NODE<TYPE> *root ,bool& smaller);
	NODE<TYPE> *dltRightBalance (NODE<TYPE> *root ,bool& shorter);
	NODE<TYPE> *_retrieve		(KTYPE	key,NODE<TYPE> *root);
	void _traversal 			(void (*process) (TYPE dataproc) ,NODE<TYPE> *root);
	void _destroyAVL 			(NODE<TYPE> *root);
public:
	NODE<TYPE> *tree;
	AvlTree (void);
	~AvlTree (void);
	bool AVL_Insert (TYPE dataIn);
	bool AVL_Delete (KTYPE dltKey);
	bool AVL_Retrieve (KTYPE key, TYPE& dataOut);
	void AVL_Traverse (void (*process)(TYPE dataProc));
	bool AVL_Empty (void);
	bool AVL_Full	(void) ;
	int	AVL_Count	(void);
}; // class AvlTree
/*=====================Constructor====================
Initializes private data.
Pre 	class is being defined
Post 	private data initialized
*/
template <class TYPE, class KTYPE>
AvlTree<TYPE, KTYPE>:: AvlTree (void) 
{
	//Statements
	tree= NULL;
	count = 0;
} // Constructor
/*==================== AVL_Insert ====================
This function inserts new data into the tree.
Pre 	dataln contains data to be inserted
Post 	data have been inserted or memory overflow Return success (true) or overflow (false)
*/
template <class TYPE, class KTYPE>
bool  AvlTree<TYPE, KTYPE> :: AVL_Insert (TYPE dataIn) 
{
	//Local Definitions
	NODE<TYPE> *newPtr;
	bool taller;
	
	//Statements
	if (!(newPtr = new NODE<TYPE>))
		return false;
	newPtr->bal= EH;
	newPtr->right = NULL;
	newPtr->left = NULL;
	newPtr->data = dataIn;
	tree=_insert(tree,newPtr,taller);
	count++;
	return true;
} // Avl_Insert
/*======================= _insert ======================= 
This function uses recursion to insert the new data into a leaf node in the AVL tree.
Pre 	application has called AVL_Insert, which passes
	root and data pointers 
Post 	data have been inserted
Return 	pointer to [potentially] new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE> ::_insert(NODE<TYPE> *root,NODE<TYPE> *newPtr,bool& taller)
{
	// statements
	if (! root)
	{
		root	= newPtr;
		taller = true;
		return root;
	} // if NULL tree
	if (newPtr->data.key < root->data.key)
	{
		root->left = _insert(root->left,newPtr,taller);
		if (taller)
			// Left subtree is taller
			switch (root->bal)
			{
				case LH: // Was left high--rotate
					root = leftBalance (root, taller);
					break;
				case EH: // Was balanced--now LH
					root->bal = LH;
					break;
				case RH: // Was right high--now EH root->bal = EH;
					taller	= false;
					break;
			} // switch
	} // new < node
	else
	// new data >= root data
	{
		root->right = _insert (root->right,newPtr,taller) ;
		if (taller)
			// Right subtree is taller
			switch (root->bal)
			{
				case LH: // Was left high--now EH 
					root->bal = EH;
					taller = false;
					break;
				case EH: // Was balanced--now RH
					root->bal = RH;
					break;
				case RH: // Was right high--rotate
					root = rightBalance (root, taller); 
					break;
			} // switch
	} // else new data >= root data
	return root;
} // _insert
/*===================== rightBalance ===================== 
The tree is out of balance to the right This function rotates the tree to the left.
Pre	the tree is right high
Post	balance restored
Returns potentially new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE> *AvlTree<TYPE, KTYPE>:: rightBalance (NODE<TYPE> *root,bool& taller)
{
	// Local Definitions
	NODE<TYPE> *rightTree;
	NODE<TYPE> *leftTree;
	
	// Statements
	rightTree = root->right;
	switch (rightTree->bal)
	{
		case RH: 
			root->bal= EH;
			rightTree->bal = EH;
			root	= rotateLeft (root);
			taller = false;
			break;
		case EH: 
			cout <<"\n\a\aError in leftBalance\n";
			exit (100);
		case LH: 
			leftTree = rightTree->left;
			switch (leftTree->bal)
			{
				case RH:	
					root->bal= LH;
					rightTree->bal = EH;
					break;
				case EH:	
					root->bal= EH;
					rightTree->bal = EH;
					break;
				case LH:	
					root->bal= EH;
					rightTree->bal = RH;
					break;
			} 
			leftTree->bal = EH;
			root->right = rotateRight (rightTree);
			root	= rotateLeft (root);
			taller = false;
	} 
	return root;
}
/*===================== leftBalance ===================== 
The tree is out of balance to the left. This function rotates the tree to the right.
Pre	the tree is left high
Post	balance restored
Returns potentially new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE> *AvlTree<TYPE, KTYPE>:: leftBalance (NODE<TYPE> *root,bool& taller)
{
	// Local Definitions
	NODE<TYPE> *rightTree;
	NODE<TYPE> *leftTree;
	
	// Statements
	leftTree = root->left;
	switch (leftTree->bal)
	{
		case LH: // Left High--Rotate Right
			root->bal= EH;
			leftTree->bal = EH;
			// Rotate Right
			root	= rotateRight (root);
			taller = false;
			break;
		case EH: // This is an error
			cout <<"\n\a\aError in leftBalance\n";
			exit (100);
		case RH: // Right High - Requires double rotation:
			 // first left, then right
			rightTree = leftTree->right;
			switch (rightTree->bal)
			{
				case LH:	
					root->bal= RH;
					leftTree->bal = EH;
					break;
				case EH:	
					root->bal= EH;
					leftTree->bal = EH;
					break;
				case RH:	
					root->bal= EH;
					leftTree->bal = LH;
					break;
			} // switch rightTree
			rightTree->bal = EH;
			// Rotate Left
			root->left = rotateLeft (leftTree);
			// Rotate Right
			root	= rotateRight (root);
			taller = false;
	} // switch leftTree
	return root;
} // leftBalance
/*===================== rotateLeft =====================
This function exchanges pointers so as to rotate the tree to the left.
Pre 	root points to tree to be rotated
Post 	NODE rotated and new root returned
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>:: rotateLeft (NODE<TYPE> *root)
{
	// Local Definitions
	NODE<TYPE> *tempPtr;
	
	// Statements
	tempPtr	= root->right;
	root->right = tempPtr->left;
	tempPtr->left = root;
	return tempPtr;
} // rotateLeft
/*===================== rotateRight =====================
This function exchanges pointers to rotate the tree to the right.
Pre 	root points to tree to be rotated
Post 	NODE rotated and new root returned
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>:: rotateRight (NODE<TYPE> *root)
{
	// Local Definitions
	NODE<TYPE> *tempPtr;

	// Statements
	tempPtr	= root->left;
	root->left= tempPtr->right;
	tempPtr->right = root;
	return tempPtr;
} // rotateRight
/* ====================== AVL _Delete =============--------¬
This function deletes a node from the tree and rebalances it if necessary.
Pre	dltKey contains key to be deleted
Post 	the node is deleted and its space recycled
	-or- an error code is returned
Return success (true) or not found (false)
*/
template <class TYPE, class KTYPE>
bool AvlTree <TYPE, KTYPE> :: AVL_Delete (KTYPE dltKey)
{
	// Local Definitions
	bool shorter;
	bool success;
 	NODE<TYPE> *newRoot;

	// statements
 	newRoot = _delete (tree, dltKey, shorter, success);
 	if (success)
 	{
		tree = newRoot;
 		count--;
	} // if
	return success;
} //AVL_Delete
/* ======================== _delete ======================= 
This function deletes a node from the tree and rebalances it if necessary.
Pre 	dltKey contains key of node to be deleted
	shorter is Boolean indicating tree is shorter
Post 	the node is deleted and its space recycled
	-or- if key not found, tree is unchanged
Return 	true if deleted, false if not found pointer to root
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>:: _delete (NODE<TYPE> *root,KTYPE dltKey,bool& shorter,bool& success)
{
	// Local Definitions
	NODE<TYPE> *dltptr;
	NODE<TYPE> *exchPtr;
	NODE<TYPE> *newRoot;
	// Statements
	if (! root)
	{
		shorter = false;
		success = false;
		return NULL;
	} // if -- base case
	if (dltKey < root->data.key)
	{
		root->left = _delete (root->left, dltKey,shorter, success);
		if (shorter)
			root = dltRightBalance (root, shorter);
	} // if less
	else if (dltKey> root->data.key)
	{
		root->right = _delete (root->right, dltKey,shorter, success);
		if (shorter)
			root = dltLeftBalance (root, shorter);
	} // if greater
	else
	//Found equal node
	{
		dltptr = root;
		if (!root->right)
		// Only left subtree
		{
			newRoot = root->left;
			success = true; 
			shorter = true; 
			delete (dltptr);
			return newRoot;		//base case
		} // if true
		else if (!root->left)
		// Only right subtree
		{
			newRoot = root->right;
			success = true; shorter = true; delete (dltptr);
			return newRoot;		// base case
		} // if
		else
		// Delete NODE has two subtrees
		{
		exchPtr = root->left;
		while (exchPtr->right)
			exchPtr = exchPtr->right;
		root->data = exchPtr->data;
		root->left = _delete (root->left,exchPtr->data.key, shorter,success);
		if (shorter)
			root = dltRightBalance (root, shorter);
		} // else
	} // equal node
	return root;
} // _delete
/* =================== dltRightBalance ================== 
The tree is shorter after a delete on the left.
Adjust the balance factors and rotate the tree to the left if necessary.
Pre	the tree is shorter
Post	balance factors adjusted and balance restored
Returns potentially new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>:: dltRightBalance (NODE<TYPE> * root ,bool& shorter) 
{ 	// Local Definitions
	NODE<TYPE> *rightTree;
	NODE<TYPE> *leftTree;
	
	//Statements
	switch (root->bal)
	{
		case LH: // Deleted Left--Now balanced
			root->bal = EH;
			break;
		case EH: // Now Right high
			root->bal = RH;
			shorter = false;
			break;
		case RH: // Right High - Rotate Left
			rightTree = root->right;
			if (rightTree->bal == LH)
			// Double rotation required
			{
				leftTree = rightTree->left;
				switch (leftTree->bal)
				{
					case LH: 
						rightTree->bal = RH;
						root->bal= EH;
						break;
					case EH: 
						root->bal= EH;
						rightTree->bal = EH;
						break;
					case RH: 
						root->bal= LH;
						rightTree->bal = EH;
						break;
				} // switch
				leftTree->bal = EH;
				// Rotate Right then Left 
				root->right = rotateRight (rightTree);
				root= rotateLeft(root);
			} // if rightTree->bal == LH
			else
			{
				// Single Rotation Only
				switch (rightTree->bal)
				{
					case LH:
					case RH: 
						root->bal= EH;
						rightTree->bal = EH;
						break;
					case EH: 
						root->bal= RH;
						rightTree->bal = LH;
						shorter	= false;
						break;
				} // switch rightTree->bal
				root = rotateLeft (root);
			} // else
	} // switch root bal
	return root;
}// dltRiqhtBalance
/* =================== dltleftBalance ================== 
The tree is shorter after a delete on the right.
Adjust the balance factors and rotate the tree to the right if necessary.
Pre	the tree is shorter
Post	balance factors adjusted and balance restored
Returns potentially new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>:: dltLeftBalance (NODE<TYPE> * root ,bool& smaller) 
{ 	
	// Local Definitions
	NODE<TYPE> *rightTree;
	NODE<TYPE> *leftTree;
	
	//Statements
	switch (root->bal)
	{
		case RH: 
			root->bal = EH;
			break;
		case EH: 
			root->bal = LH;
			smaller = false;
			break;
		case LH: 
			leftTree = root->left;
			if (leftTree->bal == RH)
			{
				rightTree = leftTree->right;
				switch (rightTree->bal)
				{
					case RH: 
						leftTree->bal = LH;
						root->bal= EH;
						break;
					case EH: 
						root->bal= EH;
						leftTree->bal = EH;
						break;
					case LH: 
						root->bal= RH;
						leftTree->bal = EH;
						break;
				} // switch
				rightTree->bal = EH; 
				root->left = rotateLeft (leftTree);
				root= rotateRight(root);
			} 
			else
			{
				
				switch (leftTree->bal)
				{
					case RH:
					case LH: 
						root->bal= EH;
						leftTree->bal = EH;
						break;
					case EH: 
						root->bal= LH;
						leftTree->bal = RH;
						smaller	= false;
						break;
				} 
				root = rotateRight (root);
			} // else
	} 
	return root;
}// dltleftBalance
/*==================== AVL_Retrieve ==================== 
Retrieve node searches the tree for the node containing the requested key and returns pointer to its data.
Pre	dataOut is variable to receive data
Post 	tree searched and data returned
Return 	true if found, false if not found
*/
template <class TYPE, class KTYPE>
bool AvlTree<TYPE,KTYPE>:: AVL_Retrieve (KTYPE key, TYPE& dataOut)
{ 
	// Local Definitions
	NODE<TYPE> *node;
	
	// Statements
	if (! tree)
		return false;
	node = _retrieve (key,tree);
	if (node)
	{
		dataOut = node->data;
		return true;
	} // if found
	else
		return false;
} // AVL_Retrieve
/*===================== _retrieve ===================== 
Retrieve searches tree for node c_ntaining requested key and returns its data to the calling function.
Pre 	AVL_Retrieve called: passes key to be locat. 
Post 	tree searched and data pointer returned 
Return 	address of matching node returned
	if not foundt NULL returned
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>::_retrieve (KTYPE key,NODE<TYPE> *root) 
{ 
	// statements
	if (root)
	{
		if (key < root->data.key)
			return _retrieve (key, root->left);
		else if (key > root->data.key)
			return _retrieve (key, root->right);
		else
			// Found equal key
			return (root);
	} // if root
	else
		//Data not in tree
		return root;
}// _retrieve
/*==================== AVL Traverse ====================
Process tree using inorder traversal.
Pre 	process used to "visit" nodes during traversal
Post 	all nodes processed in LNR (inorder) sequence
*/
template <class TYPE, class KTYPE>
void AvlTree<TYPE, KTYPE>:: AVL_Traverse (void (*process) (TYPE dataProc))
{
	// Statements
	_traversal (process, tree);
	return;
}// end AVL_Traverse
/* ===================== _traversal =====================
Traverse tree using inorder traversal. To process a node, we use the function passed when traversal is called.
Pre	tree has been created (may be null)
Post 	all nodes processed
*/
template <class TYPE, class KTYPE>
void AvlTree<TYPE, KTYPE>:: _traversal (void(*process) (TYPE dataproc),NODE<TYPE> *root) 
{ 	// statements
	if (root)
	{
		_traversal (process, root->left); 
		process (root->data);
		_traversal (process, root->right);
	} // if
	return;
} // _traversal
/*=================== AVL_Empty ==================
Returns true if tree is empty, false if any data.
Pre	tree has been created; may be null
Returns true if tree empty, false if any data
*/
template <class TYPE, class KTYPE>
bool AvlTree<TYPE, KTYPE> :: AVL_Empty (void) 
{
	//Statements
	return (count == 0);
}//AVL_Empty
/*=================== AVL_Full ===================
If there is no room for another node, returns true.
Pre	tree has been created
Returns true if no room, false if room
*/
template <class TYPE, class KTYPE>
bool AvlTree<TYPE, KTYPE> :: AVL_Full (void) 
{
	// Local Definitions
	NODE<TYPE> *newPtr;
	
	// Statements
	newPtr = new NODE<TYPE>;
	if (newPtr)
	{
		delete newPtr;
		return false;
	} // if
	else
		return true;
} // AVL_Full
/*================ AVL_count ===================
Returns number of nodes in tree.
Pre 	tree has been created
Returns tree count
*/
template <class TYPE, class KTYPE>
int AvlTree<TYPE, KTYPE>:: AVL_Count (void)
{
	// statements
	
	return (count);
}// AVL_count
/*=================== Destructor ===================
Deletes all data in tree and recycles memory.
The nodes are deleted by calling a recursive
function to traverse the tree in inorder sequence.
Pre 	tree is a pointer to a valid tree 
Post 	all data have been deleted
*/
template <class TYPE, class KTYPE>
AvlTree<TYPE, KTYPE> :: ~AvlTree (void)
{
	// statements
	if (tree)
		_destroyAVL (tree);
}// Destructor
/*=================== _destroyAvL ===================
Deletes all data in tree and recycles memory.
The nodes are deleted by calling a recursive
function to traverse the tree in postorder sequence.
Pre 	tree is being destroyed
Post 	all data have been deleted
*/
template <class TYPE, class KTYPE> void AvlTree<TYPE, KTYPE>:: _destroyAVL (NODE<TYPE> *root)
{
	// statements
	if (root)
	{
		_destroyAVL (root->left); 
		_destroyAVL (root->right); 
		delete root;
	} // if
	return;
} //_ destroyAVL
//========================END========================



the search function which i did but it shows errors :





string search(int key)
{
	AvlTree *parnt;
	parnt=tree;
	
	string x="no one";
	
	if (parnt==NULL)
	{
		return x;
	}
	else
	while(parnt!=NULL)
	{
		if(key<parnt->key)
		  {
		  	parnt=parnt->left;
		  }
		
		if(key>parnt->key)
		  {
		  	 parnt=parnt->right;
		  }
		  
		  if(key==parnt->key)
		  {
		  	return tree->name;
		  }
		   
		 	 
	}  
}
thanks

Last edited by shabbir; 22May2008 at 22:05.. Reason: Code block
rawah's Avatar, Join Date: Apr 2008
Light Poster
i use this struct

struct employee
{
string name;
int key;
}
rawah's Avatar, Join Date: Apr 2008
Light Poster
hi,

i write search function which i did it with the ADT code

realy i can not find the error i do not know where is the problem with my code


shabbir

i looking for ur replay
sura's Avatar
Banned
use some functions like findminimum ,find maximum after all it is also a binary tree....................