Click here to Skip to main content
Click here to Skip to main content

Generic Tree Container in C# 2.0

, 11 Aug 2004
Rate this:
Please Sign up or sign in to vote.
A small library implementing a generic tree container showing off generics and iterators.

Introduction

With C# 2.0, a powerful language feature is being introduced which all C++ programmers have been missing since the beginnings of this altogether so cleanly and beautifully designed language: generics. This article uses this new feature to implement a generic tree class. Tree structures have more than just one natural way of being traversed, this is also a good motivation to demonstrate the use of C# 2.0's new iterator feature. If you wonder how you can build the code or how you can start trying out the new language features, go look at Microsoft's site where you can download a beta of their new Express line of developers products.

Background

For a general introduction into the topic of generics and/or iterators, please take a look at the specification of C# 2.0 by Microsoft which does a good job on explaining them in detail.

Usage

When using the code, you will be dealing with two classes: Node and NodeCollection. Before going into the details of the implementation, it's probably a good idea to scan the demo project which comes with the source archive. The demo project is a console application which takes a single parameter. This parameter should be a path pointing to a directory. The demo first loads the file hierarchy rooted inside that path into an internally kept tree structure using the Node class, and then iterates over this tree structure once depth-first, then breadth-first. In the demo's Run() method, you see how to specialize the Node class for a given type, and construct an instance:

void Run(string rootdir)
{
    Node<string> root = new Node<string>(rootdir);

The code above creates an instance of the Node class specialized for containing data of type string and initializes the instance with a value. The Node class contains a property Data which allows read-only access to the element type for which it is specialized. Exactly this property is what you initialize in the constructor code. If you want to access the children of a node, you use the Children property which returns an instance of NodeCollection. Each node has a Parent property, too, which is read-only. If you add a node as the child of another, the first node's Parent property will reflect this change. Newly constructed nodes return null as their Parent, meaning they are located in the root of the hierarchy. The NodeCollection, on the other hand, has a read-only property Owner returning the Node whose children it contains. NodeCollection is not meant to be used as a general-purpose container for Nodes, thus its constructor is not publicly accessible. Node contains other useful properties and methods: the Root property gets the root of a node (wouldn't you have guessed Wink | ;-) ), IsAncestorOf() takes another node and returns whether the instance node is an ancestor of the passed node, IsDescendantOf() checks for exactly the opposite condition, and DoesShareHierarchyWith() takes another node and returns whether the instance node and the passed node are equal or have an ancestor-descendant relationship (true) or not (false). GetDepthFirstEnumerator() and GetBreadthFirstEnumerator() return iterators performing a depth-first or breadth-first traversal. Note that the iterators returned by these methods iterate over the Data values of the nodes, not the nodes themselves, meaning that .Current will return the value of Data of the currently visited node.

Implementation

The implementation of this small library makes use of two new features of C# 2.0: generics and iterators. Generics are used to allow the nodes to function as a type-safe container. Without them, the Data property would have to be of type object, requiring clients to cast to the correct type and allowing to instantiate Node with objects of different types. Iterators, on the other hand, are used for implementing depth-first and breadth-first traversal in a compellingly intuitive way. Let's take a look at their implementation:

        public IEnumerator<Element> GetDepthFirstEnumerator()
        {
            yield return mData;
            foreach (Node<Element> kid in mChildren)
            {
                IEnumerator<Element> kidenumerator= kid.GetDepthFirstEnumerator();
                while (kidenumerator.MoveNext())
                    yield return kidenumerator.Current;
            }
        }

IEnumerator<> is defined in System.Collections.Generic and defines a typesafe iterator, i.e., an iterator whose Current property is strongly typed.

Now, our depth-first traversal first returns the data of the current node itself, then iterates over the children nodes, gets their enumerators, and returns the values visited. For example, if you build up a structure like:

            Node<string> root= new Node<string>("Gramps");
            Node<string> son= new Node<string>("Son");
            Node<string> daughter= new Node<string>("Daughter");
            root.Children.Add(son);
            root.Children.Add(daugther);
            son.Children.Add(new Node<string>("Grandson"));
            son.Children.Add(new Node<string>("Granddaughter"));

a call like:

            foreach (string s in root.GetDepthFirstEnumerator())
                Console.WriteLine(s);

will result in:

            Gramps
            Son
            Grandson
            Granddaughter
            Daugther

First, root.GetDepthFirstEnumerator() yields root's data, i.e., "Gramps"; then it starts iterating over its children, the first one being son. Now, son.GetDepthFirstEnumerator() gets called and yields its data "Son" before starting to iterate over its own children. Both children yield their data "Grandson" and "Granddaughter", but no more because they don't have children themselves. Now, son.GetDepthFirstEnumerator() is done, and root.GetDepthFirstEnumerator() goes on to daughter, which, having no children of its own, yields only its own data "Daughter".

Breadth-first traversal is a little more complicated, but still C# 2.0's iterator facility allows an incredibly easy implementation:

        public IEnumerator<Element> GetBreadthFirstEnumerator()
        {
            Queue<Node<Element>> todo = new Queue<Node<Element>>();
            todo.Enqueue(this);
            while (0 < todo.Count)
            {
                Node<Element> n = todo.Dequeue();
                foreach (Node<Element> kid in n.mChildren)
                    todo.Enqueue(kid);
                yield return n.mData;
            }
        }

Assuming the same node structure as for the depth-first example, the code piece:

            foreach (string s in root.GetBreadthFirstEnumerator())
                Console.WriteLine(s);

produces this output:

              Gramps
              Son
              Daugther
              Grandson
              Granddaughter

In this case, recursion is unrolled into a loop. First, root.GetBreadthFirstEnumerator() creates a queue and puts root inside. Then, getting into the while loop, it unqueues root. Now, it iterates over root's children son and daughter and puts them into the queue. Then, it yields root's data "Gramps". Next time inside the loop, it pops son from the queue, pushes son's children into the queue, and yields son's data "Son". Next time, it pops daughter from the queue which has no children, so it yields daughter's data "Daugther" and proceeds. Now, it pops the two children of son, both of which don't have children of their own, thus do not add anything to the queue. Their data "Grandson" and "Granddaugther" gets yielded, and next time checking the loop-condition, the queue is empty and traversal thus finished.

Conclusion and To-Do

This little class gets you a generic tree container, if you need a quick and simple solution. It shows off the possibilities the new language features of C# 2.0 facilitate. In order to create a really useful, general purpose tree library, though, the code would have to be more adaptable to specific needs of the clients. Here's a short list of ideas - and who knows, maybe my next article will have some or even all of them implemented:

  • At the moment, Node is implemented for trees with an arbitrary number of children. But very often, you know that each node will have a fixed number of children (binary trees, quad trees etc.). For such scenarios, the presented implementation is clearly inefficient as it makes use internally of a framework container (System.Containers.Generic.List) where it should be using an array. So, it would be nice if nodes were parameterizable with a strategy for keeping children. Ideally, there would be two predefined strategies in the library, one using the list container, another one for arrays of static size, and clients could implement an interface for other cases.
  • Considering that quite often there is the need to visualize a tree structure, it would make sense to write an adaptor for filling a TreeView from a Node structure.
  • As for now, both traversal algorithms do not supply clients with any information about where exactly they are in the tree. Now, in game applications, for example, it's usually important to know how deep a depth-first traversal has gone currently. Besides, sometimes they want to parameterize how deep traversal will proceed, or they want to add nodes as they get deeper into the tree.

History

2004-08-10: first release.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

About the Author

Another Old Guy
Chief Technology Officer
Austria Austria
Started with programming about 20 years ago as a teenager. Has been doing software-development for some 16 years now commercially.
Is interested in design and process. Language specifics are sometimes fun, but they're never here to stay.
simply loves MS' new toys, .NET and C#.
 
Had his own company for a while, creating games for a living Smile | :)
 
Nowadays more Ronin-style: doing contract work together with a few good friends...

Comments and Discussions

 
QuestionMy problem [modified] PinmemberDGyurka7-Mar-11 9:15 
GeneralPassing other data structures into tree Pinmemberbarts001-Oct-08 17:11 
GeneralRe: Passing other data structures into tree Pinmembersonamsingh_1929-Nov-08 5:10 
GeneralRe: Passing other data structures into tree Pinmembersonamsingh_1929-Nov-08 5:54 
QuestionLicense question Pinmemberolbrin12-Jun-07 23:45 
Great job done. Got just one question to the author: can I use it in my own project freely? Thanks a lot.
AnswerRe: License question PinmemberMax Hajek (aka AzazelDev)13-Jun-07 2:58 
GeneralRe: License question Pinmemberolbrin13-Jun-07 21:31 
Generalforeach sample doese not work for 2.0 Pinmemberlesta16-Jul-06 23:31 
GeneralRe: foreach sample doese not work for 2.0 [modified] PinmemberDmgInc28-Jul-06 2:38 
GeneralRe: foreach sample doese not work for 2.0 [modified] Pinmembersamentu29-Apr-07 20:24 
QuestionRe: foreach sample doese not work for 2.0 PinmemberBurlingtonON24-Sep-07 3:43 
QuestionRe: foreach sample doese not work for 2.0 PinmemberBurlingtonON24-Sep-07 3:56 
JokeCode Fix due to Changes in .NET 2.0 PinmemberMonkeyCookie14-Sep-05 7:21 
GeneralRe: Code Fix due to Changes in .NET 2.0 Pinmembershawnkaczmarek7-Dec-05 17:11 
GeneralRe: Code Fix due to Changes in .NET 2.0 PinmemberdB.20-Dec-05 4:42 
GeneralRe: Code Fix due to Changes in .NET 2.0 Pinmemberdecoder7222-Nov-07 8:09 
GeneralFurther Reading Pinmemberchrisv12-Aug-04 6:41 
GeneralRe: Further Reading PinmemberAzazelDev aka Max Hajek12-Aug-04 22:33 
GeneralRe: Further Reading Pinmemberrveldman3-Dec-08 4:19 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140721.1 | Last Updated 12 Aug 2004
Article Copyright 2004 by Another Old Guy
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid