使用Java遍历最深处

Question

我有一个如下的数据结构:

Task(id,name,subTasks[Task])

但问题是subTasks可以包含具有另一个子任务的任务.这可以像这样非常深:

Task1 Contains SubTask1

SubTask1包含它的子任务

你可以理解这可以运行得非常深.

我可以从数据库表中检索这些数据.但是我如何将它存储在java中的数据结构中.在不知道深度的情况下使用for循环是没用的而不是优雅的方式.什么是最好的数据结构和数据遍历方式？

Answer 1

使用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;
    }
};

然后,您可以通过以下for几种方式循环遍历树:

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

要么

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

要么

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

Answer 2

数据结构：由对象引用形成的隐式树。

遍历：递归或队列。

但是，您必须单独考虑每个用例。有些会要求深度优先遍历，有些会要求广度优先遍历。如果您需要大量图形操作，请首先考虑使用一些图形库来构建树。