Возвращаемый список узлов Дерево в Java-Parent может иметь несколько дочерних узлов

Question

Я пытаюсь написать код Java, чтобы вернуть список узлов в дереве.Дерево выглядит как

Класс узла -

class Node{
 String label;
 List<Node> children;
}

Я пытаюсь таким образом.Но не в состоянии понять, как написать цикл для перемещения.

    public List<Node> returnAllNodes(Node node){
    List<Node> listOfNodes = 
        new ArrayList<Node>();
    boolean iterationCompleted = false;
    if(node==null){
        return null;
    }
    while(!iterationCompleted){
    if(node.getChildren()==null){
        listOfNodes.add(node);
                    break;    
    }
            else{
               //
            }
    }
    return null;
    //return traverseAndReturnAllNodes(node.getChildren().get(0));
}

Пожалуйста, помогите.

Answer 1

Если вы уверены, что структура является деревом (узел не может иметь более одного родителя), это перечислит узлы в порядке глубины:

public static List<Node> returnAllNodes(Node node){
    List<Node> listOfNodes = new ArrayList<Node>();
    addAllNodes(node, listOfNodes);
    return listOfNodes;
}

private static void addAllNodes(Node node, List<Node> listOfNodes) {
    if (node != null) {
        listOfNodes.add(node);
        List<Node> children = node.getChildren();
        if (children != null) {
            for (Node child: children) {
                addAllNodes(child, listOfNodes);
            }
        }
    }
}

Если узлы могут иметь несколько родителей, измените первую строку addAllNodes на:

    if (node != null && !listOfNodes.contains(node)) {

Алгоритм в ширину выглядит следующим образом:

public static List<Node> returnAllNodes(Node node){
    List<Node> listOfNodes = new ArrayList<Node>();
    if (node != null) {
        listOfNodes.add(node);
        for(int i = 0; i < listOfNodes.size(); ++i) {
            Node n = listOfNodes.get(i);
            List<Node> children = n.getChildren();
            if (children != null) {
                for (Node child: children) {
                    if (!listOfNodes.contains(child)) {
                        listOfNodes.add(child);
                    }
                }
            }
        }
    }
    return listOfNodes;
}

Answer 2

Вы можете использовать Поиск в ширину или Поиск в глубину .