删除树结构中没有特定子节点的节点

Question

我有一个像这样的树结构：

public class Project {
    private String id;
    private String description;
    private List<Project> subProjects;
    private List<Document> documents;
}

List<Project> projects = new ArrayList<Project>;

项目可以有子项目或文件，但不能同时有。我的问题是试图通过从列表中删除没有文档的每个项目或子项目来过滤此列表。所以如果项目没有文档也没有子项目，或者如果他的 none 个子项目有文档，我们删除该项目。

是否可以递归完成？

Answer 1

如果你能保证一个树结构，即没有循环，你只需要一个简单的post-order DFS。

如果您不想修改 Project class，请在过滤器函数中创建一个 HashMap，（键：项目，值：其子树中的文档总数。）

现在，map[P] = sum of all map[child] + number of documents in P当child在P的子项目变量中。

就是这样，甚至不需要边缘条件检查。它应该适用于任意数量的 sub-projects 或 P 下的文档，包括其中之一必须为 0 的条件。

Answer 2

直接解释你的条件A. remove if subProjects and documents are empty或B. all children have no documents（假设"none of his subprojects have documents"表示所有children，而不只是直接children）

定义一个布尔函数通常有助于检查节点的状态，然后可以查询它以检查是否应该删除该节点

该代码假定您将其放入 Project，否则您需要将其作为参数传递

boolean isEmpty()
{
    return subProjects.isEmpty() && documents.isEmpty();
}

boolean isChildrenEmpty()
{
    //put before the recursion for speed
    if(!documents.isEmpty()) //check if self has documents
        return false;

    for(Project child : subProjects)
        if(!child.isChildrenEmpty()) //check if any child has documents
            return false;

    return true; //all children + self have no documents
}

boolean toRemove()
{
    if(isEmpty()) //no children, no documents
        return true;

    for(Project child : subProjects)
        if(!child.isChildrenEmpty()) //a child has a document
            return false;
    return true;
}

删除树结构中没有特定子节点的节点

Removing nodes without a particular subnode in a tree structure

java

tree

tree-structure