Governor Technology Blog
17 May 2010 by Cameron Morrison
A common task when working with tree like data structures is
flattening them out into a list. Usually a recursive function is
used to flatten out the list, which is then iterated over. However,
with the yield keyword (c# 2.0) it's easy make custom trees (or
anything else) directly iterable.
The yield keyword usually has an example
similar to Listing 1 to show usage.
Listing 1. Basic yield example.
public class List
{
//using System.Collections;
public static IEnumerable Power(int number, int exponent)
{
int counter = 0;
int result = 1;
while (counter++ < exponent)
{
result = result * number;
yield return result;
}
}
static void Main()
{
// Display powers of 2 up to the exponent 8:
foreach (int i in Power(2, 8))
{
Console.Write("{0} ", i);
}
}
}
/*
Output:
2 4 8 16 32 64 128 256
*/
This sort of example does not really give an idea of its power.
Today, I needed to iterate depth first over a tree, rather than
create an explicitly recursive function, I decided to make the
class implement IEnumerable and use yield to provide the elements
back to the consumer. Listing 2 is a quick demo of the technique I
used.
Listing 2. Tree flattening.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace IEnumerableTreeWithYield
{
class Program
{
static void Main(string[] args)
{
System.Random rnd = new Random();
Node root = new Node(-1);
for (int i = 0; i <= 10; i++)
{
Node child = new Node(i);
for (int j = 0; j < i; j++)
{
child.Children.Add(new Node(rnd.Next()));
}
root.Children.Add(child);
}
foreach (var c in root) // this is using the IEnumerable interface
{
Console.WriteLine(c.Value);
}
Console.ReadLine();
}
}
class Node : IEnumerable<Node>
{
public List<Node> Children { get; set; }
public int Value { get; set; }
public Node(int value)
{
this.Value = value;
this.Children = new List<Node>();
}
public IEnumerator<Node> GetEnumerator()
{
yield return this;
if (this.Children.Count > 0)
{
foreach (var internalChild in this.Children)
{
foreach (var c in internalChild)
{
yield return c;
}
}
}
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
}
The simple foreach loop at line 27 uses the enumerator, and
recieves a flattened list of the tree. This seems easier, and
probably less error prone, than rolling your own recursion. As an
added benefit of this method, because IEnumerable has been
implemented, you can use Linq queries against the tree!
Leave comment:
