有没有固定内存占用的树遍历算法？

Question

我有树的第一个节点。类似这样的东西：

class TreeNode {
   int uniqueValue;
   List<TreeNode> children;
}

我想找到最有效的内存方式来打印树的所有节点。树可能很大或者非常大。它可以很深也可以很宽。我知道带有递归和堆栈的算法。我想要找到的是独立于图形大小使用固定量内存的算法。

树不是二元树！

Answer 1

不存在这样的 O(1) 算法。最坏情况下的内存使用量始终为 O(N)。您可以通过添加字段来支持直接遍历到图节点来“作弊”。这样，如果您能够将图形加载到内存中，您就可以遍历它（使用 BFS 或 DFS）。

Answer 2

如果树恰好存储在类似堆的扁平流中，例如长括号列表，则遍历它只需要足够的内存来记录您在流中的位置，这需要 O(log(N)) 位。

当然，正如 Lior 所说，您可以使用 O(log(N)) 位的堆栈来深度优先遍历它。

如果你的树引用了宇宙中的每个粒子（例如 1e85），从技术上讲，你只需要，让我们看看 - 85 乘以 3.3 = 281 位 = 大约 35 个字节。 我想你可以处理这个问题。

Answer 3

如果您以某种方式在树上执行迷宫遍历，则需要 O(2m) = O(m) = O(n) （因为它是一棵树）时间和恒定的额外空间。假设您位于邻域为 N(v) 的顶点 v，并且您从 N(v) 中的顶点 u 到达。那么你只需要记住你来自于你。然后访问 v 的邻接表中的下一个顶点，N(v)。 同样，你只记得你来自哪里（以及你在哪里，但这是隐式给出的） 当您再次到达初始顶点并访问它的所有邻居时，您将终止。第一个顶点的邻接列表将告诉您它的第一个邻居是什么。您将多次打印一些顶点，但您可以轻松地重定向该输出并将其减少为不同的输出。 希望对您有帮助，如有遗漏请指正