Лучший алгоритм для перебора структуры родитель-потомок

Question

Я сталкиваюсь с этим снова и снова, и у меня есть очень простое решение, но мне интересно, какие другие алгоритмы могли бы быть более чистыми и более удобными в обслуживании. Мой конкретный c вариант использования включает в себя работу с конвейером данных, где я буду многократно получать эту структуру и распоряжаться ею после завершения работы. Мне нужно будет повторить эту структуру только один раз.

Скажем, у вас есть древовидная структура с отношениями родитель-потомок; это отношение один ко многим без границ.

public class Node {
    private String name;

    private Boolean resource;

    private Node parent;

    private List<Node> children;

    // getters and setters...
}

Допустим, я хочу рекурсивно искать эту структуру, начиная с узла root, НО создание индекса всех узлов в структуре требует больше ресурсов, чем это стоит Я мог бы написать что-то вроде этого:

private static Node getNodeByName(Node node, String name) {
    if (node.getName().equals(name)) {
        return node;

    } else if (!node.getChildren().isEmpty()) {
        for (Node node : node.getChildren()) {
            Node childNode;

            if ((childNode = getNodeByName(node, name)) != null) {
                return childNode;
            }
        }
    }

    return null;
}

Давайте изменим требование. Теперь мы хотим собрать List из Node, которые соответствуют определенным c критериям.

private static List<Node> getResourceNodes(Node node) {
    List<Node> matchedNodes = new ArrayList<>();
    SomeClass.getResourceNodes(node, matchedNodes);

    return matchedNodes;
}

private static void getResourceNodes(Node node, List<Node> matchedNodes) {
    if (node.isResource())) {
        matchedNodes.add(node);
    }

    if (!node.getChildren().isEmpty()) {
        for (Node node : node.getChildren()) {
            getResourceNodes(node, matchedNodes);
        }
    }
}

Я написал это прямо здесь. Там может быть синтаксическая ошибка или два. Мне интересно, какие еще способы, возможно что-то более ремонтопригодное, об этом можно было бы написать. Именно так я всегда подходил к связанным узлам, и теперь мне интересно узнать, есть ли лучший способ.

Answer 1

Если вы ищете более чистый и более понятный алгоритм, не пропускайте список через методы (построение списка вниз). Вместо этого создайте список вверх, вернув его.

private static List<Node> getResourceNodes(Node node) {

    List<Node> matchedNodes = new ArrayList<>();

    if (node.isResource()) matchedNodes.add(node);

    for (Node child : node.getChildren()) {
        matchedNodes.addAll(getResourceNodes(child);
    }

    return matchedNodes;
}

Answer 2

Для уточнения ответа Майкла я также добавил Predicate к параметру метода. Ради удобства обслуживания это также должно быть частью реализации Node.

public class Node {
    //...

    private List<Node> filter(Predicate<Node> filter) {

        List<Node> matchedNodes = new ArrayList<>();

        if (filter.test(this)) matchedNodes.add(node);

        for (Node child : node.getChildren()) {
            matchedNodes.addAll(node.filter(filter));
        }

        return matchedNodes;
    }
}