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

Question

我很了解前序、中序和后序树遍历算法。 （参考）。我了解一些用途：按顺序遍历二叉搜索树，预排序用于克隆树。但我一生都无法想出一个需要后序遍历才能完成的现实世界任务。

你能举个例子吗？还有：你能给我一些预购遍历的更好用途吗？

编辑：除了表达式树和 RPN 之外，谁能给我一个例子吗？这真的是所有后购都有好处吗？

Answer 1

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

这个想法是，图的节点代表任务，从 A 到 B 的边表示 A 必须在 之前执行B。拓扑排序会将这些任务按顺序排列，使得任务的所有依赖项出现早于任务本身。任何构建系统（例如 UNIX make）都必须实现此算法。

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

Answer 2

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

伪代码：

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

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

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