在 C# 中将树排序为列表

Question

我有一个 C# 实体列表。我的实体定义如下：

public class Item
{
    // the id of an item
    public Guid ID { get; set; }

    // if this is a child item, the ParentID is the ID of the item that
    // this item is a child of
    public Guid? ParentID { get; set; }

    // If this item does not have a parent, this should be 0.
    // Otherwise if it is a child, a level=1
    // If it is a grandchild, level=2, etc.
    public int Level { get; set; }

    // The UTC date the item was created on.
    public DateTime CreateDate { get; set; }
}

我的这些实体列表是随机排列的。我试图弄清楚如何对实体列表进行排序，以便项目元素按级别（升序）排序，然后按 createDate （升序）排序。基本上一个列表看起来像这样：

Item 1 (Level 0)
  Item 2 (Level 1)
    Item 3 (Level 2)
    Item 4 (Level 2)
  Item 5 (Level 1)
Item 6 (Level 0)
  Item 7 (Level 2)
etc.

这看起来很容易。也许是我看得太久了。但我似乎可以让它发挥作用。有任何想法吗？

Answer 1

这是一个替代答案，它根据输入构建一棵树，然后按顺序遍历它。此遍历为您提供排序的输出。

class FlattenTree
{
    // map each item to its children
    ILookup<Item, Item> mapping;

    public FlattenTree(IEnumerable<Item> list)
    {
        var itemLookup = list.ToDictionary(item => item.ID);
        mapping = list.Where(i => i.ParentID.HasValue)
                      .ToLookup(i => itemLookup[i.ParentID.Value]);
    }

    IEnumerable<Item> YieldItemAndChildren(Item node)
    {
        yield return node;
        foreach (var child in mapping[node].OrderBy(i => i.CreateDate))
            foreach (var grandchild in YieldItemAndChildren(child))
                yield return grandchild;
    }

    public IEnumerable<Item> Sort()
    {
        return from grouping in mapping
               let item = grouping.Key
               where item.ParentID == null
               orderby item.CreateDate
               from child in YieldItemAndChildren(item)
               select child;
    }
}

像这样调用它：

var sorted = new FlattenTree(random).Sort();