java - 迭代父子树结构的最佳算法

Question

我一次又一次地遇到这种情况，我有一个非常简单的解决方案，但我想知道还有哪些其他算法可能更干净、更易于维护。我的具体用例涉及处理数据管道，我将多次收到此结构并在完成后将其处置。我只需要迭代这个结构一次。

假设您有一个具有父子关系的树结构；这是一种没有界限的一对多关系。

public class Node {
    private String name;

    private Boolean resource;

    private Node parent;

    private List<Node> children;

    // getters and setters...
}

假设我想从根节点开始递归搜索这个结构，但是构建结构内所有节点的索引的开销大于其值(value)。我可能会写这样的东西:

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

让我们更改一下要求。现在我们想要收集符合特定条件的 Node 的 List。

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