现实世界中的前/后序树遍历示例

Question

我很明白树的先序遍历、中序遍历和后序遍历算法(参考链接)。我也理解它们各自的用途：中序遍历用于有序的遍历二叉搜索树，先序遍历用于克隆一棵树，但是我无论如何都不能想出一个需要用到后序遍历的现实任务。

你能给我举个例子吗？还有，你能提供任何更好的先序遍历用途吗？

编辑：除了表达式树和逆波兰表示法，还有谁能给我一个例子吗？后序遍历真的只适用于这些场景吗？

- Plutor

Answer 1

拓扑排序是树（或有向无环图）的后序遍历。

其思想是，图的节点表示任务，从A到B的边表示在执行B之前必须先执行A。拓扑排序将这些任务排列成一个序列，使得任务本身出现在其所有依赖项之后。像UNIX make这样的任何构建系统都必须实现此算法。

Dario提到的例子——使用手动内存管理销毁树的所有节点——就是这个问题的一个实例。毕竟，销毁节点的任务取决于其子节点的销毁。

- Heinrich Apfelmus

---

这是一个很棒的答案。记住树是退化图可以打开各种功能。拓扑排序也非常有用。 - Plutor

为什么它被称为拓扑排序而不是调度或其他什么，或者在这个上下文中，“拓扑”应该意味着什么？ - Shawn

@Shawn：我也不清楚。可能是因为只有图/网络的拓扑结构才是重要的。 - Heinrich Apfelmus

Answer 2

正如Henk Holterman所指出的那样，使用手动内存管理来销毁一棵树通常是后序遍历。

伪代码：

destroy(node) {
  if (node == null) return;

  destroy(node.left)
  destroy(node.right)

  // Post-order freeing of current node
  free(node)
}

- Dario