如何派生/扩展递归类

Question

我有一个递归类，一种树，它具有自身的实例作为成员变量。例如：

template<class T>
class Tree {
public: 
  /* Constructors, etc. */
protected:
  T m_value;
  Tree<T> *leftChild;
  Tree<T> *rightChild;
};

如果我想添加一个使用中序遍历打印所有值的方法，我可以这样做：

template <class T>
void Tree<T>::printInOrder()
{
   leftChild->printInOrder();
   std::cout << m_value << std::endl;
   rightChild->printInOrder();
}

但是，如果由于各种原因，我不能或不想更改 Tree 的实现怎么办？如果该类不是递归的，即不包含其自身的实例，我可以从 Tree 派生并在派生类中实现一个新方法。但这种方法对 Tree 不起作用。

template <class T>
class DerivedClass : public Tree<T> {
public:
  void printInOrder();
}

template <class T>
void DerivedClass<T>::
printInOrder()
{
   this->leftChild->printInOrder();
   std::cout << this->m_value << std::endl;
   this->rightChild->printInOrder();
}

leftChild 和 rightChild 是 Tree 的实例，因此没有 printInOrder() 方法。

任何人都可以建议一种在不改变 Tree 实现的情况下以模块化方式执行此操作的方法。一般来说，改变它的实现方式是可以的，只要你想从类扩展/派生时不必改变它。我可以看到一种可能的方法，通过使模板类 T 具有执行我想要的操作的方法，但这看起来很难看。一定有更好的方法。

我非常高兴有人指出我如何忽略了一些明显的事情。我确实有这样的感觉。

编辑：重点不在于如何实现 printInOrder()。这只是一个例子。重点是如何派生一个类，使子类也是派生类。

Answer 1

节点类型上的模板。

template<typename T, typename NodeType = void> class Tree {
    NodeType node;
    T m_data;
};
template<typename T> class Tree<void> {
    struct Node {
        Tree<T, void>* left;
        Tree<T, void>* right;
    };
    Node node;
    T m_data;
};
template<typename T> struct DerivedNode {
     DerivedTree<T>* left;
     DerivedTree<T>* right;
};
template<typename T> class DerivedTree : public Tree<T, DerivedNode<T>> {
     // now left and right are of type DerivedTree<T>*.
};

这基于两个不变量 - Tree 为所有 NodeT 提供相同的接口，并且 DerivedTree 继承来自 Tree。

编辑：该死，花了很多精力来防止 Tree的递归实例化。

Answer 2

将 printInOrder 设为 virtual 函数并使其在 Tree 中可用。

这意味着树子级可以是 Tree 的任意后代，并且对它们调用 printInOrder 将始终调用重写的实现（如果它们提供了任何实现）。

主要缺点是所有方法都需要在 Tree 中声明。

Answer 3

如果您想要非侵入式打印，只需为其指定一个简单的模板函数：

template <typename T>
void TreePrinter(const Tree<T>& tree)
{
    TreePrinter(tree.leftChild);
    std::cout << tree.m_value << std::endl;
    TreePrinter(tree.rightChild);
}

不过，您显然需要一个 TreePrinter 作为朋友：

template<class T>
class Tree {
public: 
  /* Constructors, etc. */
protected:
  T m_value;
  Tree<T> *leftChild;
  Tree<T> *rightChild;

  friend template <typename U>
  TreePrinter(const Tree<U>&);
};

或者，如果您不希望将其作为朋友，请提供访问器来获取值以及树的左节点和右节点。

Answer 4

您可以接受吗？

template <class T>void DerivedClass<T>::printInOrder()
{   
    ((DerivedClass<T>*)leftChild)->printInOrder();   
    std::cout << this->m_value << std::endl;   
    ((DerivedClass<T>*)rightChild)->printInOrder();
}

Answer 5

您可以简单地编写一个接受实例进行打印的成员函数：

template <class T>
void DerivedClass::printInOrderHelper(const Tree<T>& tree)
{
    printInOrderHelper(tree->leftChild);
    std::cout << tree->m_value << std::endl;
    printInOrderHelper(tree->rightChild);
}

在零参数重载中使用它：

template <class T>
void DerivedClass::printInOrder()
{
    printInOrderHelper(*this);
}