现实世界前/后阶遍历树遍历的例子

问题描述：

我很理解预订，有序和后阶遍历算法。（Reference）。我理解了一些用途：按顺序遍历二叉搜索树，按顺序克隆树。但是我不能为了我的生活而想出一个真正的世界任务，我需要通过后序遍历来完成。现实世界前/后阶遍历树遍历的例子

你能举个例子吗？而且：你能给我预订遍历的更好用法吗？

编辑：任何人都可以给我一个例子，而不是表达式树和RPN？那真的是所有的后期订单都适合吗？

优秀的问题！ – Lazer 2010-08-20 22:30:48

答

Topological sorting是树木（或向无环图）一个后序遍历。

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

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

这是一个很好的答案。记住树是退化的图可以打开各种功能。拓扑排序非常有用。 – Plutor 2010-08-23 13:57:54

为什么它被称为拓扑排序而不是计划或什么，或者什么是“拓扑”在这种情况下应该表示的意思？ – Shawn 2011-04-30 03:08:04

@Shawn：打我。这可能是因为只有图形/网络的拓扑很重要。 – 2011-05-03 18:12:18

答

邮政编码是（可以）由编译器使用。考虑一个a + b + c的表达式树，机器语言将需要一个像a b + c +这样的序列。这也被称为Reverse polish Notation（RPN）。在维基百科页面上，它说：“RPN又名后缀”

销毁树也需要后期订单，就像创建/克隆它需要预订。

摧毁一棵树，这是一个很好的观点。 – Plutor 2010-08-20 16:08:21

+1它就像你可以使用预定顺序克隆一棵树，并使用反向步骤销毁它，例如后序。应该有一些其他领域的前/后命令将非常有效。 – Lazer 2010-08-20 22:38:05

答

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

伪代码：

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

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

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

现实世界前/后阶遍历树遍历的例子

相关推荐