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?
Edit: Can anyone give me an example other than expression trees and RPN? Is that really all post-order is good for?
Answer
Topological sorting is a post-order traversal of trees (or directed acyclic graphs).
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.
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.