构建将树排序为C＃中的列表
我有一个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.
这似乎很容易。 也许我一直在看它太久了。 但我似乎可以让它发挥作用。 有任何想法吗？
即使您说您希望按级别（升序）和createDate（升序）排序项目，否则您的图表会另外说明。 看起来您实际上希望以允许您打印出树的方式对项目进行排序，这样每个项目都在其父项之后以及其子项及其父项“年轻的兄弟姐妹”之前。 这是一种拓扑排序 ，与您要求的大不相同，但并不那么难：
class ItemComparer : IComparer- { // allow us to look up parent Items by GUID IDictionary
itemLookup; public ItemComparer(IEnumerable - 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- items.Sort(new ItemComparer(items)); // if IEnumerable
- var sorted = random.OrderBy(x => x, new ItemComparer(random));
这是一个替代答案，它从输入构建树，然后按顺序遍历它。 此遍历为您提供排序输出。
class FlattenTree { // map each item to its children ILookup mapping; public FlattenTree(IEnumerable- list) { var itemLookup = list.ToDictionary(item => item.ID); mapping = list.Where(i => i.ParentID.HasValue) .ToLookup(i => itemLookup[i.ParentID.Value]); } IEnumerable
- 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
- 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();
从字面上看，要对列表进行排序，您应该使用名为Sort方法。 您只需要提供正确的比较器，这意味着您需要定义一个方法来比较您定义的两个项目（按级别，然后创建）。 在这里查看MSDN： http ： //msdn.microsoft.com/en-us/library/w56d4y5z.aspx
例如，你可以像这样使用lambda：
mylist.Sort((x,y) => { int c = x.Level.CompareTo(y.Level); if(c==0) c = x.CreateDate.CompareTo(y.CreateDate); return c; });
请注意，我没有在Visual Studio中编译和测试此代码。 也许它不是100％正确，但希望它告诉你从哪里开始。