一段时间以来，我一直在想并寻找这个问题的答案，即：如何有效地（具体地在时间方面）列出树数据结构中节点下的所有叶子？
我最初认为可以通过连接该节点下所有叶子的链表来完成。
如果这是可能的，那么我们可以在 O(n) 的线性时间内遍历子树下的叶子，其中 n 是该子树下的叶子数。
但是，考虑到每个子树都需要有不同的链表，这听起来不切实际。
所以，如果有人能指出它是否可能，我将不胜感激，为什么？
在这种情况下，让我们考虑一个简单的二叉树。
问候
问问题
120 次
4 回答
1
B+ 树允许叶子之间的指针（下一个，上一个）。假设您的所有数据都存储在叶级别，那么 B+ 树可能是完成您的要求的最佳方式。
如果您要问，只有具有公共根节点（而不是整个树的根）的叶子节点，您可以找到该根下最左边的节点并继续关注“下一个”链接，直到您点击一个叶子节点 whos值大于根节点的右节点。
于 2013-02-17T13:54:02.800 回答
0
好吧，在没有特殊功能的通用树中（每个节点只有有效负载索引和指向子树的指针），您必须遍历整个子树，至少第一次没有其他方法
如果您需要使用快速方法再次访问这些叶子节点，您可以设置一个指针向量/数组，这几乎可以为您提供 O(1) 时间访问，但您必须管理指针，以便在插入新节点时你不再引用旧叶子而是新叶子
如果您需要与多个子树相对应的叶子，那么在正常情况下，一个简单快速的解决方案可能是一个多维数组（在这种情况下为 2D），但如果您的数据集非常大或内存有限（在这种情况下，您可能想要交换到对您的需求更友好的 B+Tree）
于 2013-02-17T13:53:35.140 回答
0
这根本不是不切实际的。
您可以为每个叶子设置“下一个”叶子，然后在每个节点中只存储一个指向第一个（或最小）叶子和最后一个叶子（最大叶子）的指针
然后您可以从每个节点（子树）到达第一个叶子并遍历叶子。
第一个和最后一个叶子可以在插入时更新，复杂度为 O(logn)。
于 2013-02-17T13:45:38.520 回答
0
速度和内存大小始终是一个权衡。
科学中有数百种不同的尝试。但是所有这些额外的指针或列表等都需要额外的内存。
当速度问题在大多数情况下不是树时，这对于通用解决方案是不切实际的。
如果您需要一个非常特殊的树，对于想要列出树节点下所有叶子的特定应用程序，那么当您想要比简单地迭代左右子树更快的东西时，您将不得不使用专门的实现，我认为合理的快。
还有谁想知道所有子节点的叶子？
这是树的内部主题，从外部你甚至不应该知道节点下面是什么。（想想平衡的树，改变它们的结构）。
于 2013-02-17T14:18:18.487 回答