Results 1 to 9 of 9
  1. #1
    kavithavr is offline Member
    Join Date
    Oct 2011
    Posts
    5
    Rep Power
    0

    Default 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

  2. #2
    doWhile is offline Moderator
    Join Date
    Jul 2010
    Location
    California
    Posts
    1,641
    Rep Power
    7

    Default 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.

  3. #3
    kavithavr is offline Member
    Join Date
    Oct 2011
    Posts
    5
    Rep Power
    0

    Default 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

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

    Default 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
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    kavithavr is offline Member
    Join Date
    Oct 2011
    Posts
    5
    Rep Power
    0

    Default 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

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

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

    Quote Originally Posted by kavithavr View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    kavithavr is offline Member
    Join Date
    Oct 2011
    Posts
    5
    Rep Power
    0

    Default 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

    Linked list with multiple links to implement Tree data structure-fp-growth-tree.jpg

  8. #8
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

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

    Quote Originally Posted by kavithavr View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  9. #9
    kavithavr is offline Member
    Join Date
    Oct 2011
    Posts
    5
    Rep Power
    0

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

    Ok Thank you

    I will get back after the implementation

    With regards
    kavitha

Similar Threads

  1. Tree data structure
    By Nacao in forum New To Java
    Replies: 18
    Last Post: 08-23-2011, 07:26 PM
  2. Spreadsheet data - linked list or hashmap
    By j919 in forum New To Java
    Replies: 2
    Last Post: 02-19-2011, 08:20 PM
  3. data structure with multiple keys
    By jon80 in forum New To Java
    Replies: 2
    Last Post: 06-13-2009, 04:02 PM
  4. Replies: 1
    Last Post: 10-20-2008, 01:58 PM
  5. Doubly-linked list with data structure
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-16-2008, 11:30 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •