c# - 如何在原地行走和过滤一棵树？

Question

给定一棵由下面的类和数据定义的复杂对象树，有没有一种方法可以在适当的位置遍历树，应用过滤器，这样我就不会不必要地克隆我的树对象。

• 出于发布目的我已经简化了该类，但我们假设由于树节点的复杂性，在内存中克隆对象将是一个负担。
• 这将在多线程环境中调用，因此让我们假设删除节点或设置树本身的属性会导致问题。

我不是在寻找 BFS 或 DFS 遍历，因为我想保留树结构。这个

类:

public class Menu
{
    public string Text { get; set; }
    public IEnumerable<Menu> Children { get; set; }
}

示例输入:

Root| A1| | A2| | B1| C1| | A3| | | A4| | B2| D1| | B3

Given a filter for 'A', the desired result should include every node that is either an 'A' itself or contains an 'A':

Root| A1| | A2| C1| | A3| | | A4

I have attempted a view different methods with recursive functions and IEnumerable functions, but I can't figure out how to pass the iterator into the children, without modifying the Menu instance.

private IEnumerable<Menu> BuildMenu(Menu menu)
{
    foreach (var i in menu.Children)
    {
        if (/* item is filtered*/)
            yield break;

        // How to pass in current iterator and criteria without NEW()'ing an object?
        yield return new Menu()
        {
            Text = menuWithChildren.Text,
            Children = BuildMenu(menuWithChildren)
        };
    }
}

这甚至可能吗，还是我的要求无效？感谢阅读。

Answer 1

为了“就地”过滤列表(即，不重建树/节点)，您可以向每个节点添加属性“IsVisible”并适本地设置值。

为了向下传递过滤逻辑，您可以使用 Func<Menu,bool> 形式的谓词作为过滤函数的参数。

这是一个递归过滤函数，它可以做到这一点:

private static bool Filter(Menu item, Func<Menu,bool> predicate)
{
    bool isVisible = predicate(item) ;
    bool isChildrenVisible = (item.Children != null && item.Children.Count(c => Filter(c,predicate))>0);
    item.IsVisible = isVisible || isChildrenVisible;
    return isVisible;
 }

可以这样调用:

Filter(tree, n => n.Text.StartsWith("A") );

我准备了一个实例来演示这一点:http://rextester.com/GCYV10964