CODEWITHSUNDEEP
javaloops
Malintha
Malintha

Reputation: 4776

Traverse to the deepest using Java

I have a data structure like below:

Task(id,name,subTasks[Task])

But the problem is the subTasks can contain Tasks which have another subTasks. This can run to very deep like this:

Task1 Contains SubTask1

SubTask1 contains it's sub tasks

and you can understand this can be run to very deep.

I can retrieve these data from a database tables. But how can I store this in a data structure in java. Using for loops without knowing the deep is useless and not a elegant way. What would be the best data structure and data traversal way?

Upvotes: 5

Views: 5244

Answers (2)

ZhekaKozlov
ZhekaKozlov

Reputation: 39576

Use Guava TreeTraverser:

Task root = ...

/*
 * For example, you have the following tree:
 *
 *          h
 *        / | \
 *       /  e  \
 *      d       g
 *     /|\      |
 *    / | \     f
 *   a  b  c        
 */

TreeTraverser<Task> traverser = new TreeTraverser<Task>() {
    @Override
    public Iterable<Task> children(Task root) {
        return root.subTasks;
    }
};

Then you can iterate over the tree with for loop in several ways:

// Iterate in breadth-first order (hdegabcf)
for (Task task : traverser.breadthFirstTraversal(root)) { ... }

or

// Iterate in preorder (hdabcegf)
for (Task task : traverser.preOrderTraversal(root)) { ... }

or

// Iterate in postorder (abcdefgh)
for (Task task : traverser.postOrderTraversal(root)) { ... }

Upvotes: 21

Sebastian Redl
Sebastian Redl

Reputation: 72044

Data structure: the implicit tree formed by object references.

Traversal: recursion or queues.

However, you will have to consider each use case individually. Some will call for depth-first traversal, some for breadth-first traversal. Consider using some graph library to build the trees in the first place if you need a lot of graph operations.

Upvotes: 3

Related Questions