0

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

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

现在我的树结构的目标是：1）尽可能快地将一个分支从一棵树移动到另一棵树。2）每个分支都应该是一棵自己的树。并且在树上工作的动作也应该能够在分支上执行。

我所做的只是创建一个包含向量的类。- 向量内部是此类的其他对象。示例（我在这里只发布一个最小的示例，因为我现在面临的最大问题是该类太大而无法处理）：

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

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

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

4

2 回答 2

1

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

这个向量的end()迭代器就是空栈。

于 2012-01-17T15:07:46.943 回答
0

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

那么这里的问题更多是一个概念问题。

我总是用递归解决树结构中的CRUD功能。递归不需要知道子树的数量，这是启用O(log n)插入、查找和删除的功能之一。

插入示例：

 void insertNode(Node* &treeNode, Node *newNode) {
     if (treeNode) treeNode = newNode;
     else if (newNode->key < treeNode->key) insertNode(treeNode->left, newNode);
     else insertNode(treeNode->right, newNode);
 }

如果您需要知道树上有多少级别，只需转到左孩子直到 NULL。您可以O(log n)使用这些知识轻松计算出计算树中孩子数量的算法。

树是为递归访问而设计的。如果您想要非递归访问，也许树不是您想要的？- 该结构将保存哪些数据，访问频率如何？

于 2012-01-17T15:22:43.970 回答