c# - 在 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

即使您说您希望项目按级别(升序)排序，然后按 createDate(升序)排序，您的图表却另有说明。看起来您实际上希望以一种允许您打印出树的方式对项目进行排序，这样每个项目都在其父级之后，在其子级和其父级“弟弟妹妹”之前。这是 topological sort这与您的要求有很大不同，但并不难:

class ItemComparer : IComparer<Item>
{
    // allow us to look up parent Items by GUID
    IDictionary<Guid, Item> itemLookup;

    public ItemComparer(IEnumerable<Item> list)
    {
        itemLookup = list.ToDictionary(item => item.ID);
        foreach (var item in list)
            SetLevel(item);
    }

    int SetLevel(Item item)
    {
        if (item.Level == 0 && item.ParentID.HasValue)
            item.Level = 1 + itemLookup[item.ParentID.Value].Level;
        return item.Level;
    }

    public int Compare(Item x, Item y)
    {
        // see if x is a child of y
        while (x.Level > y.Level)
        {
            if (x.ParentID == y.ID)
                return 1;
            x = itemLookup[x.ParentID.Value];
        }
        // see if y is a child of x
        while (y.Level > x.Level)
        {
            if (y.ParentID == x.ID)
                return -1;
            y = itemLookup[y.ParentID.Value];
        }
        // x and y are not parent-child, so find common ancestor
        while (x.ParentID != y.ParentID)
        {
            x = itemLookup[x.ParentID.Value];
            y = itemLookup[y.ParentID.Value];
        }
        // compare createDate of children of common ancestor
        return x.CreateDate.CompareTo(y.CreateDate);
    }
}

像这样调用它:

// if List<Item>
items.Sort(new ItemComparer(items));
// if IEnumerable<Item>
var sorted = random.OrderBy(x => x, new ItemComparer(random));