Binary Tree, C# and Delegates - Part 1
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 cool. Soon I will publish couple of posts in the context of same topic - "Data Structure Fundamentals" brain-brush. See part 2.