1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

please help???

Discussion in 'C++' started by rawah, May 21, 2008.

  1. rawah

    rawah New Member

    Joined:
    Apr 23, 2008
    Messages:
    7
    Likes Received:
    0
    Trophy Points:
    0
    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
     
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,285
    Likes Received:
    364
    Trophy Points:
    83
    Can you please clarify which ADT and why you are looking for the function search?
     
  3. rawah

    rawah New Member

    Joined:
    Apr 23, 2008
    Messages:
    7
    Likes Received:
    0
    Trophy Points:
    0
    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 a moderator: May 22, 2008
  4. rawah

    rawah New Member

    Joined:
    Apr 23, 2008
    Messages:
    7
    Likes Received:
    0
    Trophy Points:
    0
    i use this struct

    struct employee
    {
    string name;
    int key;
    }
     
  5. rawah

    rawah New Member

    Joined:
    Apr 23, 2008
    Messages:
    7
    Likes Received:
    0
    Trophy Points:
    0
    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
     
  6. sura

    sura Banned

    Joined:
    Aug 4, 2011
    Messages:
    47
    Likes Received:
    1
    Trophy Points:
    0
    Location:
    India,Tamil Nadu.
    use some functions like findminimum ,find maximum after all it is also a binary tree....................
     

Share This Page