Linked list with multiple links to implement Tree data structure

[kavithavr]

Hello

I am interested to implement Tree data structure in that i want to dynamically create links if needed. For example i cannot restrict my node to have only two links front and back. If need arises i should be able to add third link dynamically.

How to do this? Kindly help me to get the answer.
kavitha

[doWhile]

Define 'links'. If I understand correctly, you could use a List of outgoing/child nodes (or edges, depending upon how complex you want the data structure to be) for each Node.

[kavithavr]

Thank you for your response.

Actually my tree will be having the number of children based upon the users wish. This information is dynamically got from the user if he wishes to add new child at that moment i should be able to do that.

Example : a-b-c-d

is one path and if i want to a child to "b" i should be able to create a new link in b and i should be able to generate another path start from b

Example : "a-b-c-d" is one path and "a-b-e-f " is another path


This is the actual situation for me to implement.

Thank you

[JosAH]

You can define an arbitrary tree with Nodes having three pointers/links/references:

1) a pointer to the parent Node;
2) a pointer to the next sibling Node;
3) a pointer to its leftmost child Node.

kind regards,

Jos

[kavithavr]

Yes i understood what you have mentioned but my problem is not one sibling it can be multiple siblings and the count also i do not know

Thanks in advance
kavitha

[JosAH]

Yes i understood what you have mentioned but my problem is not one sibling it can be multiple siblings and the count also i do not know

You didn't understand my hint; if a (root) node A has three children B, C and D then:

1) A has a null parent node and B, C and D have A as their parent node;
2) A has a null sibling node, B has C as its sibling node, C has D as its sibling node and D has null as its sibling node;
3) A has B as its leftmost child node and the others has null as their leftmost child node.

kind regards,

Jos

[kavithavr]

yes i got it. Thank you


The same structure can i use it for FP-Growth Tree implementation? The example i have attached with this.

With regards

[JosAH]

The same structure can i use it for FP-Growth Tree implementation? The example i have attached with this.

Sure, that three pointer structure can be used for any tree; the advantage of that structure is that there are just a fixed number of pointers per node; the disadvantage is that you have to traverse the sibling list if you want to find a (any) sibling.

kind regards,

Jos

[kavithavr]

Ok Thank you

I will get back after the implementation

With regards
kavitha