通过递归检查父子关系构建树型列表

本文关键字：构建 树型 列表 父子关系 检查 递归 | 更新日期: 2023-09-27 18:07:50

我有一个类，它有一个自己的列表，所以它可以在树结构中表示。

我正在拉这些类的一个扁平列表，并希望将其非扁平化。

public class Group
{
     public int ID {get;set;}
     public int? ParentID {get;set;}
     public List<Group> Children {get;set;}
}

我希望能够做以下事情

List<Group> flatList = GetFlatList() //I CAN ALREADY DO THIS
List<Group> tree = BuildTree(flatList);

与父组的ID属性相关的ParentID

编辑

为什么我返回一个列表而不是一个对象，这有些令人困惑。

我正在构建一个UI元素，它有一个项目列表，每个为什么有一个孩子。所以初始列表没有根节点。到目前为止，似乎所有的解决方案都不起作用。

这意味着我本质上需要一个使用Group类的树型结构列表

通过递归检查父子关系构建树型列表

我不知道为什么你想要你的BuildTree方法返回List<Group> -树需要有根节点，所以你应该期望它返回单个Group元素，而不是一个列表。

我将在IEnumerable<Group>上创建一个扩展方法: 
public static class GroupEnumerable
{
    public static IList<Group> BuildTree(this IEnumerable<Group> source)
    {
        var groups = source.GroupBy(i => i.ParentID);
        var roots = groups.FirstOrDefault(g => g.Key.HasValue == false).ToList();
        if (roots.Count > 0)
        {
            var dict = groups.Where(g => g.Key.HasValue).ToDictionary(g => g.Key.Value, g => g.ToList());
            for (int i = 0; i < roots.Count; i++)
                AddChildren(roots[i], dict);
        }
        return roots;
    }
    private static void AddChildren(Group node, IDictionary<int, List<Group>> source)
    {
        if (source.ContainsKey(node.ID))
        {
            node.Children = source[node.ID];
            for (int i = 0; i < node.Children.Count; i++)
                AddChildren(node.Children[i], source);
        }
        else
        {
            node.Children = new List<Group>();
        }
    }
}
使用

var flatList = new List<Group>() {
    new Group() { ID = 1, ParentID = null },    // root node
    new Group() { ID = 2, ParentID = 1 },
    new Group() { ID = 3, ParentID = 1 },
    new Group() { ID = 4, ParentID = 3 },
    new Group() { ID = 5, ParentID = 4 },
    new Group() { ID = 6, ParentID = 4 }
};

var tree = flatList.BuildTree();

你可以这样做:

static void BuildTree(List<Group> items)
{
    items.ForEach(i => i.Children = items.Where(ch => ch.ParentID == i.ID).ToList());
}

你可以这样称呼它:

BuildTree(flatList);

如果最后你想获得父节点为null的节点(即顶级节点)，你可以简单地这样做:

static List<Group> BuildTree(List<Group> items)
{
    items.ForEach(i => i.Children = items.Where(ch => ch.ParentID == i.ID).ToList());
    return items.Where(i => i.ParentID == null).ToList();
}

如果你想让它成为一个扩展方法，你可以在方法签名中添加this:

static List<Group> BuildTree(this List<Group> items)

那么你可以这样调用它:

var roots = flatList.BuildTree();

我尝试了建议的解决方案，发现它们给我们带来了大约O(n^2)的复杂度。

在我的情况下(我有大约50,000个项目要构建到树中)，这是完全不可接受的。

我得到了以下解决方案(假设每个项只有一个父项，并且所有父项都存在于列表中)复杂度为O(n*log(n)) [n乘以getById, getById具有O(log(n))复杂度]:

static List<Item> BuildTreeAndReturnRootNodes(List<Item> flatItems)
{
    var byIdLookup = flatItems.ToLookup(i => i.Id);
    foreach (var item in flatItems)
    {
        if (item.ParentId != null)
        {
            var parent = byIdLookup[item.ParentId.Value].First();
            parent.Children.Add(item);
        }
    }
    return flatItems.Where(i => i.ParentId == null).ToList();
}

完整代码片段:

class Program
{
    static void Main(string[] args)
    {
        var flatItems = new List<Item>()
        {
            new Item(1),
            new Item(2),
            new Item(3, 1),
            new Item(4, 2),
            new Item(5, 4),
            new Item(6, 3),
            new Item(7, 5),
            new Item(8, 2),
            new Item(9, 3),
            new Item(10, 9),
        };
        var treeNodes = BuildTreeAndReturnRootNodes(flatItems);
        foreach (var n in treeNodes)
        {
            Console.WriteLine(n.Id + " number of children: " + n.Children.Count);
        }
    }
    // Here is the method
    static List<Item> BuildTreeAndReturnRootNodes(List<Item> flatItems)
    {
        var byIdLookup = flatItems.ToLookup(i => i.Id);
        foreach (var item in flatItems)
        {
            if (item.ParentId != null)
            {
                var parent = byIdLookup[item.ParentId.Value].First();
                parent.Children.Add(item);
            }
        }
        return flatItems.Where(i => i.ParentId == null).ToList();
    }
    class Item
    {
        public readonly int Id;
        public readonly int? ParentId;
        public Item(int id, int? parent = null)
        {
            Id = id;
            ParentId = parent;
        }
        public readonly List<Item> Children = new List<Item>();
    }
}

      public class Item {
      public readonly int Id;
      public readonly int ? ParentId;
      public Item(int id, int ? parent = null) {
        Id = id;
        ParentId = parent;
      }
      public readonly List < Item > Children = new List < Item > ();
    }
    public class BuildTree {
      public static List < Item > BuildTreeAndReturnRootNodes(List < Item > flatItems) {
        var byIdLookup = flatItems.ToLookup(i => i.Id);
        foreach(var item in flatItems) {
          if (item.ParentId != null) {
            var parent = byIdLookup[item.ParentId.Value].First();
            parent.Children.Add(item);
          }
        }
        return flatItems.Where(i => i.ParentId == null).ToList();
      }
    }
    public class TreeToFlatternBack {
      public static IEnumerable < Item > GetNodes(Item node) {
        if (node == null) {
          yield
          break;
        }
        yield
        return node;
        foreach(var n in node.Children) {
          foreach(var innerN in GetNodes(n)) {
            yield
            return innerN;
          }
        }
      }
    }
    class Program {
      static void Main(string[] args) {
        var flatItems = new List < Item > () {
          new Item(1),
            new Item(2),
            new Item(3, 1),
            new Item(4, 2),
            new Item(5, 4),
            new Item(6, 3),
            new Item(7, 5),
            new Item(8, 2),
            new Item(9, 3),
            new Item(10, 9),
        };
        Console.WriteLine();
        Console.WriteLine("--------------------Build a Tree--------------------");
        Console.WriteLine();
        var treeNodes = BuildTree.BuildTreeAndReturnRootNodes(flatItems);
        foreach(var n in treeNodes) {
          Console.WriteLine(n.Id + " number of children: " + n.Children.Count);
        }
        Console.WriteLine();
        Console.WriteLine("--------------------Tree Back to Flattern--------------------");
        Console.WriteLine();
        List < Item > BackToflatItems = new List < Item > ();
        foreach(var item in treeNodes) {
          BackToflatItems.AddRange(TreeToFlatternBack.GetNodes(item));
        }
        foreach(var n in BackToflatItems.OrderBy(x => x.Id)) {
          Console.WriteLine(n.Id + " number of children: " + n.Children.Count);
        }
      }
    }
相关文章：