1

抽象「比較可能」クラスを作成する必要があります。このクラスを継承するすべてのクラスは、compare_to メソッドを実装します。

/* returns 1 if this class > rhs, 0 if equal, -1 if this class < rhs */    
int compare_to(const Comparable& rhs);

整数ではなく「比較可能な」オブジェクトを格納する二分探索ツリー クラスを作成します。

私が問題を抱えているのは、Binary Search Tree クラスがどのように見えるか、および Comparable オブジェクトをそこに格納する方法を理解することです。

テンプレートを使用できます。

4

2 に答える 2

1

これをしないでください。一般的なインターフェースを作成しないでください。これには多くの欠点があります。Int と String のように、IComparable から派生した 2 つのクラスが互いに比較できない場合はどうなるでしょうか。

テンプレートを使用できると言いました。それらを使用して、Comparator を 2 番目のテンプレート引数として指定します。

template <class T, class Comparator>
class BSTree  {
public:
   bool present(const T& value)
   {
       int res = comparator(value, root->value);
       switch(res) {
         case 0: return true;
         case -1: return find(root->left, value);
         case 1: return find(root->right, value);
       }
   }
private:
  struct Node {
  ...
  };
  Node* root;
  Comparator comparator;
};

典型的なコンパレータは次のとおりです。

template <class T>
class RawComparator {
public:
    int operator()(const T& l, const T& r) 
    {
       if (l < r) return -1;
       else if (l > r) return 1;
       else return 0;
    }

};

そしてintの二分探索木：

typedef BSTree<int, RawComparator<int>> BSTreeInt;
于 2012-10-11T22:08:34.503 に答える
0

二分探索木のクラステンプレートを作成する必要があると思います。クラステンプレートは次のようになります

template <typename Comparable>
class BSTNode
{
public:
BSTNode const Comparable & theElement = Comparable( ),BSTNode *lt = NULL, BSTNode *rt = NULL);
int size( BSTNode *t ) ;
int height( BSTNode *t);
void printPostorder( ) ; 
void printInOrder( ) ; 
void printPreOrder( ) ;
bool operator<(const Comparable&,const Comparable &); 
BSTNode *duplicate() ;


public:

Comparable element;
BSTNode *left;
BSTNode *right;

};

そして、オーバーロードして型オブジェクトoperator<の比較メソッドを追加できます。Comparable

于 2012-10-11T19:42:38.030 に答える