How can I change the preorder tree traversal algorithm to handle multi-parent nodes?
I've searched for a while and can't find an alternative solution. I need a tree traversal algorithm such that a node can have more than one parent if possible (found a great article here: Storing a Data Hierarchy in a Database ). Are there any algorithms so that starting from the root node we can determine the sequence and dependencies of the nodes (currently reading topological sort)?
a source to share
A tree is basically a directed unweighted graph, where each vertex has N or fewer edges, and no cycles can happen. If you are sure that there are no loops in your tree, you can simply treat the parent as another child of the specified node, and usually preform the preorder traversal.
However, if loops can happen, then you need graph algorithms.
In particular: Fast Breadth Search .
a source to share
The structure you described is not a tree, it is a directed graph. Since this would be appropriate 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 depth-first and width -first plots . The graph implementation differs only in that it registers the nodes that it has already visited, so as not to visit certain nodes multiple times. However, if your data structure guarantees that it is acyclic, you can use tree algorithms in your graph by simply treating "parents" as "children".
I made a simple sketch to illustrate what I mean (great chance to try out the new Google Docs drawing feature):
As you can see, you can consider any graph that has an acyclic directional shape like a tree and applies tree algorithms on it. Once you cannot guarantee this property, you will have to move on to dedicated graph algorithms.
a source to share
Just check maybe a simple case: can two parents have different parents? If not, you can turn them into a single node (conceptually) and have a tree again.
Otherwise, you will have to split the child node and duplicate the branch for the other parent. (This can of course lead to inconsistencies and / or alternative algorithms later, depending on whether you need to maintain the data structure).
The above parameters are preserved if you insist on having a tree structure that definition can have only one parent.
So maybe you need to step back and explain what you are trying to accomplish and why it should be a tree structure if nodes can have two parents.
a source to share
You are not describing a tree here. You can NOT call your graph a tree.
A tree is an undirected graph with no cycles. The parent / child relationship is NOT an interpretation of the directions drawn around the edges. They are the result of naming one vertex of the root.
We call the vertex "parent" current because it is next to the path to the root. All other vertices adjacent to the current one are "children".
You can't just lay out an arbitrary graph so that the "parents" are "above" or "point to the top" and the children are "below" or "the top points to them". A tree is a tree because the root is chosen. What you depict in your question is not a tree. And tree traversal algorithms are NOT applicable for traversing arbitrary graphs.
There are several algorithms for traversing the graph, such as Breadth First Search or Depth First Search (check additional notes on these pages). Use them instead of tying your fully functional graph to your tree knowledge.
a source to share