C ++ overload operator <with int parameter (versus type which is not guaranteed to be int)
I want to overload the <and> operators to allow searching for an int value inside a BST (which is not meant to hold int, but rather words).
For anyone wondering why this overload is done in the first place, please check out C ++. I am stuck filling this BST with its correct values
I need two search functions to fill in the words of the dictionary correctly and then identify its synonyms / antonyms.
This is the search function:
//--- Definition of findId() template <typename DataType> DataType& BST<DataType>::findId(const int id ) const { typename BST<DataType>::BinNodePointer locptr = myRoot; typename BST<DataType>::BinNodePointer parent =0; bool found = false; while (!found && locptr != 0) { if (locptr->data > id) // descend left locptr = locptr->left; else if (locptr->data < id) // descend right locptr = locptr->right; else // item found found = true; } return found ? locptr->data : NULL; }
And my attempt so far ..
template <typename DataType> bool BST<DataType>::operator >(const int anotherId)const { typename BST<DataType>::BinNodePointer locptr; //undefined pointer, what should I make it point at? return (locptr->data > anotherId); }
The whole template:
#include <iostream> #include <iomanip> #include <stdlib.h> #ifndef BINARY_SEARCH_TREE #define BINARY_SEARCH_TREE template <typename DataType> class BST { public: /***** Function Members *****/ BST(); bool empty() const; DataType& findId (const int id)const; bool operator >(const int anotherId)const; bool operator < (const int anotherId)const; bool search(const DataType & item) const; void insert(const DataType & item); void remove(const DataType & item); void inorder(std::ostream & out) const; void graph(std::ostream & out) const; private: /***** Node class *****/ class BinNode { public: DataType data; BinNode * left; BinNode * right; // BinNode constructors // Default -- data part is default DataType value; both links are null. BinNode() : left(0), right(0) {} // Explicit Value -- data part contains item; both links are null. BinNode(DataType item) : data(item), left(0), right(0) {} }; //end inner class typedef BinNode * BinNodePointer; /***** Private Function Members *****/ void search2(const DataType & item, bool & found, BinNodePointer & locptr, BinNodePointer & parent) const; /*------------------------------------------------------------------------ Locate a node containing item and its parent. Precondition: None. Postcondition: locptr points to node containing item or is null if not found, and parent points to its parent.#include <iostream> ------------------------------------------------------------------------*/ void inorderAux(std::ostream & out, BST<DataType>::BinNodePointer subtreePtr) const; /*------------------------------------------------------------------------ Inorder traversal auxiliary function. Precondition: ostream out is open; subtreePtr points to a subtree of this BST. Postcondition: Subtree with root pointed to by subtreePtr has been output to out. ------------------------------------------------------------------------*/ void graphAux(std::ostream & out, int indent, BST<DataType>::BinNodePointer subtreeRoot) const; /*------------------------------------------------------------------------ Graph auxiliary function. Precondition: ostream out is open; subtreePtr points to a subtree of this BST. Postcondition: Graphical representation of subtree with root pointed to by subtreePtr has been output to out, indented indent spaces. ------------------------------------------------------------------------*/ /***** Data Members *****/ BinNodePointer myRoot; }; // end of class template declaration //--- Definition of constructor template <typename DataType> inline BST<DataType>::BST() : myRoot(0) {} //--- Definition of empty() template <typename DataType> inline bool BST<DataType>::empty() const { return myRoot == 0; } //--- Definition of findId() template <typename DataType> DataType& BST<DataType>::findId(const int id ) const { typename BST<DataType>::BinNodePointer locptr = myRoot; typename BST<DataType>::BinNodePointer parent =0; bool found = false; while (!found && locptr != 0) { if (locptr->data > id) // descend left locptr = locptr->left; else if (locptr->data < id) // descend right locptr = locptr->right; else // item found found = true; } return found ? locptr->data : NULL; } template <typename DataType> bool BST<DataType>::operator >(const int anotherId)const { typename BST<DataType>::BinNodePointer locptr; return (locptr->data > anotherId); } template <typename DataType> bool BST<DataType>::operator < (const int anotherId)const { typename BST<DataType>::BinNodePointer locptr; return (locptr->data < anotherId); } //--- Definition of search() template <typename DataType> bool BST<DataType>::search(const DataType & item) const { typename BST<DataType>::BinNodePointer locptr = myRoot; typename BST<DataType>::BinNodePointer parent =0; /* BST<DataType>::BinNodePointer locptr = myRoot; parent = 0; */ //falta el typename en la declaracion original bool found = false; while (!found && locptr != 0) { if (item < locptr->data) // descend left locptr = locptr->left; else if (locptr->data < item) // descend right locptr = locptr->right; else // item found found = true; } return found; } //--- Definition of insert() template <typename DataType> inline void BST<DataType>::insert(const DataType & item) { typename BST<DataType>::BinNodePointer locptr = myRoot, // search pointer parent = 0; // pointer to parent of current node bool found = false; // indicates if item already in BST while (!found && locptr != 0) { parent = locptr; if (item < locptr->data) // descend left locptr = locptr->left; else if (locptr->data < item) // descend right locptr = locptr->right; else // item found found = true; } if (!found) { // construct node containing item locptr = new typename BST<DataType>::BinNode(item); if (parent == 0) // empty tree myRoot = locptr; else if (item < parent->data ) // insert to left of parent parent->left = locptr; else // insert to right of parent parent->right = locptr; } else std::cout << "Item already in the tree\n"; } //--- Definition of remove() template <typename DataType> void BST<DataType>::remove(const DataType & item) { bool found; // signals if item is found typename BST<DataType>::BinNodePointer x, // points to node to be deleted parent; // " " parent of x and xSucc search2(item, found, x, parent); if (!found) { std::cout << "Item not in the BST\n"; return; } //else if (x->left != 0 && x->right != 0) { // node has 2 children // Find x inorder successor and its parent typename BST<DataType>::BinNodePointer xSucc = x->right; parent = x; while (xSucc->left != 0) // descend left { parent = xSucc; xSucc = xSucc->left; } // Move contents of xSucc to x and change x // to point to successor, which will be removed. x->data = xSucc->data; x = xSucc; } // end if node has 2 children // Now proceed with case where node has 0 or 2 child typename BST<DataType>::BinNodePointer subtree = x->left; // pointer to a subtree of x if (subtree == 0) subtree = x->right; if (parent == 0) // root being removed myRoot = subtree; else if (parent->left == x) // left child of parent parent->left = subtree; else // right child of parent parent->right = subtree; delete x; } //--- Definition of inorder() template <typename DataType> inline void BST<DataType>::inorder(std::ostream & out) const { inorderAux(out, myRoot); } //--- Definition of graph() template <typename DataType> inline void BST<DataType>::graph(std::ostream & out) const { graphAux(out, 0, myRoot); } //--- Definition of search2() template <typename DataType> void BST<DataType>::search2(const DataType & item, bool & found, BST<DataType>::BinNodePointer & locptr, BST<DataType>::BinNodePointer & parent) const { locptr = myRoot; parent = 0; found = false; while (!found && locptr != 0) { if (item < locptr->data) // descend left { parent = locptr; locptr = locptr->left; } else if (locptr->data < item) // descend right { parent = locptr; locptr = locptr->right; } else // item found found = true; } } //--- Definition of inorderAux() template <typename DataType> void BST<DataType>::inorderAux(std::ostream & out, BST<DataType>::BinNodePointer subtreeRoot) const { if (subtreeRoot != 0) { inorderAux(out, subtreeRoot->left); // L operation out << subtreeRoot->data << " "; // V operation inorderAux(out, subtreeRoot->right); // R operation } } //--- Definition of graphAux() template <typename DataType> void BST<DataType>::graphAux(std::ostream & out, int indent, BST<DataType>::BinNodePointer subtreeRoot) const { if (subtreeRoot != 0) { graphAux(out, indent + 8, subtreeRoot->right); out << std::setw(indent) << " " << subtreeRoot->data << std::endl; graphAux(out, indent + 8, subtreeRoot->left); } } #endif
+1
source share
3 answers
I'm not really sure why you want to overload> and <in this case, but maybe I don't quite understand the question. It sounds like you intend to have several different types of tree nodes, all of which inherit from DataType
. If so, just add a const member function to the base class DataType
:
class DataType { private: mutable int internalID; // ... public: const int id() const { return internalID; } // ... virtual ~DataType(); };
Now, in your loop findID
, you can simply use:
while (!found && locptr != 0) { if (locptr->data.id() > id) { locptr = locptr->left; } else if (locptr->data.id() < id) { locptr = locptr->right; } else { found = true; } }
And you don't have to go through all the unnecessary operator overloading issues.
+1
source share
Operator overloading really doesn't make sense here.
Member function
bool BST<DataType>::operator >(const int anotherId)const;
Basically, this means comparing an entire tree to an int, which is not what I think your goal is. You can make sure that you have <defined for the datatype and then also add something like
template<typename type> friend bool operator>(const BST<type>::node&, BST<type>::const node&);
My two cents at least.
+1
source share