树的遍历时间复杂度是什么？

Question

二叉树遍历的时间复杂度是什么？我确信这很显然，但我的脑袋目前无法理清。

- new299

---

这是《编程之美》第一卷第326页的内容，涉及线性算法。 - new299

那是 Knuth 的《计算机程序设计艺术》吗？我正在寻找这本书，以便为朋友提供一个好的例子，说明 n 叉树是线性的。 - Nicholas

是的，Knuth的《计算机程序设计艺术》。 - new299

Answer 1

这取决于你执行的遍历类型和算法，但通常情况下，它将是O(n)，其中n是树中节点的总数。深度优先遍历的经典递归实现会按照最深层级的顺序在堆栈上消耗内存，在平衡树上，最深层级的深度为log(n)。

- Uri

---

这对于n元树是正确的吗？我有一个最大深度为4的树形数据结构，我的朋友正在使用3个for循环来遍历它，并且他说他的算法的运行时间是O(n^3)，但我相信它的运行时间是n，其中n是树中节点的总数。 - Nicholas

@Nocholas，你是正确的，你的朋友是错误的。它的时间复杂度为O(n)。 - Uri London

Answer 2

如果一棵树有n个节点，那么这不就是n吗？

您只需访问每个树叶一次，所以我认为这是线性的。

- Nanne

---

我猜应该是有“n个节点”的树，而不是“n个叶子”。 - aamadmi

@Nanne 如果使用正确的算法，时间复杂度确实是线性的（只访问每个节点一次），但空间复杂度可能仍然不是线性的。例如使用堆栈。 - Tim

但问题是关于时间复杂度的。 - Nanne