C# tree/collection algorithm

Question

Мне нужно заполнить древовидный элемент управления пользовательским интерфейсом некоторыми элементами (конечно, в родительских-child1-child2 -... дочернихN-отношениях), и перед продолжением я хочу убедиться, что моя коллекция, которая содержит содержимое упорядочивается следующим образом:

Каждый объект (в данном случае экземпляр моего класса категории) из моей коллекции (ObservableCollection, который не упорядочен) имеет общедоступное свойство (ParentCategoryID как строку), которое указывает на другой символ ' Категория ", которая будет его родителем в моем дереве. Узел в дереве может иметь 0 или любое количество детей.

Таким образом, при заполнении дерева каждый объект категории, который должен быть отображен, уже имеет свою «родительскую категорию» (на основе идентификатора родительской категории) в коллекции.

Какой алгоритм следует использовать для обеспечения того, чтобы моя коллекция упорядочивалась таким образом, прежде чем добавлять элементы в дерево?

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 
} 

Answer 2

Возможно, дочерний узел не должен знать, что это родительский узел, на мой взгляд, он должен быть наоборот. Когда каждый родительский узел содержит коллекцию дочерних узлов, и эта коллекция может быть отсортирована после добавления нового узла. Возможно, это решает вашу проблему.

С уважением.