Results 1 to 3 of 3
  1. #1
    ryan.ames is offline Member
    Join Date
    Mar 2009
    Posts
    2
    Rep Power
    0

    Default Multiple paths through trees

    Hi

    I have a tree structure (root, internal nodes and leaves) and at each internal node I have recorded one or more values.

    I want to be able to move from the root to the leaves and generate all possible paths through the tree. Im using recursion to move through the tree and processing each node individually.
    i.e. where an internal node has two values I need to generate two paths and if the next node has only one value this is appended to each path and so on.

    Therefore the number of possible paths is the product of the number of values at each node.

    I have managed to code this but it is inefficient and generates an out of memory error when the number of potential paths through the tree is large (i.e. about 7 million)

    I was wondering if anyone could suggest data structures or an api suitable for this type of problem.

    Thanks in advance.

  2. #2
    Sylar's Avatar
    Sylar is offline Member
    Join Date
    Mar 2009
    Location
    Odessa, Texas
    Posts
    16
    Rep Power
    0

    Default

    Try adding some indicator. A boolean data which indicates whether that path has already been traversed.

  3. #3
    ryan.ames is offline Member
    Join Date
    Mar 2009
    Posts
    2
    Rep Power
    0

    Default

    Hi Sylar

    The problem isn't that I store redundant paths through the tree. Its just that there are so many paths I run out of memory before I have found them all. The problem I think is finding an efficient way to store a large number of strings. I have since tried the StringBuffer class which allowed me to store more objects but still not enough.

Similar Threads

  1. passing variable in trees??
    By player123 in forum Advanced Java
    Replies: 2
    Last Post: 02-03-2009, 12:42 PM
  2. Game Trees
    By javaBoy1 in forum Advanced Java
    Replies: 0
    Last Post: 12-27-2008, 12:20 AM
  3. Help With Tournament Trees
    By wiggsfly in forum New To Java
    Replies: 2
    Last Post: 10-26-2008, 09:38 PM
  4. Eclipse with VERY LARGE source trees
    By wyrickre in forum Eclipse
    Replies: 0
    Last Post: 02-01-2008, 02:23 AM
  5. ElegantJ Trees Bean 1.1
    By JavaBean in forum Java Software
    Replies: 0
    Last Post: 07-06-2007, 02:59 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
  •