java - 正确地从树中删除节点

Question

我有以下函数来修剪树数据结构:

public static void pruneTree(final ConditionTreeNode treeNode) {

    final List<ConditionTreeNode> subTrees = treeNode.getSubTrees();

    for (ConditionTreeNode current : subTrees) {
        pruneTree(current);
    }

    if(subTrees.isEmpty()) {
        final ConditionTreeNode parent = treeNode.getParent();
        parent.removeConditionTreeNode(treeNode);
    }

    if (treeNode.isLeaf()) {
        //this is the base case
        if (treeNode.isPrunable()) {
            final ConditionTreeNode parent = treeNode.getParent();
            parent.removeConditionTreeNode(treeNode);
        }
        return;
    }

}

我想知道修剪它的最佳方法是什么。我当前收到 ConcurrentModificationExceptions，并且我读到您可以复制集合，然后删除原始集合，或者从迭代器中删除。有人可以帮助我了解我需要做什么才能使此方法发挥作用吗？

Answer 1

问题是，您正在迭代节点集合，并在某些情况下从递归调用内的集合中删除实际项目。您可以从递归调用中返回一个 boolean 标志来指示要删除的实际项目，然后通过 Iterator.remove() 删除它(您需要将 foreach 循环更改为迭代器循环使这成为可能)。

用其唯一的子节点替换实际项目比较棘手 - 您可以定义一个自定义类以从递归方法调用中返回更多信息，但它开始变得尴尬。或者您可以考虑使用例如循环来替换递归调用一个堆栈。