C# 树/集合算法

Question

我需要用一些项目填充一个树状 UI 控件(当然是在parent-child1-child2-...childN 关系中)，在继续之前我想确保保存内容的集合已正确排序如下:

我的集合(未排序的 ObservableCollection)中的每个对象(在本例中是我的 Category 类的实例)都有一个公共(public)属性(ParentCategoryID 作为字符串)，该属性指向另一个“Category”，该属性将成为我的集合中的父级。树。树中的一个节点可以有 0 个或任意数量的子节点。

因此，在填充树时，要显示的每个“类别”对象在集合中已经有其“父类别”(基于 ParentCategoryID)。

在添加树中的元素之前，我应该使用什么算法来确保我的集合按这种方式排序？

Answer 1

我不确定这是否是您正在寻找的内容，但希望它会有所帮助:

using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
public class Program
{
   public static void Main(string[] args)
   {
      /* Tree Structure

         a
          d
           e   
         b
          f
          i
           j
         c
          g
           h
      */

      var a = new Category("a", null);
      var b = new Category("b", null);
      var c = new Category("c", null);
      var d = new Category("d", "a");
      var e = new Category("e", "d");
      var f = new Category("f", "b");
      var g = new Category("g", "c");
      var h = new Category("h", "g");
      var i = new Category("i", "b");
      var j = new Category("j", "i");
      var k = new Category("k", "z");

      var list = new CategoryCollection { k, j, i, h, g, f, e, d, c, b, a };
      foreach (var category in list.SortForTree())
      {
         Console.WriteLine("Name: {0}; Parent: {1}", category.Name, category.ParentCategoryID);
      }
   }
}

class Category
{
   public string ParentCategoryID { get; set; }
   public string Name { get; set; }
   public Category(string name, string parentCategoryID)
   {
      Name = name;
      ParentCategoryID = parentCategoryID;
   }
}

class CategoryCollection : IEnumerable<Category>
{
   private List<Category> list = new List<Category>();

   public void Add(Category category)
   {
      list.Add(category);
   }

   public IEnumerable<Category> SortForTree()
   {
      var target = new Dictionary<string, Category>();

      SortForTree(list, target);

      return target.Values;
   }

   private void SortForTree(List<Category> source, Dictionary<string, Category> target)
   {
      var temp = new List<Category>();

      foreach (var c in source)
      {
         if (c.ParentCategoryID == null || (target.ContainsKey(c.ParentCategoryID) && !target.ContainsKey(c.Name)))
         {
            target.Add(c.Name, c);
         }
         else
         {
            if (source.Exists(o => o.Name == c.ParentCategoryID))
            {
               temp.Add(c);
            }
         }
      }

      if (temp.Count > 0) SortForTree(temp, target);
   }

   #region IEnumerable<Category> Members

   public IEnumerator<Category> GetEnumerator()
   {
      return list.GetEnumerator();
   }

   #endregion

   #region IEnumerable Members

   IEnumerator IEnumerable.GetEnumerator()
   {
      return list.GetEnumerator();
   }

   #endregion
}