C++：分离分支节点和叶子节点的类？

Question

我正在制作一棵树（本质上是一个前缀树，但针对数字而非字符串），该树由数字元组的排序列表构建而成（(1,1,2),(1,2,5),(2,1,0)等），每个元组与单个标量值（int或double）相关联。由于树只建立一次，然后进行多次迭代/搜索，我计划使用std::vectors来保存每个节点的子节点。要搜索树，我只需要调用std::lower_bound在每个节点的_children向量上执行二进制搜索，该向量将包含每个节点及其相应键的std::pair。但是，底部节点必须包含一个向量，其中包含每个元组中最后一个条目及其相应值的对，因此必须与BranchNode类型不同。代码如下：

class GenNode
{
};

template<typename key_type,typename value_type>
class BranchNode : GenNode
{
    void insert(std::pair< std::vector<key_type> , value_type>);
private:
    std::vector< std::pair<key_type,GenNode*> > _children;
};

template<typename key_type,typename value_type>
class LeafNode : GenNode
{
private:
    std::vector< std::pair<key_type,value_type> > _children;
};

然而，这样做真的很丑陋，因为两个类都必须继承自无用的GenNode类，以便每个BranchNode的子节点可以是其他BranchNodes或LeafNodes...有更好的方法吗？

- Sam Manzer

---

一个 Node 在没有子节点的情况下是叶子节点，一旦添加了子节点，它就成为了分支节点。只需要拥有 Node 对象即可。 - Peter Wood

出于效率的原因，我不想这样做；我不希望叶节点具有空的_children向量，这些向量仍然可能存储“size = 0”和其他类似成员。 - Sam Manzer

在这篇博客文章的评论区中，有关于不同树实现方法的优点的讨论。链接：http://math.andrej.com/2009/04/11/on-programming-language-design/ - Heatsink

Answer 1

如果您想在同一个向量中存储两种类型的数据，那么这两种类需要有关联（一种继承自另一种或者都继承自共同的祖先类）。

拥有一个空的共同祖先类可能看起来不太好。但是如果将搜索操作（以及其他迭代/处理操作）作为虚方法放入基类中，并在BranchNode和LeafNode中实现它（实现会不同），则可以获得更优雅的设计。

在这种情况下，基类也应该是模板类。我的意思是像这样拥有一个基类：

template<typename key_type,typename value_type>
class GenNode {
 public:
  virtual value_type search(key_type key) = 0;
};

- nullptr

---

我最终采用了这种设计方法，将begin()和search()方法放在公共接口中。 - Sam Manzer

Answer 2

是的，你需要两种不同类型。事实上，像这样的(Leaf OR Node)被称为标签联合。

有几种实现方法，但在C++中，使用一个公共基类和两个派生类可能是最常见的。

另一个有趣的选择是使用boost::variant和递归包装器而不是使用公共基类。这特别有趣，因为它避免了使用指针（从而为您处理内存管理）。

- Konrad Rudolph

---

基类+派生类模式有时会代替区分联合使用，但它实际上并不是一个区分联合。区分联合的区别在于不能使用新变量扩展区分联合。换句话说，区分联合让您断言永远不会有非“Leaf”、非“Branch”树节点。类层次结构不能保证这一点，因为它们允许定义新的子类。 - Heatsink

@Heatsink 嗯，区分联合通过继承来实现。正如你所说，这种实现并不完美，但我仍然认为在这种情况下，你试图用它们来实现的是一个有效的区分联合。 - Konrad Rudolph