使用递归过滤树

Question

我有一棵树，如下所示。

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

我想过滤这个返回

A1
  A2
    A3 
    A4        
  A5
  A6

基本思想是只返回 A 节点。我遇到的困难是在 A2 的情况下我想删除 B1 并将 A2 拉到 B2 的级别

我正在使用 c# 树由节点列表组成

Answer 1

您想要深度搜索（递归）并消除不是 A 的节点，对吗？

我会在返回时删除节点，将子节点插入到父节点（位于您当前所在节点的位置），然后每当您位于非 A 节点时删除该节点。

像这样的东西（简化的伪代码，在迭代节点集合时必须小心更改节点集合等）：

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

我假设您的树结构如下所示：

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