-// C5 example\r
-// 2004-11-09\r
-\r
-using System;\r
-using C5;\r
-using SCG = System.Collections.Generic;\r
-\r
-namespace TreeTraversal\r
-{\r
- class MyTest\r
- {\r
- public static void Main(String[] args)\r
- {\r
- Tree<int> t = MakeTree(1, 15);\r
- Act<int> act = delegate(int val) { Console.Write("{0} ", val); };\r
- Console.WriteLine("Depth-first:");\r
- Tree<int>.DepthFirst(t, act);\r
- Console.WriteLine("\nBreadth-first:");\r
- Tree<int>.BreadthFirst(t, act);\r
- Console.WriteLine("\nDepth-first:");\r
- Tree<int>.Traverse(t, act, new ArrayList<Tree<int>>());\r
- Console.WriteLine("\nBreadth-first:");\r
- Tree<int>.Traverse(t, act, new LinkedList<Tree<int>>());\r
- Console.WriteLine();\r
- }\r
-\r
- // Build n-node tree with root numbered b and other nodes numbered b+1..b+n\r
- public static Tree<int> MakeTree(int b, int n)\r
- {\r
- if (n == 0)\r
- return null;\r
- else\r
- {\r
- int k = n / 2;\r
- Tree<int> t1 = MakeTree(b + 1, k), t2 = MakeTree(b + k + 1, n - 1 - k);\r
- return new Tree<int>(b, t1, t2);\r
- }\r
- }\r
- }\r
-\r
- class Tree<T>\r
- {\r
- private T val;\r
- private Tree<T> t1, t2;\r
- public Tree(T val) : this(val, null, null) { }\r
- public Tree(T val, Tree<T> t1, Tree<T> t2)\r
- {\r
- this.val = val; this.t1 = t1; this.t2 = t2;\r
- }\r
-\r
- public static void DepthFirst(Tree<T> t, Act<T> act)\r
- {\r
- IStack<Tree<T>> work = new ArrayList<Tree<T>>();\r
- work.Push(t);\r
- while (!work.IsEmpty)\r
- {\r
- Tree<T> cur = work.Pop();\r
- if (cur != null)\r
- {\r
- work.Push(cur.t2);\r
- work.Push(cur.t1);\r
- act(cur.val);\r
- }\r
- }\r
- }\r
-\r
- public static void BreadthFirst(Tree<T> t, Act<T> act)\r
- {\r
- IQueue<Tree<T>> work = new CircularQueue<Tree<T>>();\r
- work.Enqueue(t);\r
- while (!work.IsEmpty)\r
- {\r
- Tree<T> cur = work.Dequeue();\r
- if (cur != null)\r
- {\r
- work.Enqueue(cur.t1);\r
- work.Enqueue(cur.t2);\r
- act(cur.val);\r
- }\r
- }\r
- }\r
-\r
- public static void Traverse(Tree<T> t, Act<T> act, IList<Tree<T>> work)\r
- {\r
- work.Clear();\r
- work.Add(t);\r
- while (!work.IsEmpty)\r
- {\r
- Tree<T> cur = work.Remove();\r
- if (cur != null)\r
- {\r
- if (work.FIFO)\r
- {\r
- work.Add(cur.t1);\r
- work.Add(cur.t2);\r
- }\r
- else\r
- {\r
- work.Add(cur.t2);\r
- work.Add(cur.t1);\r
- }\r
- act(cur.val);\r
- }\r
- }\r
- }\r
- }\r
+// C5 example
+// 2004-11-09
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace TreeTraversal
+{
+ class MyTest
+ {
+ public static void Main(String[] args)
+ {
+ Tree<int> t = MakeTree(1, 15);
+ Act<int> act = delegate(int val) { Console.Write("{0} ", val); };
+ Console.WriteLine("Depth-first:");
+ Tree<int>.DepthFirst(t, act);
+ Console.WriteLine("\nBreadth-first:");
+ Tree<int>.BreadthFirst(t, act);
+ Console.WriteLine("\nDepth-first:");
+ Tree<int>.Traverse(t, act, new ArrayList<Tree<int>>());
+ Console.WriteLine("\nBreadth-first:");
+ Tree<int>.Traverse(t, act, new LinkedList<Tree<int>>());
+ Console.WriteLine();
+ }
+
+ // Build n-node tree with root numbered b and other nodes numbered b+1..b+n
+ public static Tree<int> MakeTree(int b, int n)
+ {
+ if (n == 0)
+ return null;
+ else
+ {
+ int k = n / 2;
+ Tree<int> t1 = MakeTree(b + 1, k), t2 = MakeTree(b + k + 1, n - 1 - k);
+ return new Tree<int>(b, t1, t2);
+ }
+ }
+ }
+
+ class Tree<T>
+ {
+ private T val;
+ private Tree<T> t1, t2;
+ public Tree(T val) : this(val, null, null) { }
+ public Tree(T val, Tree<T> t1, Tree<T> t2)
+ {
+ this.val = val; this.t1 = t1; this.t2 = t2;
+ }
+
+ public static void DepthFirst(Tree<T> t, Act<T> act)
+ {
+ IStack<Tree<T>> work = new ArrayList<Tree<T>>();
+ work.Push(t);
+ while (!work.IsEmpty)
+ {
+ Tree<T> cur = work.Pop();
+ if (cur != null)
+ {
+ work.Push(cur.t2);
+ work.Push(cur.t1);
+ act(cur.val);
+ }
+ }
+ }
+
+ public static void BreadthFirst(Tree<T> t, Act<T> act)
+ {
+ IQueue<Tree<T>> work = new CircularQueue<Tree<T>>();
+ work.Enqueue(t);
+ while (!work.IsEmpty)
+ {
+ Tree<T> cur = work.Dequeue();
+ if (cur != null)
+ {
+ work.Enqueue(cur.t1);
+ work.Enqueue(cur.t2);
+ act(cur.val);
+ }
+ }
+ }
+
+ public static void Traverse(Tree<T> t, Act<T> act, IList<Tree<T>> work)
+ {
+ work.Clear();
+ work.Add(t);
+ while (!work.IsEmpty)
+ {
+ Tree<T> cur = work.Remove();
+ if (cur != null)
+ {
+ if (work.FIFO)
+ {
+ work.Add(cur.t1);
+ work.Add(cur.t2);
+ }
+ else
+ {
+ work.Add(cur.t2);
+ work.Add(cur.t1);
+ }
+ act(cur.val);
+ }
+ }
+ }
+ }