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

Question

我非常了解前序、中序和后序树遍历算法。 (Reference)。我了解一些用途:按顺序遍历二叉搜索树，预排序用于克隆树。但我一辈子都想不出需要后序遍历才能完成的现实世界任务。

你能举个例子吗？并且:你能给我更好的预序遍历用法吗？

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

Answer 1

Topological sorting是树(或有向无环图)的后序遍历。

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

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