现实世界中前/后顺序树遍历示例 [英] Real world pre/post-order tree traversal examples

问题描述

我了解顺序，顺序和顺序树遍历算法很好。 （参考）。我了解一些用途：按顺序遍历二进制搜索树，按顺序克隆树。但是我无法终生提出一个现实世界的任务，我需要后遍历才能完成任务。

I understand pre-order, in-order, and post-order tree traversal algorithms just fine. (Reference). I understand a few uses: in-order for traversing binary search trees in order, pre-order for cloning a tree. But I can't for the life of me come up with a real world task that I'd need post-order traversal to accomplish.

能举个例子吗？ ？并且：您能给我更好的用于遍历顺序的方法吗？

Can you give me an example? And: can you give me any better uses for pre-order traversal?

编辑：除了表达式树和RPN之外，还有谁能给我一个例子？

Can anyone give me an example other than expression trees and RPN? Is that really all post-order is good for?

推荐答案

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

Topological sorting is a post-order traversal of trees (or directed acyclic graphs).

图的节点表示任务，并且从 A 到 B 的边表示 A 必须在 B 之前执行。拓扑排序将按顺序排列这些任务，以使任务的所有依存关系早于任务本身出现。任何类似 UNIX make 的构建系统都必须实现此算法。

The idea is that the nodes of the graph represent tasks and an edge from A to B indicates that A has to be performed before B. A topological sort will arrange these tasks in a sequence such that all the dependencies of a task appear earlier than the task itself. Any build system like UNIX make has to implement this algorithm.

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

The example that Dario mentioned — destroying all nodes of a tree with manual memory management — is an instance of this problem. After all, the task of destroying a node depends on the destruction of its children.

这篇关于现实世界中前/后顺序树遍历示例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！