c++ - 创建树数据结构 - 不同的方法

Question

过去我问过很多关于树数据结构的问题，但我似乎没有以 C++ 的正确方式处理它。

在我编写数据结构的方式中，我想不出一种关于如何拥有“结束”或“开始”迭代器的方式。因此，我采用了将所有功能都包含为成员方法的方法。而不是使用迭代器和算法的标准方法。

现在我的树结构的目标是:1) 尽可能快地将一个分支从一棵树移动到另一棵树。 2)每个分支都应该是一棵独立的树。在树上工作的 Action 也应该能够在分支上执行。

我所做的只是创建一个类，其中包含一个 vector 。 - vector 内部是此类的其他对象。示例(我在这里只发布了一个最小的示例，因为我现在面临的最大问题是类太大而无法处理):

template <typename ValTy>
class Tree {
private:
    std::vector<std::unique_ptr<Tree> > subtrees;
    ValTy value;
};

正如您看到的那样，我可以从 subtrees 中取出一些东西 - 并将其用作树或复制它。 然而，由于顶级树没有指示有多少子树(或多少层)，所以不可能声明“结束迭代器”？像 std::find() 这样的算法不会遍历整个树(及其所有子树)吗？

是否有可能利用这些算法，同时仍然保持易于“分支”的结构？

Answer 1

您可以通过保留一堆子树 vector 的迭代器对来迭代这样的树。这种 vector 的增量意味着最顶层子树迭代器的增量，如果最底端的迭代器在其末尾，则随后进行清理。

此 vector 的 end() 迭代器将只是空堆栈。