algorithm - 在通用数据结构方面，如何高效地列出树数据结构中节点下的所有叶子？

Question

一段时间以来，我一直在想并寻找这个问题的答案:如何高效地(具体在时间上)列出树数据结构中某个节点下的所有叶子？

我一开始以为可以用一个链表来完成，该链表连接该节点下的所有叶子。

如果这是可能的，那么我们可以在 O(n) 的线性时间内遍历子树下的叶子，其中 n 是该子树下的叶子数。

但是，考虑到每个子树都需要有不同的链表，这听起来不切实际。

所以，如果有人能指出是否可能，我将不胜感激，为什么？

在这种情况下，让我们考虑一个简单的二叉树。

问候

Answer 1

B+ Tree允许叶子之间的指针(下一个，上一个)。假设您的所有数据都存储在叶级别，那么 B+ 树可能是完成您的要求的最佳方式。

如果您要问，只有具有公共(public)根节点(不是整棵树的根)的叶子节点，您可以只找到该根下最左边的节点，然后继续点击“下一个”链接，直到您点击值大于根节点右节点的叶节点。