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

Question

我正在刷新不同的树遍历方法,最后阅读以下维基百科文章.正如所料,二叉树有三种深度优先遍历方法:

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

以下是维基百科提供的所有解释:

其中n是子节点的数量.根据手头的问题,预订,有序或后序操作可能无效,或者您可能只想访问特定的子节点,因此这些操作应视为可选.而且,实际上可能需要不止一个预订,有序和后订单操作.例如,当插入三元树时,通过比较项目来执行预订操作.之后可能需要后序操作来重新平衡树.

指定的算法对我没有意义,因为它是根据未定义的操作指定的:

1. 预订操作.
2. 后期订单操作.
3. 顺序操作.

为了增加混乱,我无法根据我所知道的以及维基百科文章中的内容提出所述操作的定义.我一直在困惑这一段时间没有真正的突破.我有以下问题:

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

Answer 1

所述算法确实是正确的.在这种情况下发生的事情是,维基百科文章包含一段代码,用于处理处理预订,顺序和后序遍历的一般情况.

您可以将preorder,inorder和postorder遍历视为更通用算法的特殊情况.具体来说,假设您想要在搜索期间(预订,订购或后订购)的特定时间进行树遍历并执行某些操作.考虑这一点的一种方法是在访问当前节点之前执行一些预订操作,在访问节点的子节点和节点本身之间执行一些顺序操作,以及在访问节点之后执行一些后序操作.任何这些操作都可以"什么都不做".例如,一个简单的前序遍历将被指定为

• 预购步骤:执行您要预先安排的操作
• 顺序步骤:无操作
• 后序步骤:无操作

同样,后序遍历也是如此

• 预购步骤:无操作
• 顺序步骤:无操作
• 后序步骤:执行您想要的后期操作

维基百科代码的优势在于它允许您执行需要预订和后订单步骤的操作.例如,假设您要进行树搜索,但在每个时间点跟踪已访问但尚未完成的节点.你可以这样做:

• 预订步骤:将当前节点添加到"活动"列表中.
• 顺序步骤:无操作
• 后序步骤:从"活动"列表中删除当前节点.

一些算法,如Tarjan的SCC算法,实际上做了这样的事情(虽然不可否认这是一个图算法,问题与树有关).维基百科代码因此给出了一般情况,其中更常见的情况,加上这种更高级的情况,是特殊情况.

希望这可以帮助!