在给定条件的情况下，如何从递归层次结构返回节点的路径？

David 发表于 Dev

大卫

我正在尝试创建一个linq扩展方法，该方法将路径返回到选定的节点。

节点Item4的路径将产生-{ Item1, Item2, Item4 }
节点Item3的路径将产生-{ Item1, Item3 }

public class Item
{
    public int Id { get; set; }
    public IList<Item> Items { get; set; }
}

Item1
    Item2
        Item4
    Item3

呼叫码

var path = myItem.Items
    .Path(e => e.Items, e => MyPredicateCondition())
    .ToList();

扩展方式

public static IEnumerable<T> Path<T>(
    this IEnumerable<T> source,
    Func<T, IEnumerable<T>> childrenSelector,
    Predicate<T> condition)
{
    if (source == null || !source.Any()) return default(T);

    var attempt = source.FirstOrDefault(t => condition(t));
    if (!Equals(attempt, default(T))) return attempt;

    var items = source.SelectMany(childrenSelector)
        .Path(childrenSelector, condition)
        .ToList();

    return attempt;
}

我的问题不是找到实际的节点，而是递归地返回节点将树备份到根节点。数据结构应保持原样-即，我不希望Item引用它parent item。

注意：由于我尝试以其他方式使用IEnumerable yields等，因此当前代码无法编译。

效率不是问题，因为它将用于3或4个层次的深层，每个层次仅包含几个项目。

懒惰

这是一个Stack基于简单的实现。

想法是将要检查的每个项目放在堆栈上，如果它不是我们要查找的路径的一部分，请从堆栈中将其删除，直到找到要查找的项目为止。

IEnumerable<T> Path<T>(IEnumerable<T> source,
                       Func<T, IEnumerable<T>> childrenSelector,
                       Func<T, bool> condition)
{
    var path = new Stack<T>();
    Path(source, childrenSelector, condition, path);
    return path.Reverse().ToList();
}                       
bool Path<T>(IEnumerable<T> source,
             Func<T, IEnumerable<T>> childrenSelector,
             Func<T, bool> condition,
             Stack<T> path)
{
    foreach (var item in source)
    {
        path.Push(item);
        if (condition(item) || Path(childrenSelector(item), childrenSelector, condition, path))
            return true;
        else
            path.Pop();
    }
    return false;
}

例子：

Item[] items = { new Item {Id = 1, Items = new List<Item> 
{ 
    new Item {Id = 2,  Items = new List<Item> {new Item { Id = 4, Items = new List<Item>()}}},
    new Item {Id = 3,  Items = new List<Item>()},
}}};

var path = Path(items, e => e.Items, e => e.Id == 4);

// prints '1 -> 2 -> 4'
Console.WriteLine(String.Join(" -> ", path.Select(i=>i.Id)));

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。