algorithm - 了解通用深度优先树搜索的维基百科代码？

Question

我复习了不同的树遍历方法，最后阅读了以下维基百科 article .不出所料，二叉树的深度优先遍历有3种方式:

1. 前序遍历
2. 后序遍历
3. 中序遍历

然后文章继续处理任意(通用)树的深度优先遍历。为了方便起见，我把它贴在这里:

// To traverse a non-empty tree in depth-first order,
// perform the following operations recursively at each node:
Perform pre-order operation
for i=1 to n-1 do
    Visit child[i], if present
    Perform in-order operation

Visit child[n], if present
Perform post-order operation

这里是维基百科提供的所有解释:

where n is the number of child nodes. Depending on the problem at hand, the pre-order, in-order or post-order operations may be void, or you may only want to visit a specific child node, so these operations should be considered optional. Also, in practice more than one of pre-order, in-order and post-order operations may be required. For example, when inserting into a ternary tree, a pre-order operation is performed by comparing items. A post-order operation may be needed afterwards to rebalance the tree.

指定的算法对我来说毫无意义，因为它是根据未定义的操作指定的:

1. 预购操作。
2. 后序操作。
3. 有序操作。

更令人困惑的是，我无法根据我所知道的和维基百科文章中的内容为上述操作给出定义。我一直对此感到困惑，没有真正的突破。我有以下问题:

1. 维基百科文章中指定的算法是否有误？我怀疑它是，但除了它是不明确的事实之外不能肯定地说什么。
2. 是否为通用树定义了后序、前序、中序深度优先遍历？这些实用吗？跟三个操作的定义有关系吗？如果是这样，如何？
3. 如果算法确实正确，有人可以为我定义上述操作并解释它是如何工作的吗？

Answer 1

所陈述的算法确实是正确的。在这种情况下发生的事情是，维基百科文章包含一段代码，该代码处理一般情况，即处理前序、中序和后序遍历。

您可以将前序、中序和后序遍历视为更通用算法的特例。具体来说，假设您要进行树遍历并在搜索期间的特定时间执行某些操作(前序、中序或后序)。一种思考方式是在访问当前节点之前执行一些前序操作，在访问节点的子节点和节点本身之间执行一些中序操作，在访问节点之后执行一些后序操作。这些操作中的任何一个都可以“什么都不做”。例如，一个简单的前序遍历将被指定为

• 预购步骤:做你想做预购的操作
• 顺序步骤:无操作
• 后序步骤:无操作

类似地，后序遍历是

• 预订步骤:无操作
• 顺序步骤:无操作
• 后序步骤:做你想做后序的操作

Wikipedia 代码的优点是它允许您执行需要前序和后序步骤的操作。例如，假设您要进行树搜索，但要在每个时间点跟踪哪些节点已被访问但尚未完成。您可以按如下方式执行此操作:

• 预购步骤:将当前节点添加到“事件”列表。
• 顺序步骤:无操作
• 后序步骤:从“事件”列表中删除当前节点。

一些算法，比如 Tarjan's SCC algorithm ，实际上做这样的事情(尽管不可否认这是一个图形算法并且问题与树有关)。因此，维基百科代码给出了一般情况，其中更常见的情况加上这个更高级的情况是特殊情况。

希望这对您有所帮助!