带有节点过滤的Java通用树遍历

Question

我有一个通用的树结构。我需要一个算法来遍历它，并删除一些不包含在给定列表中的叶子。如果所有的叶子都从子树中删除，那么也删除整个子树。

示例树：

         0
       / |  \
      1  2   3
    /  \ |  / \
   4   5 6  7  8

要保留的叶子：{4，6}

结果树：

         0
       / | 
      1  2 
    /    | 
   4     6  

输入数据结构包含在 HashMap 中，其中键是节点的父 ID，值是父节点正下方的节点列表（但不是递归所有子节点）。根节点的父 ID 为空字符串。

Map<String, List<Node>> nodes;

class Node {
    private String id;
    //other members
    //getters, setters
}

我想，某种递归DFS遍历算法应该可以工作，但我不知道它是如何工作的。

Answer 1

使用接口树：

public static interface Tree<T> {
    public T getValue();

    public List<Tree<T>> children();

    public default boolean isLeaf() {
        return children().isEmpty();
    }

    public default boolean removeDeadBranches(Predicate<T> testLiveLeaf) {
        if (isLeaf()) {
            return testLiveLeaf.test(getValue());
        }
        boolean remainLife = false;
        for (Iterator<Tree<T>> it = children().iterator(); it.hasNext();) {
            if (it.next().removeDeadBranches(testLiveLeaf)) {
                remainLife = true;
            } else {
                it.remove();
            }
        }
        return remainLife;
    }
}

Answer 2

我想，某种递归DFS遍历算法应该可以工作

完全正确。下面是你如何构建这个算法：

• 观察任务是否具有递归结构：将其应用于树的任何分支对分支的操作与要对整个树执行的操作相同
• 可以修剪分支，也可以完全删除分支
• 递归实现将返回修剪的分支;它将通过返回 null 来发出删除分支的信号。
• 递归函数将检查传入的节点
• 如果节点代表一个叶子，则其内容将根据我们希望保留的项目列表进行检查
• 如果叶子不在“保留列表”上，则返回 null;否则返回叶子
• 对于非叶枝，调用递归方法，并检查其结果
• 如果结果为 null，则从映射中删除相应的分支;否则，将分支替换为从调用返回的修剪分支
• 如果在检查所有分支时子节点的映射为空，则返回 null

请注意，如果没有任何叶节点与“keep”列表匹配，则该算法可能会返回 null。如果不希望这样做，请在递归实现的顶部添加一个额外的级别，并将顶层的 null return 替换为返回空树。

Answer 3

我建议您尝试以下方法：

方法布尔远程递归（String id， Set

首先，我们检查当前节点是否是叶子。如果叶子不在leavesTo保持集中，我们将其删除并返回true，否则返回false。这是我们递归的基本情况。

如果节点不是叶子，那么我们做这样的事情：

children.removeIf(n -> removeRecursively(n.id, leavesToKeep));

RemoveIF是一个方便的Java8方法，用于删除所有满足给定谓词的元素。这意味着只有当它的所有子级也被删除时，子级才会从列表中删除。因此，如果在children.removeIf调用子级列表为空时，我们应该使RemoveRecurely返回true：

if (children.isEmpty()) {
    tree.remove(id);
    return true;
} else return false;

完整的方法可能如下所示：

public static boolean removeRecursively(Map<String, List<Node>> tree, String id, Set<String> leavesToKeep) {
    List<Node> children = tree.get(id);
    if (children == null || children.isEmpty()) {
        if (!leavesToKeep.contains(id)) {
            tree.remove(id);
            return true;
        } else return false;
    }
    children.removeIf(n -> removeRecursively(tree, n.id, leavesToKeep));
    if (children.isEmpty()) {
        tree.remove(id);
        return true;
    } else return false;
}

其中tree是您描述的映射，id是开始节点id，leavesToKee是一组要保留的id。