Фильтровать дерево с помощью рекурсии

Question

У меня есть дерево, которое выглядит следующим образом.

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

Я хочу отфильтровать это, чтобы вернуть

A1
  A2
    A3 
    A4        
  A5
  A6

Основная идея - возвращать только узлы A. Я испытываю борьбу в случае А2, я хочу сбросить В1 и подтянуть А2 до уровня В2

.

Я использую c # Дерево состоит из списка узлов

Answer 1

Я предполагаю, что ваша древовидная структура выглядит следующим образом:

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

Вы можете отфильтровать ваше дерево за один проход с первым поиском на глубину.

Я обычно нахожупроще создавать прототипы таких алгоритмов на функциональном языке, а затем переводить их в C # при необходимости.Вот код 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

И вывод F #:

val testPasses : bool = true

А вот эквивалентный код в 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;
}

Answer 2

Вы хотите углубленный поиск (рекурсия) и исключить узлы, которые не являются А, верно?

Я бы удалил узлы на обратном пути, вставив дочерние элементы в родительский (в положении узла, в котором вы сейчас находитесь), а затем удалил бы этот узел всякий раз, когда вы находитесь на узле, отличном от А.

Примерно так (упрощенный псевдокод, вы должны быть осторожны с изменением коллекций узлов во время их повторения и т. Д.):

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 3

Это решение, которое я придумал до того, как увидел решение 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;
}