Tree data structure in C#

Question

I was looking for a tree or graph data structure in C# but I guess there isn't one provided. http://msdn.microsoft.com/en-us/library/ms379574.aspx explains a bit about why. Is there a convenient library which is commonly used to provide this functionality? Perhaps through a strategy pattern to solve the issues presented in the article.

I feel a bit silly implementing my own tree, just as I would implementing my own ArrayList.

Edit:

I think I need to explain better what I'm looking for. I just want a generic tree which can be unbalanced. Think of a directory tree. C5 looks nifty, but their tree structures seem to be implemented as balanced red-black trees better suited to search than representing a hierarchy of nodes.

Answer 1

The generally excellent C5 Generic Collection Library has several different tree-based data structures, including sets, bags and dictionaries. Source code is available if you want to study their implementation details. (I have used C5 collections in production code with good results, although I haven't used any of the tree structures specifically.)

Answer 2

My best advice would be that there is no standard tree data structure because there are so many ways you could implement it that it would be impossible to cover all bases with one solution. The more specific a solution, the less likely it is applicable to any given problem. I even get annoyed with LinkedList - what if I want a circular linked list?

The basic structure you'll need to implement will be a collection of nodes, and here are some options to get you started. Let's assume that the class Node is the base class of the entire solution.

If you need to only navigate down the tree, then a Node class needs a List of children.

If you need to navigate up the tree, then the Node class needs a link to its parent node.

Build an AddChild method that takes care of all the minutia of these two points and any other business logic that must be implemented (child limits, sorting the children, etc.)

Answer 3

If you would like to write your own, you can start with this six-part document detailing effective usage of C# 2.0 data structures and how to go about analyzing your implementation of data structures in C#. Each article has examples and an installer with samples you can follow along with.

“An Extensive Examination of Data Structures Using C# 2.0” by Scott Mitchell

Answer 4

I hate to admit it but I ended up writing my own tree class using a linked list. On an unrelated note I just discovered this round thing which, when attached to a thing I'm calling an 'axle' allows for easier transportation of goods.

Answer 5

I came across this question while looking for the same thing myself. After some googling in found Dan Vanderboom's post and it looks quite promising. I'll give it a try this week-end and I'll post my findings here.

Answer 6

delegate void TreeVisitor<T>(T nodeData);

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

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

        public void addChild(T data)
        {
            children.AddFirst(new NTree<T>(data));
        }

        public NTree<T> getChild(int i)
        {
            foreach (NTree<T> n in children)
                if (--i == 0) return n;
            return null;
        }

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

Simple recursive implementation... < 40 lines of code... You just need to keep a reference to the root of the tree outside of the class, or wrap it in another class, maybe rename to TreeNode??

Answer 7

See http://quickgraph.codeplex.com/

QuickGraph provides generic directed/undirected graph datastructures and algorithms for .Net 2.0 and up. QuickGraph comes with algorithms such as depth first seach, breath first search, A* search, shortest path, k-shortest path, maximum flow, minimum spanning tree, least common ancestors, etc... QuickGraph supports MSAGL, GLEE, and Graphviz to render the graphs, serialization to GraphML, etc...