具有不同元素的 C++ n 叉树

Question

我想从文档构建一棵 n-arry 树。为此，我有 3 种不同类型的树元素：

结构节点
- 有名字
- 可以包含其他节点
- 深度
元素节点（树叶）
- 有钥匙
- 有价值
- 深度
元素模板节点（树叶）
- 有一个占位符应该稍后在程序中解决
- 深度

此刻我在想这样的事情：


class Node {
    public:
        Node(int depth);
        int depth() const;
    private:
        int depth_;
};

class StructNode : public Node {
    ...
    private:
        std::vector<std::unique_ptr<Node>> children;
};

class ElementNode : public Node {
...
};

class ElementTemplateNode : public Node {
...
};

树将在启动时从文件生成，并重新用于创建如下输出字符串：

Structname:
   key = value
   key = value
   Structname:
       key = value
   Structname:
       key = value
...

其中Key和value直接从ElementNode读取或者从另一个文件读取ElementTemplateNode

里面的placeholder的值

是否有更好的树结构？因为对于当前版本，我必须首先检查它是 StructNode、ElementNode 还是 ElementTemplateNode

Answer 1

这是实现具有不同类型节点的树的典型结构。另一个变体是 composite pattern.

你描述的问题，通常是由于询问节点他们知道什么，而不是告诉他们做什么。如果你反过来做 (tell, don't ask)，你可以摆脱这些检查并从多态性中受益。

不同类型的节点继承自 Node。您可以使用统一接口设计树，为 Node 定义虚函数，然后可以为不同类型的节点覆盖这些虚函数。然后调用该方法会做正确的事情，而不需要手动类型检查。要生成输出字符串，您需要告诉根节点生成一个字符串。如果它是一个结构，它会添加标题并告诉它的 children 生成一个字符串，但如果它是一个叶子，它只会将 key/value 对添加到字符串中。无需从外部了解每个节点的任何信息。

如果探索树的操作不应该由树本身来实现，通常的做法是使用visitor pattern。最大的优点是您只需编写一次访问者，然后就可以轻松地为不同的算法专门化一种新的访问者。同样，无需检查节点的类型。该模式确保为正确类型的节点调用正确的初等函数。

具有不同元素的 C++ n 叉树

C++ n-arry tree with different elements

c++

data-structures