Skip to content

Instantly share code, notes, and snippets.

@rogovski
Created June 19, 2014 15:28
Show Gist options
  • Select an option

  • Save rogovski/3ad62d2cec47ffcde7bb to your computer and use it in GitHub Desktop.

Select an option

Save rogovski/3ad62d2cec47ffcde7bb to your computer and use it in GitHub Desktop.
"Imperative" Tree Traversals in C# using stacks and queues
using System;
using System.Collections.Generic;
namespace TreeTraversals
{
public static class RT {
public static RoseTree<T> Node<T>(T value)
{
return new RoseTree<T>()
{
ChildNodes = new List<RoseTree<T>>(),
Value = value
};
}
public static RoseTree<T> Children<T>(this RoseTree<T> obj, params RoseTree<T>[] children)
{
if (obj.ChildNodes == null)
{
obj.ChildNodes = new List<RoseTree<T>>();
}
foreach (var c in children)
{
obj.ChildNodes.Add(c);
}
return obj;
}
}
public class RoseTree<T>
{
public List<RoseTree<T>> ChildNodes { get; set; }
public T Value { get; set; }
}
public class PreOrderTraversal
{
public List<T> Traverse<T>(RoseTree<T> tree)
{
var stack = new Stack<RoseTree<T>>();
var accum = new List<T>();
accum.Add(tree.Value);
if (tree.ChildNodes.Count == 0)
{
return accum;
}
for (var i = tree.ChildNodes.Count - 1; i >= 0; i--)
{
stack.Push(tree.ChildNodes[i]);
}
return TraverseRest<T>(accum, stack);
}
private List<T> TraverseRest<T>(List<T> accum, Stack<RoseTree<T>> stack)
{
while (stack.Count != 0)
{
var subtree = stack.Pop();
accum.Add(subtree.Value);
for (var i = subtree.ChildNodes.Count - 1; i >= 0; i--)
{
stack.Push(subtree.ChildNodes[i]);
}
}
return accum;
}
}
public class RunTests
{
private List<string> PreOrderTraversalTest()
{
var tree =
RT.Node("F").Children(
RT.Node("B")
.Children(
RT.Node("A"),
RT.Node("D")
.Children(
RT.Node("C"),
RT.Node("E")
)
),
RT.Node("G")
.Children(
RT.Node("I")
.Children(
RT.Node("H")
)
)
);
var preord = new PreOrderTraversal();
// >> F, B, A, D, C, E, G, I, H
return preord.Traverse(tree);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment