Сопоставимый класс и дерево двоичного поиска
Мне нужно создать абстрактный класс «Comparable». Любой класс, который наследуется от этого класса, будет реализовывать метод 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, в котором хранятся «сопоставимые» объекты, а не целые числа.
У меня проблемы с пониманием того, как будет выглядеть класс Binary Search Tree и как мы можем хранить в нем сопоставимые объекты.
Мы можем использовать шаблоны.
Решение
Не делай этого, не делай никакого общего интерфейса. Это имеет много недостатков. Что, если два класса, производные от IComparable, не сопоставимы друг с другом — как Int и String?
Вы сказали, что можете использовать шаблоны. Используйте их — и предоставьте Comparator в качестве второго аргумента шаблона:
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;
Другие решения
Я считаю, что вам придется создать шаблон класса для дерева двоичного поиска.
шаблон класса будет выглядеть примерно так
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 Тип объектов.