public static class TreeExtensions
{
public static IEnumerable<R> TraverseDepthFirst<T, R>(
this T t,
Func<T, R> valueselect,
Func<T, IEnumerable<T>> childselect)
{
return t.TraverseDepthFirstWithParent(valueselect, childselect).Select(x => x.Key);
}
public static IEnumerable<KeyValuePair<R, T>> TraverseDepthFirstWithParent<T, R>(
this T t,
Func<T, R> valueselect,
Func<T, IEnumerable<T>> childselect)
{
return t.TraverseDepthFirstWithParent(default(T), valueselect, childselect);
}
static IEnumerable<KeyValuePair<R, T>> TraverseDepthFirstWithParent<T, R>(
this T t,
T parent,
Func<T, R> valueselect,
Func<T, IEnumerable<T>> childselect)
{
yield return new KeyValuePair<R, T>(valueselect(t), parent);
foreach (var i in childselect(t))
{
foreach (var item in i.TraverseDepthFirstWithParent(t, valueselect, childselect))
{
yield return item;
}
}
}
public static IEnumerable<R> TraverseBreadthFirst<T, R>(
this T t,
Func<T, R> valueselect,
Func<T, IEnumerable<T>> childselect)
{
return t.TraverseBreadthFirstWithParent(valueselect, childselect).Select(x => x.Key);
}
public static IEnumerable<KeyValuePair<R, T>> TraverseBreadthFirstWithParent<T, R>(
this T t,
Func<T, R> valueselect,
Func<T, IEnumerable<T>> childselect)
{
yield return new KeyValuePair<R, T>(valueselect(t), default(T));
List<T> children = new List<T>();
foreach (var e in childselect(t))
{
children.Add(e);
yield return new KeyValuePair<R, T>(valueselect(e), t);
}
while (children.Count > 0)
{
foreach (var e in new List<T>(children))
{
children.Remove(e);
foreach (var c in childselect(e))
{
children.Add(c);
yield return new KeyValuePair<R, T>(valueselect(c), e);
}
}
}
}
}
// usage
interface INode<T>
{
T Value { get; }
IEnumerable<INode> Children { get; }
}
INode<int> root = ...
foreach (var i in root.TraverseDepthFirst(x => x.Value, x => x.Children))
{
Console.WriteLine(i);
}
