tree structure for data

General
1

Hi,

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

a1---a2---a3---a4---a5 \\ b2---b3---b4---b5 \\ c3---c4---c5

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.

2

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

//dictionary method
a2.list.value (b2) = b2 //i know, here the key and the value are the same. [/code]

//array method a2.thearray.append b2

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
a4/ group

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.

3

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
   recurse(n.child)
   recurse(n.sibling)
end sub

But these days, an array of children is cleaner.

4

Hi Tim,

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… :frowning:

Thanks

5

You usually count your nodes. You can have a method getNumberOfNodes which returns the ubound of your children array.

6

It would help to know if you’re familiar with recursion, and recursive routines. That is the key to dealing with tree type structures.

7

Read?
or create?

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’

[code]

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
next
else
//no kids, tell me who you are
msgbox n.name
end if

end sub[/code]

Kick it off by calling Output (firstnode)

8

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.