How to derive from/extend a recursive class

I have a recursive class, a kind of tree, that has instances of itself as member variables. For example:

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

If I want to add a method that prints all the values using an in-order traversal, I could do this:

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

But what if, for various reasons, I couldn't or didn't want to change Tree's implementation? If the class wasn't recursive, i.e. didn't contain instances of itself, I could just derive from Tree and implement a new method in the derived class. But this approach doesn't work for 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 and rightChild are instances of Tree and thus don't have a printInOrder() method.

Can anyone suggest a way to do this in a modular way without changing Tree's implementation. It's ok to change how it is implemented in general, as long as you don't have to change it whenever you want to extend/derive from the class. I can see a possible way to do it 开发者_如何学Pythonby making the template class T have methods to do the things I want, but that just seems ugly. There must be a better way.

I'm perfectly happy for someone to point out how I've overlooked something obvious. It certainly feels like I have.

Edit: The point is not how to implement printInOrder(). That was just an example. The point is how to derive a class so that the children are also the derived class.

---

Template on the node type.

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>*.
};

This works based on two invariants- that Tree<T, NodeT> offers the same interface for all NodeT, and that DerivedTree<T> inherits from Tree<T, ...>.

Edit: Damn, that took a lot of effort to prevent recursive instantiation of Tree<T, NodeType>.

---

Make printInOrder a virtual function and make it available in Tree.

This means tree chilren can be arbitrary descendents of Tree and calling printInOrder on them will always invoke the overriden implementation, if they provide any.

The major downside is that all methods need to be declared in Tree.

---

If you want non-intrusive printing, just specify a plain template function for it:

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

You obviously need a TreePrinter as a friend though:

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>&);
};

Alternatively if you don't to have it as a friend, provide accessors to get the value as well as the left and right nodes of the tree.

---

Is it acceptable for you?

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

---

You can simply write a member function that takes the instance to print:

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

Use this in a zero-parameter overload:

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