Created
July 21, 2012 00:41
-
-
Save xpando/3154042 to your computer and use it in GitHub Desktop.
Extensions methods for iteratively traversing trees using Stack<T> and Queue<T>
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
| public static class IterativeTreeExt | |
| { | |
| public static IEnumerable<T> AsDepthFirstEnumerable<T>(this T head, Func<T, IEnumerable<T>> children) | |
| { | |
| var nodes = new Stack<T>(new [] { head }); | |
| while(nodes.Count > 0) | |
| { | |
| var currentnode = nodes.Pop(); | |
| foreach (var child in children(currentnode)) | |
| nodes.Push(child); | |
| yield return currentnode; | |
| } | |
| } | |
| public static IEnumerable<T> AsBreadthFirstEnumerable<T>(this T head, Func<T, IEnumerable<T>> children) | |
| { | |
| var nodes = new Queue<T>(new[] { head }); | |
| while (nodes.Count > 0) | |
| { | |
| var currentnode = nodes.Dequeue(); | |
| foreach (var child in children(currentnode)) | |
| nodes.Enqueue(child); | |
| yield return currentnode; | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment