我有一个如下的数据结构:
Task(id,name,subTasks[Task])
但问题是子任务可以包含具有另一个子任务的任务。这可以像这样运行到很深:
Task1 Contains SubTask1
SubTask1 包含它的子任务
你可以理解这可以运行到很深。
我可以从数据库表中检索这些数据。但是我怎样才能将它存储在java中的数据结构中。在不了解深度的情况下使用 for 循环是无用的,也不是一种优雅的方式。最好的数据结构和数据遍历方式是什么?
使用 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)) { ... }
数据结构:对象引用形成的隐式树。
遍历:递归或队列。
但是,您必须单独考虑每个用例。有些会要求深度优先遍历,有些会要求广度优先遍历。如果您需要大量图形操作,请首先考虑使用一些图形库来构建树。