Algorithm for recursive passage through the forest of children
Please let me know if this is bad practice or something bad. The point is in my program, I need to make a method that goes through the root element and all the child nodes of that element. My elements are as follows:
|--ID--|--Parent--|--Additinal info--|
| 1 | 0 | root element |
| 2 | 0 | root elemnet |
| 3 | 1 |child element of 1|
| 4 | 1 |child element of 1|
| 5 | 3 |child element of 3|
--------------------------------------
Now if I want to get all the children of an element with id 1 (no matter if it has 1000 children or only 2 as in this example), I want my method to cast this too, but I'm not sure how it is to do? All of these items are in the list and this is what I am working with. Every time I find an element I need to check if it has children, the same happens with children. This is because I need to output the items in the correct order. I was thinking about doing this, so I create a layout map first and then use a map for output, but Im kinda stuck with this idea.
Any hints?
source to share
Like many of these tree problems, the magic word here is recursion. The order you describe in the table is the order by IDs, which does not match depth or width at first. But that's ok, all you have to do is put the nodes in some strcuture data that will return them in the order you want. So the general plan
- walk the tree recursively to find all the nodes; insert the nodes into strcuture file which orders them by id
- print ordered nodes
The recursive part is also simple:
-
start at root node
-
if root node is not in the list of nodes add it
- take the first child node and do the same thing.
So, something like (pseudocode):
dfs(node, nodelist):
if node not in nodelist
insert node in nodelist
for each child node n
dfs(n, nodelist)
source to share
Your approach to representing hierarchical data is very inefficient when it comes to traversing node children. You basically need to issue one request per node.
I highly recommend taking a look at the nested set model ( explained on this page ). If you use this approach, you can move the children of a node with a single request regardless of the tree depth or the number of children.
source to share
You need to implement something like a loop in the list and for each of the current list item, find the number of children, for example the number of items in the list, where element.Parent = currentElementofList.Id.If this element is the counting number of children is greater than zero, you should get these child elements, and this continues until there are no more elements in the list.
source to share
This sounds like a graph traversal problem, so I would turn this list into a graph structure (using an adjacency list ) and then traverse it with DFS or BFS .
source to share
You need an adjacency list model .
Check out the article for more details, but this method allows you to get your tree with a single query and the result easily runs through your code. This is the fastest method for randomly accessing a tree.
source to share