Linked list with multiple links to implement Tree data structure

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

Re: Linked list with multiple links to implement Tree data structure

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.

Re: Linked list with multiple links to implement Tree data structure

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

Re: Linked list with multiple links to implement Tree data structure

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

Re: Linked list with multiple links to implement Tree data structure

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

Re: Linked list with multiple links to implement Tree data structure

Quote:

Originally Posted by

**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

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

1 Attachment(s)

Re: Linked list with multiple links to implement Tree data structure

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

Attachment 1879

Re: Linked list with multiple links to implement Tree data structure

Quote:

Originally Posted by

**kavithavr** 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

Re: Linked list with multiple links to implement Tree data structure

Ok Thank you

I will get back after the implementation

With regards

kavitha