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
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
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
use some functions like findminimum ,find maximum after all it is also a binary tree....................
