建造树类型列表通过递归检查父子关系C＃

问题描述 投票：0回答：4
我希望能够做以下

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

如果尚不明显的话，与其父组上的ID属性有关的parentID。 

eDit

对于为什么我要返回列表而不是一个对象，这有些困惑。 我正在构建一个具有项目列表的UI元素，每个都有一个孩子。因此，初始列表没有根节点。到目前为止，所有解决方案似乎都没有起作用。 
这意味着我本质上需要使用组类的树类型结构列表。

我不知道为什么要您

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>(); } } }
c# recursion tree
4个回答
51
投票

usage



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

    

    
    
    

    

        

            

                

                    
29
投票

                    
                

            

        

        



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




然后您可以这样称呼：



var roots = flatList.BuildTree();


    

我尝试了建议的解决方案，并发现他们给了我们关于O（n^2）复杂性的问题。


在我的情况下（我有大约50k的物品要内置在树上），这是完全不可接受的。


I提出了以下解决方案（假设每个项目只有一个父母，并且所有父母都存在于列表中）o（n*log（n））[n次getById，getById，getByID具有O（log（log（log（log（log）））复杂性]：
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();
}




Full代码片段：



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);
        }

      }
    }

    



    

    
    
    

    

        

            

                

                    
11
投票

                    
                

            

        

        
I需要做到这一点，并且我将分层数据存储在单个SQL表中。我有几个不同的类型/表可以执行此操作，因此在这里构建其他答案，我创建了一个通用版本。

由于嵌套的循环和反射，它的速度非常慢，但是我的数据集远至远。

希望这对某人有帮助。
datamodels：


namespace DataModels
{
  public class Tag
  {
    public int TagId { get; set; }
    public int? TagIdParent { get; set; }
    public string TagName { get; set; }
    public IEnumerable<Tag> Items { get; set; }
  } // end class

  public class Equipment
  {
    public int EquipmentId { get; set; }
    public int? EquipmentIdParent { get; set; }
    public string EquipmentName { get; set; }
    public string? EquipmentDescription { get; set; }
    public string? EquipmentPhotoUrl { get; set; }
    public IEnumerable<Equipment> Items { get; set; }
  } // end class
} // end namespace



logicBase（实施）：
using DataModels

namespace Logic
{
  public class LogicBase
  {
    public IEnumerable<T> BuildObjectTree<T>(List<T> data)
    {
      var id = $"{typeof(T).Name}Id";
      var idParent = $"{typeof(T).Name}IdParent";
            
      foreach (var dataItem1 in data)
      {
        var children = new List<T>();
                
        var dataItem1Id = dataItem1.GetType().GetProperty(id).GetValue(dataItem1);

        foreach (var dataItem2 in data)
        {
          var dataItem2Id = dataItem2.GetType().GetProperty(idParent).GetValue(dataItem2);

          if (dataItem1Id.Equals(dataItem2Id)) // == doesn't work here
          {
            children.Add(dataItem2);
          }
        }

        dataItem1.GetType().GetProperty("Items").SetValue(dataItem1, children);
      }

      var results = new List<T>();

      foreach (var dataItem3 in data)
      {
        var dataItem3IdParent = dataItem3.GetType().GetProperty(idParent).GetValue(dataItem3);
                
        if (dataItem3IdParent == null)
        {
          results.Add(dataItem3);
        }
      }
        
      return results;
    } // end
  } // end class
} // end namespace


logictag（用法）：


using Data;
using DataModels;

namespace Logic
{
  public interface ILogicTag
  {
     IEnumerable<Tag> RetrieveTags();
  }
 
  public class LogicTag(IDataTag dataTag) : LogicBase, ILogicTag
  {
    public IEnumerable<Tag> RetrieveTags()
    {
      var tags = dataTag.RetrieveTags().Result;
                
      return BuildObjectTree(tags.ToList());
    } // end
  } // end class
} // end namespace


    

    

    
    
    

    

        

            

                

                    
0
投票

                    
                

            

        

        

    

    


  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2025. All rights reserved.