了解通用深度优先树搜索的维基百科代码？
我正在温习不同的树遍历方法，最后阅读了以下维基百科文章 。正如预期的那样，二叉树的深度优先遍历有以下三种方法：
- 先序遍历
- 后序遍历
- 中序遍历
本文接着讨论任意（通用）树的深度优先遍历。为了方便起见，我将其粘贴在这里：
// 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 是子节点的数量。取决于问题所在 另一方面，预购、中购或后购操作可能无效，或者 你可能只想访问某个特定的子节点，所以这些操作 应被视为可选。此外，在实践中不止一种 可能需要进行预订前、预订中和预订后操作。为了 例如，当插入到三叉树中时，预排序操作是 通过比较项目来执行。可能需要进行后订单操作 之后重新平衡树。
指定的算法对我来说没有意义，因为它是根据未定义的操作指定的：
- 预序操作。
- 后序操作。
- 有序操作。
更令人困惑的是，我无法根据我所知道的和维基百科文章中的内容给出上述操作的定义。我为此困惑了一段时间，一直没有真正的突破。我有以下问题：
- 维基百科文章中指定的算法是否错误？我怀疑是这样，但除了具体说明不明确之外，无法确定任何事情。
- 是否为通用树定义了后序、先序、中序深度优先遍历？这些实用吗？和这三个操作的定义有关系吗？如果是这样，怎么办？
- 如果该算法确实正确，有人可以为我定义上述操作并解释它是如何工作的吗？
I was brushing up on different tree traversal methods and ended up reading the following Wikipedia article. As expected, there are three methods of depth first traversal for a binary tree:
- Preorder traversal
- Postorder traversal
- Inorder traversal
The article then goes on to deal with depth first traversal of an arbitrary (generic) tree. I have pasted it here for convenience:
// 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
Here is all the explanation that Wikipedia provides:
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.
The algorithm specified makes no sense to me since it is specified in terms of undefined operations:
- A preorder operation.
- A postorder operation.
- An inorder operation.
To add to the confusion, I can't come up with a definition for the said operations based on what I know and what is present in the Wikipedia article. I have been puzzling over this for a while with no real breakthroughs. I have the following questions:
- Is the algorithm specified in the Wikipedia article wrong? I suspect it is, but can't say anything for certain beyond the fact that it is ill-specified.
- Are a postorder, preorder, inorder depth first traversal even defined for a generic tree? Are these practically used? Does it relate to the definition of the three operations? If so, how?
- If the algorithm is indeed correct, can someone define the above operations for me and explain how it works?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
上述算法确实是正确的。在这种情况下发生的情况是，维基百科文章包含一段代码，该代码处理一般情况，将前序、中序和后序遍历全部处理在一起。
您可以将前序、中序和后序遍历视为更通用算法的特殊情况。具体来说，假设您想要进行树遍历并在搜索过程中的特定时间执行某些操作（前序、中序或后序）。考虑这个问题的一种方法是，在访问当前节点之前执行一些前序操作，在访问节点的子节点和节点本身之间执行一些中序操作，以及在访问节点之后执行一些后序操作。这些操作中的任何一个都可以“不执行任何操作”。例如，一个简单的前序遍历将被指定为
类似地，后序遍历将是
维基百科代码的优点是它允许您执行需要预序和后序步骤的操作。例如，假设您想要进行树搜索，但在每个时间点跟踪哪些节点已被访问但尚未完成。您可以按如下方式执行此操作：
有些算法，例如 Tarjan 的 SCC 算法，实际上会做这样的事情（尽管不可否认，这是一个图表）算法和问题与树有关）。因此，维基百科代码给出了一般情况，其中更常见的情况以及这种更高级的情况是特殊情况。
希望这有帮助！
The algorithm stated is indeed correct. What's happening in this case is that the Wikipedia article contains one piece of code that handles a general case that handles preorder, inorder, and postorder traversals all in one.
You can think of preorder, inorder, and postorder traversals all as special cases of a more general algorithm. Specifically, suppose that you want to do a tree traversal and perform some operation at a particular time during the search (either preorder, inorder, or postorder). One way to think about this is that you do some preorder operation before visiting the current node, some inorder operation between visiting the node's child and the node itself, and some postorder operation after visiting the node. Any of these operations can be "do nothing." For example, a simple preorder traversal would be specified as
Similarly, a postorder traversal would be
The advantage of the Wikipedia code is that it lets you do operations that would require both a preorder and postorder step. For example, suppose you want to do a tree search, but track at each point in time what nodes have been visited but not finished yet. You could do this as follows:
Some algorithms, like Tarjan's SCC algorithm, actually do things like this (though admittedly that's a graph algorithm and the question pertains to trees). The Wikipedia code thus gives the general case of which the more common cases, plus this more advanced case, are special cases.
Hope this helps!