递归 Linq - Parent 指示 child 属性？

Question

我有一个 table（在这个例子中假设为数据表），它有层次结构记录（id、ParentId、IsEmergency）：

ParentId=0表示root.

所以我们有这个：

0
|
+--- 4706606
|
+--- 4706605
|
+--- 4666762
        |
        +--- 4668461
               |
               +--- 4706607

我只显示了那些 parentId=0

的记录

但我想添加另一个逻辑列，其中说明“此 parent 在其中一个 childs/sub 子项

中有 IsEmergency=true

所以我在

id         parentId        hasEmergencyInOneOfItsChild
-------------------------------------------------------
4706606    0                false
4706605    0                false
4666762    0                true

问题：

如何通过递归 linq 实现它？

为了方便，我创建了这个数据table :

   DataTable dt = new DataTable("myTable");
   dt.Columns.Add("id", typeof (int));
   dt.Columns.Add("parentId", typeof (int));
   dt.Columns.Add("isEmergency", typeof (bool));

   DataRow row = dt.NewRow();
   row["id"] =4706606;
   row["parentId"] = 0;
   row["isEmergency"] =false;
   dt.Rows.Add(row);

       row = dt.NewRow();
   row["id"] =4706605;
   row["parentId"] = 0;
   row["isEmergency"] = false;
   dt.Rows.Add(row);

       row = dt.NewRow();
   row["id"] =4666762;
   row["parentId"] = 0;
   row["isEmergency"] =false;
   dt.Rows.Add(row);

       row = dt.NewRow();
   row["id"] =4668461;
   row["parentId"] = 4666762;
   row["isEmergency"] = false;
   dt.Rows.Add(row);

        row = dt.NewRow();
   row["id"] =4706607;
   row["parentId"] = 4668461;
   row["isEmergency"] = true;
   dt.Rows.Add(row);

~~我试过一些东西，但它很讨厌而且效率不高~~

Answer 1

一种方法是定义一个包含相关属性的数据结构和一个递归属性以确定它是否在 isEmergency 层次结构中：

internal class Node
{
    internal string Id { get; set; }
    internal IEnumerable<Node> Children { get; set; } 
    internal bool IsEmergency { get; set; }

    internal bool IsEmergencyHierarchy
    {
        get { return IsEmergency || 
                     (Children != null && Children.Any(n => n.IsEmergencyHierarchy)); }
    }
}

那么你可以这样构建树：

// convert rows to nodes
var nodes = dt.Rows.Cast<DataRow>().Select(r => new Node
{
    Id = r["id"].ToString(),
    ParentId = r["parentId"].ToString(),
    IsEmergency = (r["isEmergency"] as bool? == true)
}).ToList();

// group and index by parent id
var grouped = nodes.GroupBy(n => n.ParentId).ToDictionary(g => g.Key);

// match up child nodes
foreach (var n in nodes)
{
    n.Children = grouped.ContainsKey(n.Id) 
        ? (IEnumerable<Node>)grouped[n.Id] 
        : new Node[0];
}

// select top nodes
var top = grouped.ContainsKey("0") 
    ? (IEnumerable<Node>)grouped["0"] 
    : new Node[0];

您可以这样查看结果：

foreach (var t in top)
{
    Console.WriteLine("{0} - {1}", t.Id, t.IsEmergencyHierarchy);
}

输出：

4706606 - False
4706605 - False
4666762 - True

Answer 2

鉴于您的数据：

var lookup = dt.Rows.Cast<DataRow>().Select(x => new
{
    id = (int)x["id"],
    parentId = (int)x["parentId"],
    isEmergency = (bool)x["isEmergency"],
}).ToLookup(x => x.parentId);

我通过 parentid 构建了一个查找 "sorted"（假设它就像一本字典，但每个键都有多个值）

// Taken from 
public static IEnumerable<T> SelectSelfDescendents<T>(IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
{
    foreach (var item in source)
    {
        yield return item;

        foreach (T item2 in SelectSelfDescendents(selector(item), selector))
            yield return item2;
    }
}

一个递归函数return递归输入集合加上后代

var roots = lookup[0].Select(x => new
{
    x.id,
    // x.parentId // useless, it's 0
    isEmergency = SelectSelfDescendents(new[] { x }, y => lookup[y.id]).Any(y => y.isEmergency),
    childs = SelectSelfDescendents(new[] { x }, y => lookup[y.id]).ToArray()
}).ToArray();

一点 Linq 来处理一切:-)

lookup[0]

我们从 "root" 个元素开始（parentId == 0 的元素）

这个

.SelectSelfDescendents(new[] { x }, y => lookup[y.id])

给定一个 ienumerable returns ienumerable 加上它的所有递归子项。

new[] { x }

转换单个元素集合中的 "current" 根元素。

y => lookup[y.id]

这是一个后代选择器：给定一个元素，它在查找中找到所有以 y.id 作为父项的子项（因为查找是按 parentId）

所以最后 SelectSelfDescendents 将 return new[] { x } 与其所有 "descendents"

连接

.Any(y => y.isEmergency)

如果任何 isEmergency 是 true returns true

现在，正如您所注意到的，我正在重新计算 SelectSelfDescendants 两次（一次用于 isEmergency，一次用于 childs）...实际上 childs 是一个属性我已将递归枚举添加到 "debug" 中，因此如果不需要，可以将其删除。如果你想保留它，你可以使用 let 关键字（或 "expand" let 关键字，就像你在聊天中显示的那样......这是一回事）。请注意，我 "cache" SelectSelfDescendents 和 .ToArray() （就像你所做的那样）。没有它，它仍然会被计算两次，因为它 return 是一个 IEnumerable<>

var roots = (from x in lookup[0]
             let childs = SelectSelfDescendents(new[] { x }, y => lookup[y.id]).ToArray()
             select new
             {
                 x.id,
                 // x.parentId // useless, it's 0
                 isEmergency = childs.Any(y => y.isEmergency),
                 childs 
             }).ToArray();

递归 Linq - Parent 指示 child 属性？

Recursive Linq - Parent indication for child property?

c#

linq

recursion