有没有一种具有固定内存使用量的树遍历算法？

Question

我有树的第一个节点。就像这样:

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

我希望找到一种最节省内存的方法来打印树的所有节点。树可能很大，甚至非常大。它可以是深度或宽度优先遍历。我知道有使用递归和使用栈的算法。我想要找到一种使用固定内存量的算法，与图形大小无关。

这个树不是二叉树！

- Pavel Vyazankin

---

时间复杂度有哪些限制？此外，可以在TreeNode类中添加额外的指针吗？ - Abhishek Bansal

顺序重要吗？您可以向每个节点添加布尔标志，以将其标记为已打印吗？您是否关心它需要O(n^2)的时间？树真的很深吗，以至于普通递归深度优先遍历会导致堆栈溢出？ - Jim Mischel

如果您可以遍历树到最深层，打印节点并删除它(!)，然后从顶部重新开始，那么您拥有一个非常低效的算法 - 但它不使用额外的内存。这是一种智力锻炼，还是您正在寻找一个有用的答案？如果树适合内存，则应该可以通过递归来实现（堆栈不深于树的最深层）。 - Floris

Floris，谢谢！你的想法对我的产品没有帮助，但很棒，因为它真正使用了常量内存空间。 - Pavel Vyazankin

Answer 1

没有O(1)算法。在最坏情况下，内存使用总是O(N)。您可以通过向支持直接遍历图节点的字段添加来“欺骗”算法。这样，如果您能够将图加载到内存中，就可以使用BFS或DFS遍历它。

- bobah

---

@MooingDuck，没错，但如果树不平衡，则深度为O(n)。 - ile

@ile：我不确定是否应该将随机树称为O(n)，“随机”树仍然非常接近于O(log(n))，但是最坏情况肯定是O(n)。 - Mooing Duck

@MooingDuck你错了，随机树的深度接近于O(√N)。 - Vikram Bhat

@VikramBhat：有趣，我以前从未听过这个。 （我假设sqrt仅适用于二叉树，但您的观点可以推广，因此您的观点站得住脚）你有来源吗？ （除了我记得听到的内容之外，我没有我的来源）。 我得查一下。 - Mooing Duck

@MooingDuck - O(N)最坏情况的一个例子：*-*-*-*-*，请用O(log(n))完成它 :) - bobah

Answer 2

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

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

如果您的树引用了宇宙中的每个粒子（比如1e85），从技术上讲，您只需要，让我们看看 - 85乘以3.3 = 281位=约35字节。我假设您可以处理它。

- Mike Dunlavey