我假设你的树形结构长这样:
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;
}