mcs/class/Mono.C5/UserGuideExamples/TreeTraversal.cs

   1 // C5 example
   2 // 2004-11-09
   3
   4 using System;
   5 using C5;
   6 using SCG = System.Collections.Generic;
   7
   8 namespace TreeTraversal
   9 {
  10   class MyTest
  11   {
  12     public static void Main(String[] args)
  13     {
  14       Tree<int> t = MakeTree(1, 15);
  15       Act<int> act = delegate(int val) { Console.Write("{0} ", val); };
  16       Console.WriteLine("Depth-first:");
  17       Tree<int>.DepthFirst(t, act);
  18       Console.WriteLine("\nBreadth-first:");
  19       Tree<int>.BreadthFirst(t, act);
  20       Console.WriteLine("\nDepth-first:");
  21       Tree<int>.Traverse(t, act, new ArrayList<Tree<int>>());
  22       Console.WriteLine("\nBreadth-first:");
  23       Tree<int>.Traverse(t, act, new LinkedList<Tree<int>>());
  24       Console.WriteLine();
  25     }
  26
  27     // Build n-node tree with root numbered b and other nodes numbered b+1..b+n
  28     public static Tree<int> MakeTree(int b, int n)
  29     {
  30       if (n == 0)
  31         return null;
  32       else
  33       {
  34         int k = n / 2;
  35         Tree<int> t1 = MakeTree(b + 1, k), t2 = MakeTree(b + k + 1, n - 1 - k);
  36         return new Tree<int>(b, t1, t2);
  37       }
  38     }
  39   }
  40
  41   class Tree<T>
  42   {
  43     private T val;
  44     private Tree<T> t1, t2;
  45     public Tree(T val) : this(val, null, null) { }
  46     public Tree(T val, Tree<T> t1, Tree<T> t2)
  47     {
  48       this.val = val; this.t1 = t1; this.t2 = t2;
  49     }
  50
  51     public static void DepthFirst(Tree<T> t, Act<T> act)
  52     {
  53       IStack<Tree<T>> work = new ArrayList<Tree<T>>();
  54       work.Push(t);
  55       while (!work.IsEmpty)
  56       {
  57         Tree<T> cur = work.Pop();
  58         if (cur != null)
  59         {
  60           work.Push(cur.t2);
  61           work.Push(cur.t1);
  62           act(cur.val);
  63         }
  64       }
  65     }
  66
  67     public static void BreadthFirst(Tree<T> t, Act<T> act)
  68     {
  69       IQueue<Tree<T>> work = new CircularQueue<Tree<T>>();
  70       work.Enqueue(t);
  71       while (!work.IsEmpty)
  72       {
  73         Tree<T> cur = work.Dequeue();
  74         if (cur != null)
  75         {
  76           work.Enqueue(cur.t1);
  77           work.Enqueue(cur.t2);
  78           act(cur.val);
  79         }
  80       }
  81     }
  82
  83     public static void Traverse(Tree<T> t, Act<T> act, IList<Tree<T>> work)
  84     {
  85       work.Clear();
  86       work.Add(t);
  87       while (!work.IsEmpty)
  88       {
  89         Tree<T> cur = work.Remove();
  90         if (cur != null)
  91         {
  92           if (work.FIFO)
  93           {
  94             work.Add(cur.t1);
  95             work.Add(cur.t2);
  96           }
  97           else
  98           {
  99             work.Add(cur.t2);
 100             work.Add(cur.t1);
 101           }
 102           act(cur.val);
 103         }
 104       }
 105     }
 106   }
 107 }