Filtrer un arbre en utilisant la récursivité

Question

J'ai un arbre qui apparaît comme suit.

 
A1 
    B1 
    B2 
    A2 
     A3 
     B3 
     A4   
    A5 
    C1 
    C2 
     C3 
     A6 

Je veux filtrer ce pour retourner

 
A1 
    A2 
    A3 
    A4   
    A5 
    A6 

L'idée de base est de ne retourner que A nœuds. La lutte que j'ai est dans le cas A2 je veux déposer B1 et tirer A2 au niveau B2

J'utilise C# L'arbre est composé de la liste des noeuds

Answer 1

Vous voulez de une recherche en profondeur (récursion) et éliminer les nœuds qui ne sont pas de A, non? Je supprimerais les noeuds au retour, en insérant les enfants au parent (à la position du noeud où vous vous trouvez actuellement), puis en supprimant ce noeud lorsque vous êtes sur un noeud non-A.

Quelque chose comme ceci (pseudo-code simplifié, vous devez faire attention à l'évolution des collections de nœuds alors qu'ils sont réitérés, etc.):

void FilterNode(Node node) { 
    foreach (Node child in node.Children) { 
     FilterNode(child); 
    } 
    if (node.Type != NodeType.A) { 
     foreach (Node child in node.Children) { 
      node.Parent.InsertAfter(node, child); 
     } 
     node.Parent.RemoveNode(node); 
    } 
} 

Answer 2

C'est la solution que je suis venu avec avant d'avoir vu la solution de Lucero

private List<NodesEntity> ReturnHierarchyFilteredByType(List<NodesEntity> nodesEntities, List<String> nodeTypes) 
{ 
    List<NodesEntity> _nodesEntities = new List<NodesEntity>(); 
    foreach (NodesEntity _nodesEntity in nodesEntities) 
    { 
    //We first recurse to the bottom 
    List<NodesEntity> _childNodesEntities = ReturnHierarchyFilteredByType(_nodesEntity.ChildNodes, nodeTypes); 

    if (nodeTypes.Contains(_nodesEntity.Type)) 
    { 
     //The node matches what we have in the list 
     _nodesEntities.Add(_nodesEntity); 
     _nodesEntity.ChildNodes = _childNodesEntities; 
    } 
    else 
    { 
     //We pull the child nodes into this level 
     _nodesEntities.AddRange(_childNodesEntities); 
    } 
    } 

    return _nodesEntities; 
} 

Answer 3

Je vais supposer que la structure de votre arbre ressemble à ceci:

class Node<T> { 
    public readonly T Value; 
    public readonly LinkedList<Node<T>> Children; 
    public readonly bool IsEmtpy; 

    public Node() { 
     IsEmpty = true; 
    } 

    public Node(T value, LinkedList<Node<T>> children) { 
     Value = value; 
     Children = children; 
     IsEmpty = false; 
    } 
} 

Vous pouvez filtrer votre arbre en un seul passage avec une première recherche en profondeur.

Je trouve généralement plus facile de prototyper ces sortes d'algorithmes dans un langage fonctionnel, puis de les traduire en C# lorsque cela est nécessaire. Voici le code F #:

type 'a tree = Nil | Node of 'a * 'a tree list 

// val filter : ('a -> bool) -> 'a tree list -> 'a tree list 
let rec filter f = function 
    | Node(value, children)::xs -> 
     if f value then Node(value, filter f children)::filter f xs 
     else (filter f children) @ filter f xs 
    | Nil::xs -> filter f xs 
    | [] -> [] 

let input = 
    Node("A1", 
     [ Node("B1", 
      [ Node("B2", []); 
       Node("A2", 
       [ Node("A3", []); 
        Node("B3", [ Node("A4", []) ]) ]) ]); 
      Node("A5", []); 
      Node("C1", 
      [ Node("C2", 
       [Node("C3", [ Node("A6", []) ]) ]) ]) ]) 

let expectedOutput = 
    Node("A1", 
     [ Node("A2", 
      [ Node("A3", []); 
       Node("A4", []) ]); 
      Node("A5", []); 
      Node("A6", []) ]) 

let actualOutput = [input] |> filter (fun value -> value.StartsWith("A")) |> List.head 

let testPasses = expectedOutput = actualOutput 

Et la sortie F #:

val testPasses : bool = true 

Et voici le code équivalent en C#:

static LinkedList<Node<T>> Filter(Func<T, bool> predicate, IEnumerable<Node<T>> input) { 
    var res = new LinkedList<Node<T>>(); 

    foreach(Node<T> node in input) { 
     if (!node.IsEmpty) { 
      if (predicate(node.Value)) { 
       res.AddLast(new Node(node.Value, Filter(predicate, node.Children)); 
      else { 
       res.AddRange(Filter(predicate, node.Children)); 
      } 
     } 
    } 

    return res; 
}