Я действительно не видел достаточно вашего кода, чтобы использовать классы, которые вы определили. Поэтому я пошел писать собственное рабочее решение.
В следующем коде, проблема решается с помощью рекурсии:
public class TreeNode {
private String id;
private TreeNode parent;
private List<TreeNode> children;
public TreeNode(String id) {
this.id = id;
this.children = new LinkedList<>();
}
public void addChild(TreeNode child) {
this.children.add(child);
child.setParent(this);
}
public List<TreeNode> getChildren() {
return Collections.unmodifiableList(this.children);
}
private void setParent(TreeNode parent) {
this.parent = parent;
}
public TreeNode getParent() {
return this.parent;
}
public String getId() {
return this.id;
}
}
public class TreePaths {
private static List<List<TreeNode>> getPaths0(TreeNode pos) {
List<List<TreeNode>> retLists = new ArrayList<>();
if(pos.getChildren().size() == 0) {
List<TreeNode> leafList = new LinkedList<>();
leafList.add(pos);
retLists.add(leafList);
} else {
for (TreeNode node : pos.getChildren()) {
List<List<TreeNode>> nodeLists = getPaths0(node);
for (List<TreeNode> nodeList : nodeLists) {
nodeList.add(0, pos);
retLists.add(nodeList);
}
}
}
return retLists;
}
public static List<List<TreeNode>> getPaths(TreeNode head) {
if(head == null) {
return new ArrayList<>();
} else {
return getPaths0(head);
}
}
}
Чтобы использовать код выше, дерево должно быть построено с использованием TreeNode класса. Начните с создания головы TreeNode, затем добавьте к нему дочерние узлы по мере необходимости. Затем голова передается статической функции TreePaths getPaths.
После того, как getPaths проверит значение null, вызывается внутренняя функция getPaths0. Здесь мы следуем глубине первого подхода, пытаясь добраться до всех листовых узлов как можно скорее. Как только листовой узел будет найден, список, содержащий только этот листовой узел, будет создан и возвращен внутри коллекции списка. Родитель этого листового узла будет добавлен в начало списка, который снова будет помещен в список. Это произойдет для всех детей родителя.
В конце концов, все возможные пути будут объединены в единую структуру.Эта функция может быть проверена следующим образом:
public class TreePathsTest {
TreeNode[] nodes = new TreeNode[10];
@Before
public void init() {
int count = 0;
for(TreeNode child : nodes) {
nodes[count] = new TreeNode(String.valueOf(count));
count++;
}
}
/*
* 0 - 1 - 3
* - 4
* - 2 - 5
* - 6
* - 7 - 8
* - 9
*/
private void constructBasicTree() {
nodes[0].addChild(nodes[1]);
nodes[0].addChild(nodes[2]);
nodes[1].addChild(nodes[3]);
nodes[1].addChild(nodes[4]);
nodes[2].addChild(nodes[5]);
nodes[2].addChild(nodes[6]);
nodes[2].addChild(nodes[7]);
nodes[7].addChild(nodes[8]);
nodes[7].addChild(nodes[9]);
}
@Test
public void testPaths() {
constructBasicTree();
List<List<TreeNode>> lists = TreePaths.getPaths(nodes[0]);
for(List<TreeNode> list : lists) {
for(int count = 0; count < list.size(); count++) {
System.out.print(list.get(count).getId());
if(count != list.size() - 1) {
System.out.print("-");
}
}
System.out.println();
}
}
}
Это напечатает:
0-1-3
0-1-4
0-2-5
0-2-6
0-2-7-8
0-2-7-9
Примечания: выше достаточно для ручного тестирования, но функция теста должна быть изменена, чтобы сделать правильные утверждения для надлежащего автоматизированное модульное тестирование.
Проблема заключается в том, что вы предоставляете только части информации, которые нам нужны, чтобы помочь вам. Не понимая, как ваше дерево действительно создано (представлено внутри), мы не можем сказать, почему ваш алгоритм неверен. Поэтому, пожалуйста, откиньтесь назад, обратитесь в справочный центр и прочитайте о http://stackoverflow.com/help/mcve, кроме того ... вы знаете, что есть много способов обхода деревьев? https://en.wikipedia.org/wiki/Tree_traversal – GhostCat
Я ясно проиллюстрировал это требование. –
из-за метода 'getChilds' возвращает' String'. Проблема, когда узел имеет более двух детей – Jerry06