algorithm - 真实世界的前/后顺序树遍历示例

Question

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

你可以给我一个例子吗？并且：你能给我更好的预购遍历用途吗？

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

Answer 1

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

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

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

Answer 2

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

伪代码：

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

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

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