Geeks With Blogs
.NET Corner Jeans, .NET and Physics (eka The Quantum Boy)

During the last week I was brushing up my Data Structure fundamentals. It was great to get back the days of C style pointers, link list, binary trees etc. But at the same time I want to play around the anonymous delegates of C# 2.0. Both my wishes were granted...My data structures were based on C# generics. The TreeNode structure and the action delegate were both templatized(i.e. based on Generics

public delegate void Action<T>(TreeNode<T> p);
public class TreeNode<T>
{
        //Data
        public T nodeData;

        //Self pointers
        public TreeNode<T> left;
        public TreeNode<T> right;

       //More stuff...
}

Pretty simple stuff. The task I wanted to implement first is to do a inorder walk down the tree without using recursion. My primary objective in this blog is to resurrect the dying spirit of Data Structure fundamentals ,not to show a new discovery or geeky stuff. Now to do an Inorder walk non-recursively we need a stack. You name it , System.Collections.Generic has it.

//declare a stack
Stack<TreeNode<T>> s = new Stack<TreeNode<T>>();
TreeNode<T> ptr = nodePtr;
               
do
{
  while (ptr != null)
  {
     s.Push(ptr);
     ptr = ptr.left;
  }

  ptr = s.Pop();

  action(ptr);

  ptr = ptr.right;

}while (s.Count != 0);

Let's give the interface of the function. 

private void InOrder(Action<T> action, TreeNode<T> nodePtr)

Another short pointer for the usage of private qualifier. For all(well almost) traversal algorithms of the tree it is always wise to keep two versions. One private method taking a generic TreeNode*(in C) or TreeNode(in C#) and another top level public function calling the private counterpart with the root as a value of the TreeNode* or TreeNode refrence variable. The private function is often called "workhorse.

public void InOrder(Action<T> action)
{
    this.InOrder(action, root);
}

Now the funniest part. The calling portion

tree.InOrder(delegate(TreeNode<int> p)
             {
                 lblPrintTree.Text += p.nodeData.ToString();
             });

We are injecting our own callback function to the InOrder tree traversal algorithm through the anonymous generic delegate . C#2.0 is good.  Some guys might think that this is oldy but LINQ, PLINQ, Lambda Expressions are good but more and more language features of csharp are more of a syntactic sugars than anything else. Soon I will publish couple of posts in the context of same topic - "Data Structure Fundamentals" brain-brush. See part 2.

Posted on Saturday, November 8, 2008 3:34 AM .NET Core | Back to top


Comments on this post: Binary Tree, C# and Delegates - Part 1

No comments posted yet.
Your comment:
 (will show your gravatar)


Copyright © dbose | Powered by: GeeksWithBlogs.net