c++ - 具有X类，如何将X作为模板参数传递给自身？

Question

我正在尝试实现从BS树继承的红黑树。 BST使用BSNode作为其节点，而RBT(红黑树)使用RBNode，后者又继承自BSNode。代码看起来像这样，问题出现在代码中:

#include <iostream>

#define _BST BST<K, T, RBNode<K, T>>

// attempt 1
//template <typename K, typename T, typename NODE>
//class BSNode
//{
//
//public:
//
//  K key;
//  T value;
//
//  NODE* left;
//  NODE* right;
//
//  // ...
//};

// attempt 2
template <typename K, typename T, template<typename, typename> typename NODE>
class BSNode
{

public:

    K key;
    T value;

    NODE<K, T>* left;
    NODE<K, T>* right;

    // ...
};

template <typename K, typename T>
class RBNode : public BSNode<K, T, RBNode>
{

public:

    bool color;

    // ...
};

template <typename K, typename T, typename NODE>
class BST
{

public:

    NODE* root = nullptr;

    // ...
};

template <typename K, typename T>
class RBT : public _BST
{
    // ...
};

int main()
{
    RBT<int, int> rbt;

    // attempt 1
    // recursive and can't be done.
    // BST<int, int, BSNode<int, int, BSNode<int, int, BSNode<int.....

    // attempt 2
    // template arguments list for NODE takes
    // 2 arguments while BSNode takes 3. Not compatible.
    // BST<int, int, BSNode<int, int, BSNode>>
}

问题:
1-
如何实现它，以便BST只是写为BST<int, int>，同时仍然让它接受左右不同类型的节点(例如RBNode)？
2-
如何让RBNode从BSNode继承，同时能够创建BST和RBT？
3-
在尝试2中，在宏#define _BST BST<K, T, RBNode<K, T>>中，为什么将其写为#define _BST BST<K, T, RBNode>时出现错误？在BSNode类中，定义了left和right
作为NODE<K, T>*。这意味着用NODE替换BSNode<K, T>将导致left和
等于BSNode<K, T><K, T>*。为什么这是正确的方法？
设计是否有问题，或者是否可以改进？

Answer 1

您需要将Node和Tree与特定的BSNode，RBNode，BSTree和RBTree类型分开

template <typename K, typename T, template<typename, typename> typename NODE>
struct Node
{
    K key;
    T value;

    NODE<K, T>* left;
    NODE<K, T>* right;

    // ...
};

template <typename K, typename T>
struct BSNode : Node<K, T, BSNode>
{};

template <typename K, typename T>
struct RBNode : Node<K, T, RBNode>
{
    bool color;

    // ...
};

template <typename NODE>
struct Tree
{
    NODE* root = nullptr;

    // ...
};

template <typename K, typename T>
struct BSTree : Tree<BSNode<K, T>>
{
    // ...
};

template <typename K, typename T>
struct RBTree : Tree<RBNode<K, T>>
{
    // ...
};

撇开:如果要制作所有的public，则最好使用struct而不是class。默认情况下唯一的区别是public。