how to use a tree data structure in C#

Question

I found an implementation for a tree at this SO question. Unfortunately I don't know how to use it. Also I made a change to it since LinkedList does not have Add method:

delegate void TreeVisitor<T>(T nodeData);

class NTree<T>
{
    T data;
    List<NTree<T>> children;

    public NTree(T data)
    {
        this.data = data;
        children = new List<NTree<T>>();
    }

    public void AddChild(T data)
    {
        children.Add(new NTree<T>(data));
    }

    public NTree<T> GetChild(int i)
    {
        return children[i];
    }

    public void Traverse(NTree<T> node, TreeVisitor<T> visitor)
    {
        visitor(node.data);
        foreach (NTree<T> kid in node.children)
            Traverse(kid, visitor);
    }
}

I have class named tTable and I want to store it's children and their grandchildren (...) in this tree. My need is to find immediate children and not traverse entire tree. I also might need to find children with some criteria. Let's say tTable has only name and I want to find children with names matching some criteria. tTables constructor gives name a value according to int-value (somehow).

How do I use Traverse (write delegate) if I have code like this;

int i = 0;
Dictionary<string, NTree<tTable>> tableTreeByRootTableName = 
                  new Dictionary<string, NTree<tTable>>();
tTable aTable = new tTable(i++);
tableTreeByRootTableName[aTable.Name] = new NTree(aTable);
tableTreeByRootTableName[aTable.Name].AddChild(new tTable(i++));
tableTreeByRootTableName[aTable.Name].AddChild(new tTable(i++));

tableTreeByRootTableName[aTable.Name].GetChild(1).AddChild(new tTable(i++));

Answer 1

To get any benefit of using trees over lists or hash tables, there have to rules in place governing which nodes are children of parent nodes and not other parents and possibly the order in which the siblings occur. For example a binary search tree ensures that left children are less than the current node and right children are greater than the current node. This rule allows the binary search tree to get O(log n) search times. Similarly a heap guarantees that the root is greater than its children which gives it excellent sorting performance (worst case O(n log n)).

Your problem is insufficiently specified to grant any benefit to using a tree over another data structure.

Answer 2

This code will traverse the tree and add all the nodes matching the given name. This is C# 3x, for 2.0 you'll need to use an anonymous delegate.

NTree<tTable> tree = new NTree<tTable>(table);

string nameToMatch = "SomeName";
LinkedList<tTable> matches = new LinkedList<tTable>();

tree.Traverse(tree, data => {
  if (data.Name == nameToMatch) {
    matches.AddLast(data);
  }
});