C++ 重载运算符 < 带有 int 参数(与不保证为 int 的类型相比)

Question

我想重载运算符 < 和 > 以允许在 BST 中搜索 int 值(它不是设计用于存储 int 而是单词)。

对于那些想知道为什么首先要完成此重载的人，请查看 C++ I'm stuck filling this BST with its proper values

我需要两个搜索功能才能正确填写词典中的单词，然后定义其同义词/反义词。

这是搜索功能:

//--- 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;
     //undefined pointer, what should I make it point at?         

     return (locptr->data > anotherId);

} 

整个模板:

#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's 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

Answer 1

我不太清楚为什么要在这种情况下重载 > 和 <，但也许我不太明白这个问题。看起来您打算拥有几种不同类型的树节点，所有这些节点都继承自 DataType。如果是这种情况，只需将 const 成员函数添加到 DataType 基类:

class DataType
{
    private:
        mutable int internalID;
        // ...
    public:
        const int id() const { return internalID; }
        // ...
        virtual ~DataType();
};

现在，在您的 findID 循环中，您可以简单地使用:

while (!found && locptr != 0)
{
    if (locptr->data.id() > id)
    {
        locptr = locptr->left;
    }
    else if (locptr->data.id() < id)
    {
        locptr = locptr->right;
    }
    else
    {
        found = true;
    }
}

而且您不必经历所有不必要的运算符重载麻烦。