Build a simple, high performance Tree Data Structure in c#

Question

I need to create a product catalog, in tree type.

every tree node presents by a ID(string), the functions on the tree data only 2:

1. getChild(string ID), give a ID, get children (no need include childrens' children), if ID is null, get all root nodes
2. getParent(string ID), return parent ID if have, or null if is root

Since once the tree decided, will not change, so I think put all code in static will be best. So I start to try use Dictionary

"id": {parent:ID, child:[id2, id3, id4....]} 

Since theres about 1000+ catalog, I found I quickly mess myself up, lots of mistake in the static data, and make final result on usable. Also, now I only wrote dozens and the code is looking like mess.

Please advice a way create this simple catalog tree with high performance. Thanks

Answer 1

Just make a class out of it.

UPDATED:

class TreeNode : IEnumerable<TreeNode> {     private readonly Dictionary<string, TreeNode> _children =                                         new Dictionary<string, TreeNode>();      public readonly string ID;     public TreeNode Parent { get; private set; }      public TreeNode(string id)     {         this.ID = id;     }      public TreeNode GetChild(string id)     {         return this._children[id];     }      public void Add(TreeNode item)     {         if (item.Parent != null)         {             item.Parent._children.Remove(item.ID);         }          item.Parent = this;         this._children.Add(item.ID, item);     }      public IEnumerator<TreeNode> GetEnumerator()     {         return this._children.Values.GetEnumerator();     }      IEnumerator IEnumerable.GetEnumerator()     {         return this.GetEnumerator();     }      public int Count     {         get { return this._children.Count; }     } } 

Usage will be fairly simple to statically define:

var tree = new TreeNode("Root")                {                    new TreeNode("Category 1")                        {                            new TreeNode("Item 1"),                            new TreeNode("Item 2"),                            new TreeNode("Item 3"),                        },                    new TreeNode("Category 2")                        {                            new TreeNode("Item 1"),                            new TreeNode("Item 2"),                            new TreeNode("Item 3"),                            new TreeNode("Item 4"),                        }                }; 

Edit

Some more functionality for even easier creation...

public static TreeNode BuildTree(string tree) {     var lines = tree.Split(new[] { Environment.NewLine },                            StringSplitOptions.RemoveEmptyEntries);      var result = new TreeNode("TreeRoot");     var list = new List<TreeNode> { result };      foreach (var line in lines)     {         var trimmedLine = line.Trim();         var indent = line.Length - trimmedLine.Length;          var child = new TreeNode(trimmedLine);         list[indent].Add(child);          if (indent + 1 < list.Count)         {             list[indent + 1] = child;         }         else         {             list.Add(child);         }     }      return result; }  public static string BuildString(TreeNode tree) {     var sb = new StringBuilder();      BuildString(sb, tree, 0);      return sb.ToString(); }  private static void BuildString(StringBuilder sb, TreeNode node, int depth) {     sb.AppendLine(node.ID.PadLeft(node.ID.Length + depth));      foreach (var child in node)     {         BuildString(sb, child, depth + 1);     } } 

Usage:

var tree = TreeNode.BuildTree(@" Cat1  Sub1   Item1   Item2   Item3  Sub2   Item1   Item2 Cat2  Sub1  Sub2   Item1   Item2  Sub3   Item1 Cat3 Cat4");