Как получить / расширить рекурсивный класс

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 и реализовывать новый метод в производном классе. Но этот подход не работает для дерева.

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 ().

Может кто-нибудь предложить способ сделать это модульным способом без изменения реализации дерева. Это нормально, чтобы изменить, как это реализовано в целом, если вам не нужно менять его всякий раз, когда вы хотите расширить / извлечь из класса. Я могу увидеть возможный способ сделать это, сделав в шаблонном классе 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<T, NodeT> предлагает один и тот же интерфейс для всех NodeT и DerivedTree<T> наследуется от Tree<T, ...>.

Редактировать: Черт, потребовалось много усилий, чтобы предотвратить рекурсивное создание Tree<T, NodeType>.

Answer 2

Это приемлемо для вас?

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

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

Answer 5

Сделайте printInOrder функцию virtual и сделайте ее доступной в Tree.

Это означает, что дети дерева могут быть произвольными потомками Tree, и вызов printInOrder для них всегда вызовет переопределенную реализацию, если они предоставят ее.

Основным недостатком является то, что все методы должны быть объявлены в Tree.