如何修改先序树遍历算法来处理具有多个父节点的节点？
我已经搜索了一段时间，似乎无法找到替代解决方案。我需要树遍历算法，以便一个节点可以有多个父级（如果可能的话）（在这里找到一篇很棒的文章：在数据库中存储分层数据）。有没有什么算法可以让我们从根节点开始确定节点的顺序和依赖关系（目前正在阅读拓扑排序）？
I've been searching for a while now and can't seem to find an alternative solution. I need the tree traversal algorithm in such a way that a node can have more than 1 parent, if it's possible (found a great article here: Storing Hierarchical Data in a Database). Are there any algorithms so that, starting from a root node, we can determine the sequence and dependencies of nodes (currently reading topological sorting)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您描述的结构不是树，而是有向图。由于它适合分层绘图，您可能会想将它视为一棵树（它本身是一个非循环连通图）。
典型的图遍历算法是 深度优先 和 广度优先。图实现的唯一不同之处在于它记录了已经访问过的节点，以避免多次访问某些节点。但是，如果您的数据结构保证它是非循环的，您可以通过简单地将“父母”视为“孩子”来在图上使用树算法。
我画了一个简单的草图来说明我的意思（这是尝试 Google 文档新绘图功能的绝佳机会）：
如您所见，可以处理任何具有将非循环有向形式作为树并对其应用树算法。一旦您无法保证此属性，您就必须采用专用的图算法。
The structure you described isn't a tree, it's a directed graph. As it would be suitable for hierarchical drawing you might be tempted to think of it as a tree (which itself is an acyclic connected graph).
Typical traversal algorithms for graphs are depth-first and breadth-first. The graph implementation is only different as it records the nodes it has already visited in order to avoid visiting certain nodes multiple times. However, if your data structure guarantees that it's acyclic, you can use tree algorithms on your graph by simply treating "parents" as "children".
I made a simple sketch to illustrate what I mean (the perfect chance to try Google Docs' new drawing feature):
As you see, it's possible to treat any graph that has an acyclic directed form as a tree and apply tree algorithms on it. As soon as you can't guarantee this property you'll have to go for dedicated graph algorithms.
树基本上是一个有向未加权图，其中每个顶点具有 N 或更少的边，并且不会发生循环。
如果您确定树中没有循环，则可以将父节点视为指定节点的另一个子节点，并正常执行前序遍历。
但是，如果可能发生循环，则需要图算法。
具体来说：广度优先搜索。
A tree is basically a directed unweighted graph, where each vertice has N or less edges, and no cycles can happen.
If your'e certain there are no cycles in your tree, you could just treat a parent as another child of the specified node, and preform a preorder traversal normally.
However, if cycles might happen, you need graph algorithms.
Specifically: Breadth first search.
只是检查一个简单的情况：两个父母可以有不同的父母吗？
如果不是，您可以将它们变成单个节点（概念上）并再次拥有一棵树。
否则，您将必须拆分子节点并为另一个父节点复制一个分支。
（这当然会导致稍后出现不一致和/或低效的算法，具体取决于您是否需要维护数据结构）。
如果您坚持使用树结构，则上述选项有效，根据定义，树结构只能有一个父母。
因此，也许您需要退后一步，解释一下您想要完成什么，以及为什么如果节点可以有两个父节点，那么它必须是树结构。
Just checking for maybe a simple case: can the two parents have different parents?
If no you could turn them into single node (conceptually) and have a tree again.
Otherwise you will have to split the child node and duplicate a branch for the other parent.
(This can of course lead to inconsistency and/or inneficient algorithms later, depending if you will need to maintain the data structure).
The above options hold if you insist on having the tree structure, which by definition can have only one parent.
So maybe you need to step back and explain what are you trying to accomplish and why it must be a tree structure if nodes can have two parents.
你在这里描述的不是一棵树。您不能将您的图表称为树。
树是一个没有环的无向图。父/子关系不是对边缘绘制方向的解释。它们是将一个顶点命名为根的结果。
我们将顶点命名为 current 的“父”，因为它是根路径的下一个顶点。与当前顶点相邻的所有其他顶点都是“子顶点”。
您不能以“父级”位于“上方”或“指向顶点”，而子级位于“下方”或“顶点指向它们”的方式来布局任意图。一棵树之所以是一棵树，是因为摘下了根。你在问题中描绘的不是一棵树。并且树遍历算法不适用于遍历任意图。
有多种图遍历算法，例如 广度优先搜索 或 深度优先搜索（查看这些页面中的附注以了解更多信息）。使用它们，而不是试图将您的全功能图表与您对树的知识联系起来。
You aren't describing a tree here. You can NOT call your graph a tree.
A tree is an undirected graph without cycles. Parent/child relationship is NOT an interpretation of directions drawn on the edges. They are the result of naming one vertex the root.
We name a vertex "parent" to current, because it's the next one to the path to root. All other vertexes adjacent to current one are "children".
You can't just lay out an arbitrary graph in such a way that "parents" are "above" or "point to vertex", and children are "below" or "vertex points to them". A tree is a tree because a root is picked. What you depict in your question is not a tree. And tree traversal algorithms are NOT applicable to traversing arbitrary graphs.
There are several graph traversal algorithms, such as breadth-first search or depth-first search (check side notes in those pages for more). Use them instead of trying to tie your full-featured graph into your knowledge about trees.