6 using SCG = System.Collections.Generic;
\r
8 namespace TreeTraversal
\r
12 public static void Main(String[] args)
\r
14 Tree<int> t = MakeTree(1, 15);
\r
15 Act<int> act = delegate(int val) { Console.Write("{0} ", val); };
\r
16 Console.WriteLine("Depth-first:");
\r
17 Tree<int>.DepthFirst(t, act);
\r
18 Console.WriteLine("\nBreadth-first:");
\r
19 Tree<int>.BreadthFirst(t, act);
\r
20 Console.WriteLine("\nDepth-first:");
\r
21 Tree<int>.Traverse(t, act, new ArrayList<Tree<int>>());
\r
22 Console.WriteLine("\nBreadth-first:");
\r
23 Tree<int>.Traverse(t, act, new LinkedList<Tree<int>>());
\r
24 Console.WriteLine();
\r
27 // Build n-node tree with root numbered b and other nodes numbered b+1..b+n
\r
28 public static Tree<int> MakeTree(int b, int n)
\r
35 Tree<int> t1 = MakeTree(b + 1, k), t2 = MakeTree(b + k + 1, n - 1 - k);
\r
36 return new Tree<int>(b, t1, t2);
\r
44 private Tree<T> t1, t2;
\r
45 public Tree(T val) : this(val, null, null) { }
\r
46 public Tree(T val, Tree<T> t1, Tree<T> t2)
\r
48 this.val = val; this.t1 = t1; this.t2 = t2;
\r
51 public static void DepthFirst(Tree<T> t, Act<T> act)
\r
53 IStack<Tree<T>> work = new ArrayList<Tree<T>>();
\r
55 while (!work.IsEmpty)
\r
57 Tree<T> cur = work.Pop();
\r
67 public static void BreadthFirst(Tree<T> t, Act<T> act)
\r
69 IQueue<Tree<T>> work = new CircularQueue<Tree<T>>();
\r
71 while (!work.IsEmpty)
\r
73 Tree<T> cur = work.Dequeue();
\r
76 work.Enqueue(cur.t1);
\r
77 work.Enqueue(cur.t2);
\r
83 public static void Traverse(Tree<T> t, Act<T> act, IList<Tree<T>> work)
\r
87 while (!work.IsEmpty)
\r
89 Tree<T> cur = work.Remove();
\r