Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/forums/cpp/)
-   -   please help??? (http://www.go4expert.com/forums/please-help-t10691/)

rawah 21May2008 21:20

please help???
 
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 22May2008 08:26

Re: please help???
 
Can you please clarify which ADT and why you are looking for the function search?

rawah 22May2008 21:55

Re: please help???
 
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

rawah 22May2008 22:18

Re: please help???
 
i use this struct

struct employee
{
string name;
int key;
}

rawah 24May2008 20:41

Re: please help???
 
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 27Oct2011 05:06

Re: please help???
 
use some functions like findminimum ,find maximum after all it is also a binary tree....................


All times are GMT +5.5. The time now is 16:06.