使用LINQ表达式创建树形结构

Question

我有一个C#列表，其中包含存储过程返回的以下字段：

CarrierId   ParentCarrierId Name Descrition
1            NULL            A         AA
2              1             B         BB
3              1             C         CC
4              3             D         DD
5            NULL            E         EE

我需要根据这个输出构建一个嵌套的对象列表

因此，每个Carrier对象都应该有其所有子项的列表。 有谁能帮助我构建一个LINQ代码以实现此目的？

期望的结果：

 CarrierId = 1
      |__________________ CarrierId = 2
      |__________________ CarrierId = 3
                              |___________________ CarrierId = 4

 CarrierId = 5

期望的结果应如上所述。

- InTheWorldOfCodingApplications

---

这个表有多少行？它可以使用Linq-To-Objects吗？如果不行，你使用的是哪个LINQ提供程序？ - Tim Schmelter

这是存储过程返回的输出，以List<Carrier>的形式呈现。 - InTheWorldOfCodingApplications

它可以有多深，只有一层还是无限制的？ - Tim Schmelter

没有限制，但大多数情况下不超过3级。需要将其视为N级别。 - InTheWorldOfCodingApplications

Answer 1

首先创建一个查找表，将父ID映射到其子项：

var lookup = carriers.ToLookup(carrier => carrier.ParentCarrierId);

遍历每个节点，并根据查找结果为其分配子节点：

foreach(var carrier in carriers)
    carrier.Children = lookup[carrier.CarrierId];

要获取所有根节点，只需从查找中获取空值即可：

var roots = lookup[null];

注意，整个操作的时间复杂度为O(n)，因为构建查找表的时间复杂度为O(n)，而每个载体的所有子项可以在O(n)的时间内找到，而非像其他已发布的解决方案那样需要O(n^2)的时间（因为它们使用O(n)的操作来查找单个节点的所有子项）。这使得此代码比其他选项更快，而且更加简单和短小。

- Servy

---

由于CarrierId是主键，您正在将每个运营商映射到其自身。 - Tim Schmelter

@TimSchmelter是正确的。当您创建查找表时，必须提供carrier.ParentCarrierId作为查找键。除了这个错误之外，这是一个非常好的解决方案。 - Good Night Nerd Pride

@TimSchmelter 这将获取每个项的所有直接后代，并将它们分配为该项的子项。这样做会创建一个与问题描述中相同的树形结构。 - Servy

另外，为了使这个答案更好，我建议将“lookup”重命名为更有意义的名称，比如“childrenOf”。 - Good Night Nerd Pride

@Servy，从对象的类型签名和使用ToLookup()创建它的事实可以清楚地看出它是一个查找表。变量的类型不应该成为其名称的一部分。我只是认为，如果符号名称表达其意图而不是其类型，那么您的完全正确的答案对于新手来说更容易理解。无论意图是以符号的定义属性还是如何被操作来表达，都是次要的。 - Good Night Nerd Pride

Answer 2

请尝试这个。

 class Program
    {
        static void Main(string[] args)
        {
            IList<Carrier> CarrierList = new List<Carrier>();
            CarrierList.Add(new Carrier { CarrierId = 1, Name = "A", Description = "AA", ParentCarrierId = null });
            CarrierList.Add(new Carrier { CarrierId = 2, Name = "B", Description = "BB", ParentCarrierId = 1 });
            CarrierList.Add(new Carrier { CarrierId = 3, Name = "C", Description = "CC", ParentCarrierId = 1 });
            CarrierList.Add(new Carrier { CarrierId = 4, Name = "D", Description = "DD", ParentCarrierId = 3 });
            CarrierList.Add(new Carrier { CarrierId = 5, Name = "E", Description = "EE", ParentCarrierId = null });
            Temp temp = new Temp();
        IList<Carrier> CarrierList1=new List<Carrier>(); 
             foreach (Carrier carrier in CarrierList.Where(p => p.ParentCarrierId == null).ToList() )
            {
                CarrierList1.Add(temp.Recursive(carrier, CarrierList));
            }
        }
    }
    public class Temp
    {
        public Carrier Recursive(Carrier carrier,IList<Carrier> carrierList)
        {

            if (carrierList.Where(c => c.ParentCarrierId == carrier.CarrierId).Count() <1)
            {
                return carrier ;
            }
            else
            {
                IList<Carrier> newList = new List<Carrier>();
                foreach (Carrier ca in carrierList.Where(c => c.ParentCarrierId == carrier.CarrierId)){
                    newList.Add(Recursive(ca, carrierList));
            }
                carrier.CarrierList = newList;
                return carrier;
            }
        }
    }
    public class Carrier
    {
        public int CarrierId { get; set; }
        public string Name { get; set; }
        public string Description { get; set; }
        public int? ParentCarrierId { get; set; }
        public IList<Carrier> CarrierList { get; set; }
    }
}

- Nithila Shanmugananthan

Answer 3

你最初的问题有些不同。我认为每个载体都应该持有其所有后代的列表。现在看来，你只想持有所有直接子代。那很简单：

c.Children = carrierList.Where(child => child.ParentCarrierId == c.CarrierId).ToList();

如果您希望将其作为LINQ查询，则必须创建Carrier的新实例：

List<Carrier> rootCarriers = carrierList
    .Select(c => new Carrier { 
        CarrierId = c.CarrierId,
        Name = c.Name,
        Descrition = c.Descrition,
        ParentCarrierId = c.ParentCarrierId,
        Children = carrierList
            .Where(child => child.ParentCarrierId == c.CarrierId)
            .ToList()
    })
    .Where(c => !c.ParentCarrierId.HasValue)
    .ToList(); 

那个查询还会移除所有没有父级的非根载体。 下面展示了两种不同属性的方法，Children和Descendants，后者甚至返回孙子等更多后代。

public class Carrier
{
    public List<Carrier> Descendants { get; set; }
    public List<Carrier> Children { get; set; }

    public static IEnumerable<Carrier> TraverseDescendants(IEnumerable<Carrier> allCarriers, Carrier rootCarrier)
    {
        Queue<Carrier> queue = new Queue<Carrier>();
        var children = allCarriers.Where(c => c.ParentCarrierId == rootCarrier.CarrierId);
        foreach (Carrier c in children)
            queue.Enqueue(c);
        while (queue.Count > 0)
        {
            Carrier child = queue.Dequeue();
            yield return child;
            var grandchildren = allCarriers.Where(c => c.ParentCarrierId == child.CarrierId);
            foreach (Carrier c in grandchildren)
                queue.Enqueue(c);
        }
    }
}

使用TraverseDescendents，您可以初始化类中的List<Carrier> Descendents。 Children列表是一个简单的LINQ查询：

foreach (Carrier c in carrierList)
{
    c.Descendants = Carrier.TraverseDescendants(carrierList, c).ToList();
    c.Children = carrierList.Where(child => child.ParentCarrierId == c.CarrierId).ToList();
}

- Tim Schmelter

---

@在编程应用的世界中: 是的，您想要什么结果？ 您的要求是_"因此，每个Carrier对象都应该有其所有子项的列表"_。 在您的问题中提供所需的结果可能会有所帮助。 我的解决方案提供了一种获取所有Carrier子项的方法。 - Tim Schmelter

@在编程应用的世界中：我不知道你想要实现什么。请在你的问题中提供所需的结果。 - Tim Schmelter

@在编程应用的世界中：但是这个“分层方式”的集合是什么样的呢？由于每个“Carrier”都持有其子项列表，因此您甚至现在可以使用我的方法遍历子项。因此，“List<Carrier>”包含所有扁平化的载体子项，但是如果您想向下到达孙子等，则只需查看子项的“Children”属性即可。 - Tim Schmelter

我来举个例子：如果您有一个ID为1的承运人，则“Children”属性将返回一个包含ID为2、3和4的三个承运人的“List<Carrier>”。但是，如果您查看列表中的第一个承运人（即carrier2）及其“Children”属性，则它仅包含一个承运人，即carrier4，即carrier1的孙子。您是否希望carrier1仅包含2和3而不是4，因此只有直接祖先？ - Tim Schmelter

这仍然返回所有对象而不是嵌套结构。抱歉，我漏掉了什么。 - InTheWorldOfCodingApplications

Answer 4

如果您在 Carrier 类中添加一个公共的 public List<Carrier> Children { get; set; } 属性，那么这将适用于内存中的 Carrier 枚举。

public static class CarrierExt
{

    public static List<Carrier> AsTree(this IEnumerable<Carrier> carriers)
    {
        return carriers.AsTree(null);
    }

    private static List<Carrier> AsTree(this IEnumerable<Carrier> carriers, int? parentId)
    {
        return (from carrier in carriers
                where carrier.ParentCarrierId == parentId
                let children = carrier.Children = carriers.AsTree(carrier.CarrierId)
                select carrier).ToList();
    }
}

编辑：请注意，这将仅将顶级列表减少为仅包含2个根元素。

- Lorentz Vedeler