I have to create a tree structure for data where each node can have an arbitrary number of childrens. I tried to create a Node class with an array of Node as property but I cannot figure out how to fill and navigate it. Consider the following data to fill the tree
and consider that if there is a new branch I have to read it first. So the order of data I get for the previous example is:
a1, a2, b2, b3, c3, c4, c5, b4, b5, a3, a4, a5
How do I fill these data effectively? How do I move between branches?
Thank you for the inputs.
It’s a linked list.
One way to do this is to have one of the properties of the object, be a dictionary or a collection or an array
You can add as many references to other objects to the dictionary of each node.
[code]a1 = new myobject
a2 = new myobject
b2 = new myobject
a2.list.value (b2) = b2 //i know, here the key and the value are the same. [/code]
Another way to do this is to use an in-memory SQLLite database to hold the relationships.
You would need unique identifiers for your objects
You could have a table which contained 2 columns:
ME_REF / PARENT_REF
group / null
a1 / group
a2 / group
a3 / group
b2 / a2
b3 / a2
b4 / a2
b5 / a2
Armed with that table, you can loop through items at the group level:
Select me_ref from thetable where parent_ref = 'group'
and for each of them, obtain all their kids with the same code:
Select me_ref from thetable where parent_ref = 'a2'
and so on.
The old-school method was for each node to have both a child and a sibling. You would do a depth-first traversal with code like
sub recurse(n as Node)
// process this node
But these days, an array of children is cleaner.
thank you for the answer. There’s something I still do not understand. a1, a2, etc… are nodes belonging to a “tree” which I am trying to build. I have to read many trees like that, where the number of nodes and their relationships is variable: how to deal with references to objects when you don’t know a priori how many nodes you have? Should I create a dictionary of nodes? I am a little bit confused…
You usually count your nodes. You can have a method getNumberOfNodes which returns the ubound of your children array.
It would help to know if you’re familiar with recursion, and recursive routines. That is the key to dealing with tree type structures.
What are you doing?
If you are reading the tree, where is the data, and what does it look like?
Building the tree in memory is
-Read a node
-Know what the parent is.
-Create an object to represent the node.
-Add the object to the array of the parent.
Afterwards, you can use a recursive method to display or write the output
(This code is pseudocode, written straight to screen… dont expect it to run ‘as is’)
It assumes the object has a .name property and an array property called ‘array’
sub Output (n as mynode)
if ubound n.array() > 0 then
for x as integer = 0 to ubound n.array()
Output n.array(x) //recurse and tell me about this child
//no kids, tell me who you are
Kick it off by calling Output (firstnode)
Thank you all for all the answers. I will try to digest your suggestions and in case I will ask you again in case of doubts.