平面列表 到结构化列表通过 C# 中的递归

本文关键字：列表 递归 平面 结构化 通过 | 更新日期: 2023-09-27 18:33:51

我有一个现有的类： 

public class Product
{
 public int Id { get; set; }
 public int ParentId { get; set; }
 public string Info { get; set; }
}

我还有一个给定的List<Product>： 

var Lst = new List<Product>();
Lst.Add(new Product{ Id=1,ParentId=0,Info="a"});
Lst.Add(new Product{ Id=2,ParentId=0,Info="a"});
Lst.Add(new Product{ Id=3,ParentId=0,Info="a"});
Lst.Add(new Product{ Id=60,ParentId=1,Info="a"});
Lst.Add(new Product{ Id=61,ParentId=1,Info="a"});
Lst.Add(new Product{ Id=62,ParentId=61,Info="a"});
Lst.Add(new Product{ Id=72,ParentId=61,Info="a"});
Lst.Add(new Product{ Id=90,ParentId=2,Info="a"});

可视化： 

1
|
+---60
|
+---61
     |
     +---62
     |
     +---72
2
|
+---90
3

如您所见，List<>是平坦的。（所有项目在列表中都处于同一级别，只是id,parentId代表继承制）

现在 - 我需要创建结构List<>以便List中的每个项目都将位于其父对象内：

所以我创建了一个额外的结构类来保存这个结构： 

public class Node
{
 public Product Product { get; set; }
 public List<Node> LstNodes  { get; set; }
}

所以现在我可以做： 

List<Node> lstNodes = new List<Node>();

最初我可以添加根的： 

lstNodes=Lst.Where(product=>product.ParentId==0).Select(node=>new Node{Product=node}).ToList();

现在我可以开始递归以插入带有父项的项目。

那么问题出在哪里呢？

问题：

我想避免先插入根元素（根是ParentId=0的地方）。

有没有办法用一种递归方法（包括根）做到这一点？

期望结果：lstNodes 3 个节点，每个节点都有递归的子节点。

平面列表<T> 到结构化列表<T>通过 C# 中的递归

像这样的东西？

List<Node> GetNodes(List<Product> lst, int parentId = 0)
{
    var childProducts = lst.Where(x=>x.ParentId == parentId);
    return childProducts
           .Select(x=> new Node { Product = x, LstNodes = GetNodes(lst, x.Id)}
           .ToList();
}

和纯通用版本：

class Node<T>
{
    public T Item { get; set; }
    public List<Node<T>> LstNodes  { get; set; }
}
List<Node<T>> GetNodes<T>(List<T> lst, Func<T, int> idSelector, Func<T, int> parentIdSelector, int parentId = 0)
{
    var childProducts = lst.Where(x=>parentIdSelector(x) == parentId);
    return childProducts
           .Select(x=> new Node<T> { Item = x, LstNodes = GetNodes<T>(lst, idSelector,parentIdSelector, idSelector(x))})
           .ToList();
}
GetNodes(Lst,x=>x.Id,x=>x.ParentId, 0);

你可以试试这个：

    static List<Node> BuildTree(List<Product> lst, int topID) 
    {
        var tree = Enumerable.Empty<Node>().ToList();
        if (lst == null)
        {
            return tree;
        }
        foreach (var product in lst)
        {
            if (product.ParentId == topID)
            {
                Node node = new Node 
                {
                    Product = product,
                    LstNodes = BuildTree(lst.Where(p => p.ParentId == product.Id).ToList(), product.Id)
                };
                tree.Add(node);
            }
        }
        return tree;
    }

你可以打电话： List<Node> roots = BuildTree(Lst, 0);

到目前为止提出的解决方案有效，但每个节点遍历整个集合一次。
这使得它们成为 O（n2），不适合大型集合（数据库等）。
下面是一个线性时间运行的解决方案：

var products = new List<Product>();
products.Add(...);
...
var nodes          = products.Select(p => new Node { Product = p }).ToList(); // 1
var nodeWithId     = nodes.ToDictionary(n => n.Product.Id);                   // 2
var parentChildren = nodes.Where(n => n.Product.ParentId != 0)
                          .ToLookup(n => nodeWithId[n.Product.ParentId]);     // 3
foreach (var pc in parentChildren)  // 4
{
    var parent   = pc.Key;
    var children = pc.ToList();
    parent.LstNodes = children;
}

解释：

  1. 从产品创建节点。
  2. 创建一个字典，使我们能够轻松找到具有给定 id 的节点
  3. 创建一个查找（每个键有多个值的字典），为我们提供给定节点的子节点。
  4. 迭代查找，将孩子与父母关联起来
相关文章：