Created
June 19, 2014 15:28
-
-
Save rogovski/3ad62d2cec47ffcde7bb to your computer and use it in GitHub Desktop.
"Imperative" Tree Traversals in C# using stacks and queues
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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