Thursday, May 06, 2010

Using Lambda Expressions for Tree Traversal – C#

While learning about lambda expressions in C#, I found that trying to create a tree and traversing the tree using lambda expressions made for an interesting study in this topic (as you have to think of ways in which you can use the lambda expression to perform recursion).

The one thing I found is that if you want to use lambda’s for recursion, then you need to make them static.

Here is the code for the tree:

class Tree
{
#region Fields
public int? Id { get; set; }
public int? ParentId { get; set; }
public string Text { get; set; }
#endregion Fields

#region Tree properties
public bool IsRoot { get { return Id == null; } }
public bool IsLeaf { get { return _children == null || _children.Count <= 0; } }
#endregion tree properties

private List<Tree> _children = new List<Tree>();
public List<Tree> Children
{
get { return _children; }
}

public override string ToString()
{
return string.Format("Id:{0},ParentID:{1},Text:{2}", this.Id, this.ParentId, this.Text);
}

And the code for insertion of nodes, traversal and printing:

#region lambda expressions for tree traversal
public static Action<Tree, Action<Tree>> Traverse = (r, d) => r.Children.ForEach(c => { d(c); Traverse(c, d); });
public static Func<int?, Tree, Tree> Find = (id, root) =>
{
if (id == root.Id)
return root;
foreach (Tree c in root.Children)
{
Tree foundItem = Find(id, c);
if (foundItem != null)
return foundItem;
}
return null;
};
public static Func<Tree, Tree, bool> Insert = (root, gi) =>
{
Tree insertionNode = Find(gi.ParentId, root);
if (insertionNode != null)
insertionNode.Children.Add(gi);
return insertionNode != null;
};
public static Action<Tree, int> Print = (root, tab) =>
{
Console.WriteLine(string.Format("{0}{1}", new string(' ', tab), root.ToString()));
root.Children.ForEach(a => Print(a,tab+2));
};
#endregion lambda expressions for tree traversal

Here is some code for representing the tree using XML:

void LoadIntoXML(Tree rootItem)
{
XmlDocument xmlDoc = new XmlDocument();
XmlNode root = xmlDoc.AppendChild(xmlDoc.CreateElement("groups"));
Tree.GenerateXML(xmlDoc, root, rootItem);

StringWriter sw = new StringWriter();
XmlTextWriter writer = new XmlTextWriter(sw);
writer.Formatting = Formatting.Indented;
xmlDoc.WriteTo(writer);

Console.WriteLine(sw.ToString());

}
static void GenerateXML(XmlDocument xmlDocument, XmlNode xmlNode, Tree giNode)
{
if (!giNode.IsRoot)
{
XmlElement element = CreateGIElement(xmlDocument, giNode);
xmlNode = xmlNode.AppendChild(element);

if (!giNode.IsLeaf)
{
element = xmlDocument.CreateElement("children");
xmlNode = xmlNode.AppendChild(element);
}
}
foreach (Tree childGi in giNode.Children)
{
GenerateXML(xmlDocument, xmlNode, childGi);
}
}
static XmlElement CreateGIElement(XmlDocument xmlDocument, Tree giNode)
{
XmlElement element = xmlDocument.CreateElement("group");
element.SetAttribute("group", giNode.Id.ToString());
element.SetAttribute("parentId", giNode.ParentId.ToString());
element.SetAttribute("groupName", giNode.Text);
return element;
}

--------------

Here is some sample data (id, parentId, text, where if parentId is empty, then it is the root node):

1,,Group 1
2,1,Group 2
3,1,Group 3
4,2,Group 4
5,,Group 5
6,4,Group 6
7,5,Group 7

And the same data represented as XML using the above code:

<groups>
<group group="1" parentId="" groupName="Group 1">
<children>
<group group="2" parentId="1" groupName="Group 2">
<children>
<group group="4" parentId="2" groupName="Group 4">
<children>
<group group="6" parentId="4" groupName="Group 6" />
</children>
</group>
</children>
</group>
<group group="3" parentId="1" groupName="Group 3" />
</children>
</group>
<group group="5" parentId="" groupName="Group 5">
<children>
<group group="7" parentId="5" groupName="Group 7" />
</children>
</group>
</groups>

No comments: