C# tree/collection algorithm

Question

I need to fill a tree-like UI control with some items (of course in parent-child1-child2-...childN relations) and before proceeding I want to ensure that the my collection that holds the content is ordered properly as follows:

Each object(in this case an instance of my Category class) from my collection (ObservableCollection that is not ordered) has a public property(a ParentCategoryID as string) that points to another 'Category' that will be its parent in my tree. A node in the tree can have 0 or any number of children.

So when filling the tree, each 'category' object that is to be displayed has already its 'parent category'(based on the ParentCategoryID) in the collection.

What algorithm should I use to ensure that my collection is ordered this way before addig the elements in the tree?

Answer 1

Maybe a childnode should not know it's parent node, in my opinion it should be vice versa. When each parent node holds a collection of child nodes and this collection can be sorted after adding a new node. Maybe this solves your problem.

Regards.

Answer 2

I'm not sure if this is what you are looking for but hopefully it will help:

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
}