Suppression de nœuds sans sous-noeud particulier dans une structure arborescente

Question

j'ai une structure arborescente comme celui-ci:

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

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

Les projets peuvent avoir des sous-projets ou des documents, mais pas les deux en même temps. Mon problème est d'essayer de filtrer cette liste en supprimant de chaque projet ou sous-projet qui n'a pas de documents. Nous supprimons donc le projet si le projet n'a pas de documents ni de sous-projets, ou si aucun de ses sous-projets n'a de document.

Cela peut-il être fait récursivement?

Answer 1

interprétation droite de vos conditions A. remove if subProjects and documents are empty ou B. all children have no documents(en supposant « aucun de ses sous-projets ont des documents » moyens tous les enfants, pas seulement les enfants directs)

Définition d'une fonction booléenne aide à vérifier souvent l'état d'un nœud, et peut ensuite interroger pour vérifier si le nœud doit être retiré

le code suppose que vous le mettre dans Project, si vous n'êtes pas vous aurez besoin de passer comme un argument

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

Answer 2

Si vous pouvez garantir une structure en arbre, c'est-à-dire sans cycle, tout ce dont vous avez besoin est un simple DFS après commande.

Si vous ne voulez pas modifier votre Project classe, en fonction de filtre créer une table de hachage (clé: projet, Valeur: nombre total de documents dans son sous-arbre.)

Maintenant, map[P] = sum of all map[child] + number of documents in P lorsque l'enfant est dans le sous-projet de P variable.

C'est vraiment, même pas de vérification de condition de bord est nécessaire. Il devrait travailler à un certain nombre de sous-projets ou documents sous P, y compris votre condition quand l'un d'entre eux doit être 0.