Consider the challenge of in-order element retrieval from a binary-tree. This is a recursive problem, which lends itself to a push-model, not a pull-model. There is no traditional for loop that returns each element in increasing order. One would need to push the elements to a list first, and then walk the list.
Enumerators solve this problem with some compiler-magic. See Eric Lippert's blog on details of this.
Problem Statement: We need a generic collection that supports fast searching, and that we can iterate in two directions (increasing, and decreasing).
Solution: A generic Binary Tree. Let's code it up.
public class BinaryTree<T> where T : IComparable
We need it to be IComparable so that we can insert it in the correct place.
It makes it easier to find also. Later we'll add the ability to return a
sequence that meets a LessThanEquals clause.
{
public enum Order { Forward, Reverse } // the transversal order
private class Node<X> // the object that our binary tree uses
{
public Node(X value) { this.Value = value; }
public X Value;
public Node<X> Left, Right;
}
private Node<T> root; // the root node of our binary tree
A useful Binary Tree needs to have a good insert function. We'll use
the fact that the items support IComparable in order to put them in
the right place.
public void Add(T value)
{
if (null == this.root) this.root = new Node<T>(value);
else Add(Node<T> node, T value)
}
private static void Add(Node<T> node, T value) // we code this using
{ // the iterative style
Node<T> current = node; // rather than the
bool done = false; // recursive style
while (!done)
switch (current.Value.CompareTo(value)) {
case 1: // Left = less-than
if (null != current.Left) current = current.Left; // walk left
else { current.Left = new Node<T>(value); done = true; }
break;
case -1: // Right = greater-than
if (null != current.Right) current = current.Right; // walk right
else { current.Right = new Node<T>(value); done = true; }
break;
case 0: done = true; break; // we don't insert duplicates
}
}
A fast Find function is the hallmark of a useful Binary Tree collection.
public bool Find(T value)
{
bool found = false; // again, we'll do this iteratively
Node<T> current = this.root;
while ((null != current) && (!found))
switch (current.Value.CompareTo(value)) {
case 1: current = current.Left; break; // walk left
case -1: current = current.Right; break; // walk right
case 0: found = true; break; // item is found
}
return found;
}
For techniques on balancing binary trees, see algorithms + data structures = programs by Nicolas Wirth.
The function to return a sequence is recursive. We will use the yield return
statement to return the current item. You'll note that we appear to suspend
our function at each yield return statement, and then resume at that point when
the next value is requested. The "automatics" in the function are actually stored
between calls, giving IEnumerable functions the flavor of a state-machine. In fact,
that characteristic is exploited by some to create support for green-threads and
micro-threading applications (ala computer games). There are many cool patterns
that are available to state-machine coders that we'll explore in later posts.
public IEnumerable<T> GetAll(Order order)
{
if (null != this.root)
foreach (T t in getAll(order, this.root))
yield return t;
}
private static IEnumerable<T> getAll(Order order, Node<T> node)
{
Node<T> first, last;
// Specify the order to retrieve the items
if (Order.Forward == order) { // tuples would be sweet here.
first = node.Left; last = node.Right;
} else { // Reverse order
first = node.Right; last = node.Left;
}
// FIRST
if (null != first)
foreach (T t in getAll(order, first)) yield return t;
// CURRENT
yield return node.Value;
// LAST
if (null != last)
foreach (T t in getAll(order, last)) yield return t;
// implicit yield break;
}
I'll come back and modify that last function with an optional depth parameter once C# 4 ships. We'll code one more function to round it out.
public IEnumerable<T> LessThanEqual(Order order, T value)
{
// Only return a sequence if there is something in the tree
if (null != this.root)
foreach (T t in lessThanEqual(order, this.root, value))
yield return t;
}
private static IEnumerable<T> lessThanEqual(Order order, Node<T> node, T value)
{
switch (node.Value.CompareTo(value)) {
case -1:
// FIRST
if (Order.Forward == order) {
// value is greater (to our right)
// so output everything to our left
if (null != node.Left)
foreach (T t in getAll(order, node.Left))
yield return t;
} else {
// value is greater (to our right)
// so output those items to our right
// that meet the criteria
if (null != node.Right)
foreach (T t in lessThanEqual(order, node.Right, value))
yield return t;
}
// CURRENT
yield return node.Value;
// LAST
if (Order.Forward == order) {
// value is greater (to our right)
// so output those items to our right
// that meet the criteria
if (null != node.Right)
foreach (T t in lessThanEqual(order, node.Right, value))
yield return t;
} else {
// value is greater (to our right)
// so output everything to our left
if (null != node.Left)
foreach (T t in getAll(order, node.Left))
yield return t;
}
break;
case 1:
if (null != node.Left)
// value is lesser (to our left)
// so output those items to our left
// that meet the criteria
foreach (T t in lessThanEqual(order, node.Left, value))
yield return t;
break;
case 0:
if (Order.Forward == order) {
// FIRST
if (null != node.Left)
foreach (T t in getAll(order, node.Left))
yield return t;
// CURRENT
yield return node.Value;
} else {
// CURRENT
yield return node.Value;
// LAST
if (null != node.Left)
foreach (T t in getAll(order, node.Left))
yield return t;
}
break;
// implicit yield break;
}
}
Let's test it:
static void Main(sting[] args)
{
BinaryTree<int> bt = new BinaryTree();
bt.Add(17);
bt.Add(6);
bt.Add(3);
bt.Add(35);
bt.Add(14);
bt.Add(26);
bt.Add(44);
bt.Add(11);
bt.Add(9);
bt.Add(10);
bt.Add(11); // duplicate test
foreach (int n in bt.LessThanEqual(BinaryTree<int>.Order.Reverse,16))
Console.WriteLine("{0} ", n);
Console.WriteLine("Finding 35 {0}", bt.Find(35));
Console.WriteLine("Finding 112 {0}", bt.Find(112));
}
OUTPUT
14
11
10
9
6
3
Finding 35 True
Finding 112 False
There it is. Enumerating through a collection recursively using the pull model.
