3

这是 对二叉树的列表实现是否可扩展？

使用线性数组（stl向量）或stl deque完成树实现的优点或缺点是什么

而不是一个具有左右指针的单个节点的二叉树？

假设：树将被预先计算并且一旦构建就不会被修改，并且只会用于搜索。

4

2 回答 2

2

好吧，我会说它是这样的：

  • 使用指针树，您将内存用于数据和指向数据的指针，而您只为数据std::vector分配内存（容器处理自身的迭代）
  • 如果你使用std::vector，你的记忆是本地化的。例如，如果你想访问一棵树的单个完整级别，这将在内存中是连续的，而单独分配的各个节点，你会像兔子一样跳过内存访问所有这些
  • 如果您分配单个节点，您实际上无法分配它们，除非单独分配。这意味着对malloc-euqivalent 函数的大量调用。（在C中有一些技巧可以用来避免这种情况，它们仍然可以C++在std::vector.
  • 创建向量时，您可以使用它std::vector.reserve()来预分配所有内存。此外，如果您知道向量是如何操作的，您就会知道它会在malloc每次启动树的新级别时调用 -equivalent 来保留内存 - 分配的数量应该大致等于树中的级别数
  • 访问向量的元素非常简单，在基于向量的完全填充的二叉树中导航非常直观且易于使用
于 2012-05-23T08:30:23.247 回答
2

数组（包括std::vector）提供了良好的引用局部性并节省了一些空间，因为它们将数据保存在一个连续的块中，而指针树可能会将其节点分散在整个内存中并产生分配器开销。

对于预先计算的树，最好将其存储在vector. 使用二叉堆常用的布局可以非常有效地存储完整（或接近完整）的二叉树。

（可以通过选择一个好的分配器来避免树中的开销，但是 C++ 标准库只提供了一个通用的分配器。）

于 2012-05-23T08:33:41.320 回答