In the article, Lambdas for Junior Developers, I built a TreeNode class with a Find method to demonstrate the use of lambdas. This was merely an example and not something I would actually use without some work. I am going to take the fledgling TreeNode class and work on it as a basis for a tree class library.
To recap, here’s the class I used in the previous article.
public class TreeNode
{
private List<TreeNode> children = new List<TreeNode>();
public IEnumerable<TreeNode> Children
{
get { return children; }
}
public string Text { get; set; }
public TreeNode(string text)
{
this.Text = text;
}
public TreeNode Find(Func<TreeNode, bool> predicate)
{
if (predicate(this))
{
return this;
}
foreach (TreeNode node in children)
{
TreeNode found = node.Find(predicate);
if (found != null)
{
return found;
}
}
return null;
}
public TreeNode With(TreeNode node)
{
children.Add(node);
return this;
}
public TreeNode With(IEnumerable<TreeNode> nodes)
{
children.AddRange(nodes);
return this;
}
}
This was the test I used to demonstrate using the Find method. It also shows how to build a tree with this particular class.
[TestMethod]
public void ShouldFindNode()
{
var tree = new TreeNode("first").With(new TreeNode("second").With(new TreeNode("third")))
.With(new TreeNode("fourth"))
.With(new TreeNode("fifth").With(new TreeNode("sixth")));
TreeNode found = tree.Find(node => node.Text.StartsWith("t"));
Assert.AreEqual("third", found.Text);
}
Each node is limited to containing text. This isn’t very useful. What if I wanted a tree of images, files, or some other type? This can be accomplished by using generics. This will give the tree flexibility for the type of item it contains.
public class TreeNode<T>
{
private List<TreeNode<T>> children = new List<TreeNode<T>>();
public IEnumerable<TreeNode<T>> Children
{
get { return children; }
}
public T Item { get; set; }
public TreeNode(T item)
{
this.Item = item;
}
public TreeNode<T> Find(Func<TreeNode<T>, bool> predicate)
{
if (predicate(this))
{
return this;
}
foreach (var node in children)
{
var found = node.Find(predicate);
if (found != null)
{
return found;
}
}
return null;
}
public TreeNode<T> With(TreeNode<T> node)
{
children.Add(node);
return this;
}
public TreeNode<T> With(IEnumerable<TreeNode<T>> nodes)
{
children.AddRange(nodes);
return this;
}
}
This has the unfortunate effect of making the class unwieldy.
[TestMethod]
public void ShouldFindNode()
{
var tree = new TreeNode<string>("first")
.With(new TreeNode<string>("second")
.With(new TreeNode<string>("third")))
.With(new TreeNode<string>("fourth"))
.With(new TreeNode<string>("fifth")
.With(new TreeNode<string>("sixth")));
TreeNode<string> found = tree.Find(node => node.Item.StartsWith("t"));
Assert.AreEqual("third", found.Item);
}
This can be cleaned up using generic inference. First, I will create a static Tree class with a factory method to create a TreeNode. I usually prefer to name a class that does this after the generic version but without the generic parameters, but in this case I think Tree is more appropriate.
public static class Tree
{
public static TreeNode<T> Create<T>(T item)
{
return new TreeNode<T>(item);
}
}
Then I will create and overloads for the With method to add items to the tree.
public TreeNode<T> With(T item)
{
children.Add(new TreeNode<T>(item));
return this;
}
public TreeNode<T> With(T item, Func<TreeNode<T>, TreeNode<T>> func)
{
var node = func(new TreeNode<T>(item));
children.Add(node);
return this;
}
public TreeNode<T> With(IEnumerable<T> items)
{
children.AddRange(items.Select(item => new TreeNode<T>(item)));
return this;
}
This makes the unit test much cleaner.
[TestMethod]
public void ShouldFindNode()
{
var tree = Tree.Create("first").With("second", n => n.With("third"))
.With("fourth")
.With("fifth", n => n.With("sixth"));
TreeNode<string> found = tree.Find(node => node.Item.StartsWith("t"));
Assert.AreEqual("third", found.Item);
}
I may want tree structures with different behavior. I can solve this with an interface.
public interface ITreeNode<T>
{
IEnumerable<ITreeNode<T>> Children { get; }
T Item { get; }
void AddChild(ITreeNode<T> node);
}
This requires a slight modification to the TreeNode class. It needs to implement this interface, and it needs to define Children as an IEnumerable<ITreeNode<T>>.
public class TreeNode<T> : ITreeNode<T>
{
...
public IEnumerable<ITreeNode<T>> Children
{
get { return children; }
}
...
}
You’re probably wondering what happened to the Find and With methods. I’ve defined all query and fluent builder methods as extension methods to work on any class that implements ITreeNode<T>. The non-fluent AddChild method was necessary to continue manipulating the state of TreeNode<T>.
public static class Tree
{
public static TreeNode<T> Create<T>(T item)
{
return new TreeNode<T>(item);
}
public static ITreeNode<T> Find<T>(this ITreeNode<T> node,
Func<ITreeNode<T>, bool> predicate)
{
if (predicate(node))
{
return node;
}
foreach (var child in node.Children)
{
var found = child.Find(predicate);
if (found != null)
{
return found;
}
}
return null;
}
public static ITreeNode<T> With<T>(this ITreeNode<T> node, ITreeNode<T> child)
{
node.AddChild(child);
return node;
}
public static ITreeNode<T> With<T>(this ITreeNode<T> node,
IEnumerable<ITreeNode<T>> children)
{
foreach (var child in children)
{
node.AddChild(child);
}
return node;
}
public static ITreeNode<T> With<T>(this ITreeNode<T> node, T item)
{
node.AddChild(new TreeNode<T>(item));
return node;
}
public static ITreeNode<T> With<T>(this ITreeNode<T> node, T item, Func<ITreeNode<T>,
ITreeNode<T>> func)
{
var child = func(new TreeNode<T>(item));
node.AddChild(child);
return node;
}
public static ITreeNode<T> With<T>(this ITreeNode<T> node, IEnumerable<T> items)
{
return node.With(items.Select(item => new TreeNode<T>(item)));
}
}
I realize that it is useful to navigate up a chain, so I will go ahead and add the Parent property. This lead me to consider a few implications: if the parent is null then the node is a root, AddChild needs to return the child to support the lambdas in my test, and this code could use contracts.
public interface ITreeNode<T>
{
IEnumerable<ITreeNode<T>> Children { get; }
ITreeNode<T> Parent { get; }
T Item { get; }
TreeNode<T> AddChild(T item);
}
public class TreeNode<T> : ITreeNode<T>
{
private List<ITreeNode<T>> children = new List<ITreeNode<T>>();
public IEnumerable<ITreeNode<T>> Children
{
get { return children; }
}
public ITreeNode<T> Parent { get; private set; }
public T Item { get; private set; }
public TreeNode(T item) : this(item, null)
{
}
public TreeNode(T item, ITreeNode<T> parent)
{
this.Item = item;
this.Parent = parent;
}
public TreeNode<T> AddChild(T item)
{
Contract.Ensures(Contract.Result<ITreeNode<T>>() != null);
var child = new TreeNode<T>(item);
child.Parent = this;
children.Add(child);
return child;
}
}
public static class Tree
{
public static TreeNode<T> Create<T>(T item)
{
return new TreeNode<T>(item);
}
public static ITreeNode<T> Find<T>(this ITreeNode<T> node,
Func<ITreeNode<T>, bool> predicate)
{
Contract.Requires<ArgumentNullException>(node != null);
Contract.Requires<ArgumentNullException>(predicate != null);
if (predicate(node))
{
return node;
}
foreach (var child in node.Children)
{
var found = child.Find(predicate);
if (found != null)
{
return found;
}
}
return null;
}
public static bool IsRoot<T>(this ITreeNode<T> node)
{
Contract.Requires<ArgumentNullException>(node != null);
return node.Parent == null;
}
public static ITreeNode<T> With<T>(this ITreeNode<T> node, ITreeNode<T> child)
{
Contract.Requires<ArgumentNullException>(node != null);
Contract.Requires<ArgumentNullException>(child != null);
Contract.Ensures(Contract.Result<ITreeNode<T>>() != null);
node.AddChild(child.Item);
return node;
}
public static ITreeNode<T> With<T>(this ITreeNode<T> node,
IEnumerable<ITreeNode<T>> children)
{
Contract.Requires<ArgumentNullException>(node != null);
Contract.Requires<ArgumentNullException>(children != null);
Contract.Ensures(Contract.Result<ITreeNode<T>>() != null);
foreach (var child in children)
{
node.AddChild(child.Item);
}
return node;
}
public static ITreeNode<T> With<T>(this ITreeNode<T> node, T item)
{
Contract.Requires<ArgumentNullException>(node != null);
Contract.Ensures(Contract.Result<ITreeNode<T>>() != null);
node.AddChild(item);
return node;
}
public static ITreeNode<T> With<T>(this ITreeNode<T> node, T item, Func<ITreeNode<T>,
ITreeNode<T>> func)
{
Contract.Requires<ArgumentNullException>(node != null);
Contract.Requires<ArgumentNullException>(func != null);
Contract.Ensures(Contract.Result<ITreeNode<T>>() != null);
func(node.AddChild(item));
return node;
}
public static ITreeNode<T> With<T>(this ITreeNode<T> node, IEnumerable<T> items)
{
Contract.Requires<ArgumentNullException>(node != null);
Contract.Requires<ArgumentNullException>(items != null);
Contract.Ensures(Contract.Result<ITreeNode<T>>() != null);
return node.With(items.Select(item => new TreeNode<T>(item)));
}
}
This class is making a fine beginning, and I believe it’s useable as a tree structure. The next steps are to add the appropriate methods to support query expressions, and add useful, tree-specific functionality such as pruning. Stay tuned.