c++ - 空对象模式和函数

Question

我正在尝试为树遍历实现空对象模式。现在它看起来像这样，这是行不通的。我该如何实现？谢谢。

struct Node
{
    Node *_left;
    Node *_right;

    string _value;
};

struct Sentinel : Node
{
    static Sentinel Stop;
    typedef Node NodeType;
};

Sentinel Sentinel::Stop;

template<class T>
auto traverse(T *root) -> decltype(typedef T::NodeType, void)
{
    cout << "sentinel" << endl;
}

template<class T>
void traverse(T *root, ...)
{
    traverse(root->_left);
    traverse(root->_right);
}

int _tmain(int argc, _TCHAR* argv[])
{
    Node rightLeft{ &Sentinel::Stop, &Sentinel::Stop, "rightLeft" };
    Node left{ &Sentinel::Stop, &Sentinel::Stop, "left" };
    Node right{ &rightLeft, &Sentinel::Stop, "right" };
    Node root{ &left, &right, "root" };
    traverse(&root);

    return 0;
}

编辑:它进入永无止境的递归。

Answer 1

按照WikipediA提供的教科书实现，你想做的大概是:

#include <iostream>
#include <string>
class Node {
  Node *left_;
  Node *right_;
  std::string value_;

  public:
  Node() = default;
  Node(Node* left, Node* right, std::string const& value) : left_(left), right_(right), value_(value) {}

  virtual void traverse() const {
    std::cout << value_ << std::endl;
    left_->traverse();
    right_->traverse();
  }
};

struct Sentinel : Node {
  Sentinel() = default;
  void traverse() const { std::cout << "sentinel" << std::endl; }
};

static Sentinel Stop;

int main(int argc, char const *argv[])
{

  Node rightLeft{&Stop, &Stop, "rightLeft"};
  Node left{&Stop, &Stop, "left"};
  Node right{&rightLeft, &Stop, "right"};
  Node root{&left, &right, "root"};

  root.traverse();

  return 0;
}