While working on my 1st code post for Spring.net DAF (Desktop Application Framework) – I had the need for some generalized traversal code. There are a few basic factors.

Sometimes you need to just traverse through trees/ nodes and touch throughout. Sometimes you need to traverse through tree like strucutres and just find something. Sometimes – you want to go breadth 1st, sometimes you want to go depth 1st. Also – you want to avoid recursion as much as possible.

In general – you can use a queue or a stack to replace recursion for traversing arbitrary heirachies of data.

Depth First, Breadth First??

here is a pic (thanks wikipedia) of a breadth 1st search:

From the root – you want to iterate “level by level” not straight to the bottom levels.

Here is what depth 1st looks like (thanks IBM):

Using generics, delegates and simple interface implementation – we can easily generalize this. Here are the relevant code bits for a generic searcher:

Search delegate:

Child Selection delegate

The Generic search method:

The algorithm is the same for a breadth or a depth 1st search. You take the root object, put it in the object container (queue or stack for breadh or depth 1st respectively). You then look for what you want. If you find it – you are done. If you did not find it – get the child nodes of interest and put them in the object container (again queue or stack for breadh or depth 1st respectively) and continue on. You do this – till you run out of nodes or you find what you were looking for.

Here are what the public methods look like:

Depth:

Breadth:

Making the stack and queue look the same:

We use a simple adapter to make the queue and stack look the same:

The public routines – DepthFirst and BreadthFirst – simply select the correct strategy they would like to use – queue or stack – the implementation uses an adapted queue or stack to carry out it’s work. We have minimal code – we have used a few simple/ common patterns – lo and behold – generalized search! The delegates give us the freedom to implement whatever goal search criteria we have and to select the child nodes based on whatever criteria we have. All in all – a decent solution… This will be in the 1st SpringFramework.net DAF code dump

Here is what an example usage might look like:

That would find a control by name – breadth 1st (depth 1st, you would just change method call in last line). The algorithm is generic to do the search. You specify the critieria in your delegates to get the child elements and what your ‘found’ criteria is. You could just as easily search and XmlNode or anything else tree like – you just tell the searcher what you want to find – and how to get the next level in the tree – and you are done.

I hope this exercise has been fun

-Chris

No Responses to “Using generics and delegates in C# for traversal and searching trees”

1. Chris Donnan : Programming - Brooklyn Style - Using generics and delegates in C# for traversal and searching trees, on June 5th, 2006 at 3:50 am, said:
   

   [...] Moved to articles section here. Share and Enjoy:These icons link to social bookmarking sites where readers can share and discover new web pages. [...]

Comment on this post below

You must be logged in to post a comment.

You can leave a response, or trackback from your own site.