53

我有类别列表：

╔════╦═════════════╦═════════════╗
║ Id ║ Name        ║ Parent_id   ║
╠════╬═════════════╬═════════════╣
║ 1  ║ Sports      ║ 0           ║
║ 2  ║ Balls       ║ 1           ║
║ 3  ║ Shoes       ║ 1           ║
║ 4  ║ Electronics ║ 0           ║
║ 5  ║ Cameras     ║ 4           ║
║ 6  ║ Lenses      ║ 5           ║
║ 7  ║ Tripod      ║ 5           ║
║ 8  ║ Computers   ║ 4           ║
║ 9  ║ Laptops     ║ 8           ║
║ 10 ║ Empty       ║ 0           ║
║ -1 ║ Broken      ║ 999         ║
╚════╩═════════════╩═════════════╝

每个类别都有一个父级。当 parent 为 0 - 这意味着它是根类别。

将其转换为如下树结构的最佳方法是什么？

Sport
 ├ Balls
 └ Shoes

Electronics
 ├ Cameras
 │  ├ Lenses
 │  └ Tripod
 │
 └ Computers
    └ Laptops

Empty

换句话说 - 如何从这个结构中获取数据：

class category
{
    public int Id;
    public int ParentId;
    public string Name;
}

进入这个：

class category
{
    public int Id;
    public int ParentId;
    public string Name;

    public List<Category> Subcategories;
}

以普遍的方式？// 通用意味着不仅适用于提到的类。

你有一些聪明的想法吗？;)

数据：

var categories = new List<category>() {
    new category(1, "Sport", 0),
    new category(2, "Balls", 1),
    new category(3, "Shoes", 1),
    new category(4, "Electronics", 0),
    new category(5, "Cameras", 4),
    new category(6, "Lenses", 5),  
    new category(7, "Tripod", 5), 
    new category(8, "Computers", 4),
    new category(9, "Laptops", 8),
    new category(10, "Empty", 0),
    new category(-1, "Broken", 999),
};
4

10 回答 10

70

如果你想拥有通用方法，你需要一个额外的类：

public class TreeItem<T>
{
    public T Item { get; set; }
    public IEnumerable<TreeItem<T>> Children { get; set; }
}

然后将它与这个助手一起使用：

internal static class GenericHelpers
{
    /// <summary>
    /// Generates tree of items from item list
    /// </summary>
    /// 
    /// <typeparam name="T">Type of item in collection</typeparam>
    /// <typeparam name="K">Type of parent_id</typeparam>
    /// 
    /// <param name="collection">Collection of items</param>
    /// <param name="id_selector">Function extracting item's id</param>
    /// <param name="parent_id_selector">Function extracting item's parent_id</param>
    /// <param name="root_id">Root element id</param>
    /// 
    /// <returns>Tree of items</returns>
    public static IEnumerable<TreeItem<T>> GenerateTree<T, K>(
        this IEnumerable<T> collection,
        Func<T, K> id_selector,
        Func<T, K> parent_id_selector,
        K root_id = default(K))
    {
        foreach (var c in collection.Where(c => EqualityComparer<K>.Default.Equals(parent_id_selector(c), root_id)))
        {
            yield return new TreeItem<T>
            {
                Item = c,
                Children = collection.GenerateTree(id_selector, parent_id_selector, id_selector(c))
            };
        }
    }
}

用法：

var root = categories.GenerateTree(c => c.Id, c => c.ParentId);

测试：

static void Test(IEnumerable<TreeItem<category>> categories, int deep = 0)
{
    foreach (var c in categories)
    {
        Console.WriteLine(new String('\t', deep) + c.Item.Name);
        Test(c.Children, deep + 1);
    }
}
// ...
Test(root);

输出

Sport
    Balls
    Shoes
Electronics
    Cameras
        Lenses  
        Tripod
    Computers
        Laptops
Empty
于 2013-10-29T02:04:11.637 回答
33 
foreach (var cat in categories)
{
    cat.Subcategories = categories.Where(child => child.ParentId == cat.Id)
                                  .ToList();
}

你会得到O(n*n)复杂性。

更优化的方法是使用查找表：

var childsHash = categories.ToLookup(cat => cat.ParentId);

foreach (var cat in categories)
{
    cat.Subcategories = childsHash[cat.Id].ToList();
}

这给了你O(2*n)≈O(n)

结果，您将拥有下一个结构（从 LinqPad 显示）：

在此处输入图像描述

于 2013-10-29T01:41:56.053 回答
7

传递如何识别父母的另一种方式。完整代码（包括内部实现ITree和xUnit测试）可在Gist此处获得：Nice & Universal way to convert List of items to Tree

用法：

ITree<Category> tree = categories.ToTree((parent, child) => child.ParentId == parent.Id);

产品：

        <ROOT>
        -Sports
        --Balls
        --Shoes
        -Electronics
        --Cameras
        ---Lenses
        ---Tripod
        --Computers
        ---Laptops
        -Empty
        -Broken

通用树节点接口：

public interface ITree<T>
{
    T Data { get; }
    ITree<T> Parent { get; }
    ICollection<ITree<T>> Children { get; }
    bool IsRoot { get; }
    bool IsLeaf { get; }
    int Level { get; }
}

采集扩展方法：

public static ITree<T> ToTree<T>(this IList<T> items, Func<T, T, bool> parentSelector)
{
    if (items == null) throw new ArgumentNullException(nameof(items));

    var lookup = items.ToLookup(
            item => items.FirstOrDefault(parent => parentSelector(parent, item)),
            child => child);

    return Tree<T>.FromLookup(lookup);
}
于 2019-03-08T15:36:24.950 回答
5

您可以使用以下数据库查询来获取具有父子关系的类别列表：

WITH tree (categoryId, parentId, level, categoryName, rn) as 
(
   SELECT categoryId, parentid, 0 as level, categoryName,

       convert(varchar(max),right(row_number() over (order by categoryId),10)) rn
   FROM Categories
   WHERE parentid = 0

   UNION ALL

   SELECT c2.categoryId, c2.parentid, tree.level + 1, c2.categoryName,

       rn + '/' + convert(varchar(max),right(row_number() over 
       (order by tree.categoryId),10))
   FROM Categories c2 

     INNER JOIN tree ON tree.categoryId = c2.parentid
)

SELECT *
FROM tree
order by RN

我希望这会帮助你。

于 2013-10-29T01:54:05.613 回答
3

这是我整理的一个小例子。这很“通用”。

也可以通过定义一个接口（这将允许简化函数参数）来制作一种通用方法 - 但是，我选择不这样做。无论如何，“映射器”和选择器功能允许它跨不同类型工作。

另请注意，这不是一个非常有效的实现（因为它保留了所有子树的所有可能子树并反复迭代），但可能适用于给定任务。过去我也使用过一种Dictionary<key,collection>方法，它有更好的界限，但我不想那样写:)

这作为“LINQPad C# 程序”运行。享受！

// F - flat type
// H - hiearchial type
IEnumerable<H> MakeHierarchy<F,H>(
    // Remaining items to process
    IEnumerable<F> flat,
    // Current "parent" to look for
    object parentKey,
    // Find key for given F-type
    Func<F,object> key,
    // Convert between types
    Func<F,IEnumerable<H>,H> mapper,
    // Should this be added as immediate child?
    Func<F,object,bool> isImmediateChild) {

    var remainder = flat.Where(f => !isImmediateChild(f, parentKey))
        .ToList();

    return flat
        .Where(f => isImmediateChild(f, parentKey))
        .Select(f => {
            var children = MakeHierarchy(remainder, key(f), key, mapper, isImmediateChild);
            return mapper(f, children);
        });
}

class category1
{
    public int Id;
    public int ParentId;
    public string Name;

    public category1(int id, string name, int parentId) {
        Id = id;
        Name = name;
        ParentId = parentId;
    }
};

class category2
{
    public int Id;
    public int ParentId;
    public string Name;

    public IEnumerable<category2> Subcategories;
};

List<category1> categories = new List<category1>() {
    new category1(1, "Sport", 0),
    new category1(2, "Balls", 1),
    new category1(3, "Shoes", 1),
    new category1(4, "Electronics", 0),
    new category1(5, "Cameras", 4),
    new category1(6, "Lenses", 5),  
    new category1(7, "Tripod", 5), 
    new category1(8, "Computers", 4),
    new category1(9, "Laptops", 8),
    new category1(10, "Empty", 0),
    new category1(-1, "Broken", 999),
};

object KeyForCategory (category1 c1) {
    return c1.Id;
}

category2 MapCategories (category1 c1, IEnumerable<category2> subs) {
    return new category2 {
        Id = c1.Id,
        Name = c1.Name,
        ParentId = c1.ParentId,
        Subcategories = subs,
    };
}

bool IsImmediateChild (category1 c1, object id) {
    return c1.ParentId.Equals(id);
}

void Main()
{
    var h = MakeHierarchy<category1,category2>(categories, 0,
        // These make it "Generic". You can use lambdas or whatever;
        // here I am using method groups.
        KeyForCategory, MapCategories, IsImmediateChild);
    h.Dump();
}
于 2013-10-29T02:28:31.543 回答
1

使用Ilya Ivanov和Damian Drygiel解决方案，我编写了一些代码，它可以创建一个包含任何集合和任何级别子级的树，即使您完全不知道哪些节点将成为根。

树节点条目

public sealed class TreeNode<T, TKey>
{
    public T Item { get; set; }
    public TKey ParentId { get; set; }

    public IEnumerable<TreeNode<T, TKey>> Children { get; set; }
}

扩展方法

public static class EnumerableExtensions
{
    public static IEnumerable<TreeNode<T, TKey>> ToTree<T, TKey>(
        this IList<T> collection,
        Func<T, TKey> itemIdSelector,
        Func<T, TKey> parentIdSelector)
    {
        var rootNodes = new List<TreeNode<T, TKey>>();
        var collectionHash = collection.ToLookup(parentIdSelector);

        //find root nodes
        var parentIds = collection.Select(parentIdSelector);
        var itemIds = collection.Select(itemIdSelector);
        var rootIds = parentIds.Except(itemIds);

        foreach (var rootId in rootIds)
        {
            rootNodes.AddRange(
                GetTreeNodes(
                    itemIdSelector,
                    collectionHash,
                    rootId)
                );
        }

        return rootNodes;
    }

    private static IEnumerable<TreeNode<T, TKey>> GetTreeNodes<T, TKey>(
        Func<T, TKey> itemIdSelector,
        ILookup<TKey, T> collectionHash,
        TKey parentId)
    {
        return collectionHash[parentId].Select(collectionItem => new TreeNode<T, TKey>
        {
            ParentId = parentId,
            Item = collectionItem,
            Children = GetTreeNodes(
                itemIdSelector,
                collectionHash,
                itemIdSelector(collectionItem))
        });
    }
}

例子：

 //Test Item
 public class TestTreeItem
 {
     public int Id { get; set; }
     public int ParentId { get; set; }

     public string Name { get; set; }
 }

 //Usage
 var collection = new List<TestTreeItem>
 {
      new TestTreeItem {Id = 1, Name = "1", ParentId = 14},
      new TestTreeItem {Id = 2, Name = "2", ParentId = 0},
      new TestTreeItem {Id = 3, Name = "3", ParentId = 1},
      new TestTreeItem {Id = 4, Name = "4", ParentId = 1},
      new TestTreeItem {Id = 5, Name = "5", ParentId = 2},
      new TestTreeItem {Id = 6, Name = "6", ParentId = 2},
      new TestTreeItem {Id = 7, Name = "7", ParentId = 3},
      new TestTreeItem {Id = 8, Name = "8", ParentId = 3},
      new TestTreeItem {Id = 9, Name = "9", ParentId = 5},
      new TestTreeItem {Id = 10, Name = "10", ParentId = 7}
  };

  var tree = collection.ToTree(item => item.Id, item => item.ParentId);

我希望，它可以帮助某人。享受

于 2018-11-20T17:35:05.393 回答
1

还有更简单的解决方案：
无需在内存中创建新的节点对象。我们已经在源列表中有对象。只需正确填写Children.
Node可以作为其他逻辑单元的基础的类。Path看起来像1.1,1.2.1等2。
而不是PathandParentPath你可以相应地使用IdandParentId

    public abstract class Node
    {
        public int Id { get; set; }
        public string Name { get; set; }
        public string Path { get; set; }
        public string ParentPath
        {
            get
            {
                var lastDotPosition = Path.LastIndexOf('.');
                return lastDotPosition == -1 ? null : Path.Substring(0, lastDotPosition );
            }
        }
        public IEnumerable<Node> Children { get; set; }
    }

递归扩展方法：

public static class TreeExtension
{
    public static IEnumerable<T> GenerateTree<T>(this IEnumerable<T> table, T rootNode) where T : Node
    {
        var organizationalNodes = table.ToList();
        var rootNodes = organizationalNodes.Where(node => node.ParentPath == rootNode?.Path).ToList();

        foreach (var node in rootNodes)
        {
            node.Children = organizationalNodes.GenerateTree(node);
        }

        return rootNodes;
    }
}

用法：

public class RegionNode : Node
{
    public string timezone {get; set;}
}

从数据库中获取表并生成树：

var result = await _context.GetItemsAsync<RegionNode>();
return result.GenerateTree( null);
于 2020-07-29T09:07:08.500 回答
0

使用Ilya Ivanov算法（见上文），我使该方法更通用。

public static IEnumerable<TJ> GenerateTree<T, TK, TJ>(this IEnumerable<T> items,
                                                      Func<T, TK> idSelector,
                                                      Func<T, TK> parentSelector,
                                                      Func<T, IEnumerable<T>, TJ> outSelector)
{
       IList<T> mlist = items.ToList();

       ILookup<TK, T> mcl = mlist.ToLookup(parentSelector);

       return mlist.Select(cat => outSelector(cat, mcl[idSelector(cat)]));
}

用法 ：

IEnumerable<Category> mlc = GenerateTree(categories,
                                         c => c.Id, 
                                         c => c.ParentId,
                                         (c, ci) => new Category
                                         {
                                              Id = c.Id,
                                              Name = c.Name,
                                              ParentId = c.ParentId ,
                                              Subcategories = ci
                                         });
于 2015-11-22T15:07:57.097 回答
0

我更喜欢使用接口而不是创建新的通用树类型。因此，我将更改Damian Drygiel对此代码的回答：

public interface ITreeItem<T>
{
    IEnumerable<T> Children { get; set; }
}

public static IEnumerable<T> GenerateTree<T, K>(
    this IEnumerable<T> collection,
    Func<T, K> id_selector,
    Func<T, K> parent_id_selector,
    K root_id = default(K)) where T :ITreeItem<T>
{
    foreach (var c in collection.Where(c => EqualityComparer<K>.Default.Equals(parent_id_selector(c), root_id)))
    {
        c.Children = collection.GenerateTree(id_selector, parent_id_selector, id_selector(c));
        yield return c;
    }
}

和类别将是这样的：

class category :ITree<category>
{
  public int Id;
  public int ParentId;
  public string Name;
  public IEnumerable<category> Children;
}
于 2021-04-19T03:59:31.110 回答
-1

您查看数据模型：

public class PricesViewModel
{        
    public List<PriceType> PriceTypes { get; set; }// List OF Items with Parent ID
    public static string Data { get; set; } = ""; // Printed Items
    public static List<int> IDs { get; set; }// IDs of Your List To filters

    public static void Print(List<PriceType> categories, int deep = 0)
    {
        foreach (var c in categories)
        {
            if (PricesViewModel.IDs.Count(x => x == c.ID) > 0)// if Item not taken
            {
                for (int i = 0; i < deep; i++)// Get Spasece 
                {
                    PricesViewModel.Data += "&emsp;";
                    //Console.Wirte("    ");
                }
                PricesViewModel.Data +=  "<p>" +c.Name + "</p>"; //Save Items to Print
                //Console.WirteLine(c.Name);
                if (PricesViewModel.IDs.Count(x => x == c.ID) != 0)
                {
                    PricesViewModel.IDs.Remove(c.ID);//Filter Of IDs List
                    if (c.PriceTypes.Count != 0)
                        Print(c.PriceTypes.ToList(), deep + 1);
                }
            }
        }
    }
}

测试你的代码：

PricesViewModel obj = new PricesViewModel();
obj.PriceTypes = db.PriceTypes.Include(x => x.PriceTypes).Include(x => x.priceType).Include(x => x.Prices).ToList();//GenerateTree(c => c.ID, c => c.TypeID);

PricesViewModel.IDs = obj.PriceTypes.Select(x=>x.ID).ToList();
PricesViewModel.Data = "";
PricesViewModel.Print(obj.PriceTypes);
于 2021-08-09T11:12:35.663 回答