Блог

Я должен реализовать красное / черное дерево (RBTree) в C , наследуя от класса бинарного дерева поиска (BSTree), который я уже создал.

Класс BSTree содержит указатель узла (Node — это класс, который я создал для BSTree) на корень дерева.

Я хочу создать подкласс узла с именем «RBTNode», который содержит атрибут color и связанные методы (поэтому RBTNode является подклассом Node), затем я хочу создать класс RBTree, наследующий от BSTree, но с новым RBTNode вместо стандартного узла.

Структура будет следующей:

• BSTree содержит узел;
• RBTNode является подклассом узла;
• RBTree является подклассом BSTree;
• RBTree содержит RBTNode;

Как я мог этого добиться?

Как было предложено Jarod42 в комментариях, вы можете добиться этого, сделав тип узла параметром шаблона для BSTree класса.

Допустим, у вас есть эти два класса узлов:

 template<typename KeyT>
class BSNode {
public:
    KeyT key;
    // ...
};

template<typename KeyT>
class RBNode : public BSNode<KeyT> {
public:
    bool color;
};
 

Затем вы можете добавить параметр шаблона типа узла BSTree и сделать его BSNode по умолчанию. Затем вы можете использовать RBNode во время наследования RBTree .

 template <typename KeyT, typename NodeT = BSNode<KeyT>>
class BSTree {
protected:
    NodeT *root;
};

template <typename KeyT>
class RBTree : public BSTree<KeyT, RBNode<KeyT>> {
    // root will be of type RBNode<KeyT>* here
};