前序遍历 OR 后序遍历

我想请教一下，在树的遍历过程中，前序遍历和后序遍历对于解决问题的区别。

首先，概念上我是认可 前序遍历描述了一个自顶向下的过程，而后序遍历描述了一个自底向上的过程。但是仔细分析一下会发现计算机实现的过程其实都是自底向上实现的，所以我感觉前序遍历 和 后序遍历是本质上是一样的。所以想问一下这两种遍历各自代表的是什么，相对应解决那些问题，有什么区别和联系呢？

Top-down和Bottom-up这两个词在不同的context下，具体意义会有些区别。比如，同样的算法。人们可能会把使用递归实现的方法统一称作Top-down，而使用迭代法的算法称作Bottom-up。这里的TD和BU指的是implementation方式层面的TD和BU。而二者实现的算法其实是相同的。

而我们说preorder和postorder分别是TD和BU，则代表了算法本质的差别。这时的TD和BU代表了两种完全不同的算法，即使它们都用递归或都用迭代实现。

如果上层函数的执行顺序是直接把input拆成两半，分别递归调用子函数。每个子函数得到一半的结果，然后再由上层函数把着两半结果拼成一个完整结果。这叫做bottom-up递归。最明显的例子，就是mergesort和post-order。之所以这种情况是bottom-up，是因为你看最后的元素处理顺序是局部到整体。比如mergesort，最先被执行的交换都是局部交换：0和1换, 1和2换...然后才可能出现0和3换……最后一步才可能出现1和n, 2和n-1这种交换。post-order同理，最先被访问的是最基层的节点。

反之，如果是上层函数先对input做一定的处理，然后再递归调用函数分别对被处理好的input一半做处理。两半递归结束后，答案自然成型，上层函数不需要再做任何事情了。这叫做bottom-up递归。最典型的例子是quicksort和pre-order。quicksort最开始出现的交换全是整个数组范围内的交换：1和n交换，2和n-1交换……直到最后才变成局部的0和1,1和2……交换。一旦所有局部交换都完成，那数组就自然排好了。这种递归是整体到局部，所以是top-down.

区分两者你就记住一个原则就好：看算法是“先递归再处理”(bottom-up)，还是"先处理再递归"（top-down）

stellari 发表于 2016-10-25 13:20
Top-down和Bottom-up这两个词在不同的context下，具体意义会有些区别。比如，同样的算法。人们可能会把使用 ...

感谢您精彩的回复，那么您认为先序，中序，后序三种对树的遍历方式，实质上的区别究竟是什么呢？

你觉得都是自上而下是因为你写成了递归....stack call无论你写什么玩意它都是自上而下的. 这跟算法没关系.

WhatsFLAG 发表于 2016-10-25 13:56
感谢您精彩的回复，那么您认为先序，中序，后序三种对树的遍历方式，实质上的区别究竟是什么呢？

The easiest answer is that the order of the traversal is different.

adrianliu729 发表于 2016-10-25 16:03
The easiest answer is that the order of the traversal is different.

Instead of only one order, why do we need the other two orders?

“先递归再处理”(bottom-up)，还是"先处理再递归"（top-down）-----好赞！