I have a Spaghetti Stack (an N-ary tree data structure in which child nodes have pointers to the parent nodes) - received from a database.
The "stack" received from database is just a list with all nodes so can be multiple stacks inside.
The Nodes are records from the database where parent.id is a ForeignKey to another record of the same type.
class Node_Category:
def __init__(self, value):
self.value = value
parent_id = id
The structure is something like this:
Category 1
-Category 1_1
--Category 1_1_1
-Category 1_2
Category_2
Category_3
-Category 3_1
-Category 3_2
What I need:
Now I know the child's parent. Starting from a parent Node I need to know his children.
So I need to traverse the 'Spaghetti Stack' add connections in parent nodes to children so I can traverse from parent to children.
A parent can have 0, one or multiple children.
Because I don't know the depth of the stack I tried to do it recursive.
Also I think a form of memorization is necessary because looping thru array a parent of a parent get multiple accesses.
What I tried:
def _recurse_for_parents(self, category, path=None):
if path is None:
path = []
path.append(category)
if category.parent:
return self._recurse_for_parents(category.parent, path)
return path
for record in categories:
self._recurse_for_parents(category)
The issues:
In the loop I can hit the parent, first level child, second level etc:
Child1_L2-Child1_L1->parent; Child1_L1->parent; parent->Null
Child1_L1->parent; parent->Null
Child2_L1->parent; parent->Null
So, I'm hitting the same path on different depths multiple times. Also for each path I need to add the link from his parent back to children.
This seems pretty simple in concept. I don't see where a recursive implementation would be of particular use. An iterative solution is straightforward. I'll outline the basic idea.
I assume you are given an array of N nodes, and you have an ID for each node.
The first thing I'd do is create a dictionary, keyed by ID, and the values are a new node type that has the structure:
NewNode
Id - the node's id
Children - a list of some type that contains the ids of the node's children
Whatever other data the database gives you.
For each node in the list, look up the parent in the dictionary, and add the node to the list of the parent's children.
While you're going through the list in the step above, you should run across one node that has no parent id. That's the root. If there is no such node or there's more than one, then you have invalid data.
Anyway, you look up that node's id in the dictionary and save it as the root.
Let's say you have two trees:
100 200
/ \ / | \
101 120 201 210 220
| / \ | |
102 121 122 202 221
/ \ / | \
103 110 203 204 205
|
104
So you have these nodes:
ID Parent
104 103
103 102
102 101
101 100
100 NULL
110 102
121 120
120 100
122 120
203 202
202 201
201 200
204 202
205 202
210 200
221 220
220 200
200 NULL
What I'm suggesting is that you create a dictionary from that list, keyed by the node id. And with a children list for each node.
Now, starting with the first item in the list, you look up the parent, and add the node to the parent's child list. So for the first item, you see that node 104 has parent 103. You add a reference to node 104 to 103's child list.
Then you move on to the next node in the list. When you're done, your dictionary looks like this:
ID Parent Children
104 103 []
103 102 [104]
102 101 [103]
101 100 [102]
100 NULL [101,110,120]
110 102 []
121 120 []
120 100 [121,122]
122 120 []
203 202 []
202 201 [203,204,205]
201 200 [202]
200 NULL [201,210,220]
204 202 []
205 202 []
210 200 []
221 220 []
220 200 [221]
Your dictionary now contains the inverted trees. You can scan the dictionary, looking for nodes that have a Parent value of NULL. Those are the roots of your trees. Each root has an array of references to its child nodes, and those child nodes have references to their children, etc.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments