使用递归过滤树

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#。该树由节点列表组成。

- John Soer

---

你的树是否有从节点设计出的某些结构？这一点不太清楚。 - Daniel Mošmondor

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

- Lucero

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

- Juliet

---

C＃代码很丑，但至少它是纯函数的（即不会对底层数据结构产生副作用） :) - Juliet

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

- John Soer

---

你能稍微详细解释一下吗，以保持父节点不变吗？ - Gaui