我正在尝试创建一个返回选定节点路径的 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)));
关于c# - 如何在给定条件的情况下从递归层次结构返回节点路径?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18716310/