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

   1 // C5 example\r
   2 // 2004-11-09\r
   3 \r
   4 using System;\r
   5 using C5;\r
   6 using SCG = System.Collections.Generic;\r
   7 \r
   8 namespace TreeTraversal\r
   9 {\r
  10   class MyTest\r
  11   {\r
  12     public static void Main(String[] args)\r
  13     {\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
  25     }\r
  26 \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
  29     {\r
  30       if (n == 0)\r
  31         return null;\r
  32       else\r
  33       {\r
  34         int k = n / 2;\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
  37       }\r
  38     }\r
  39   }\r
  40 \r
  41   class Tree<T>\r
  42   {\r
  43     private T val;\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
  47     {\r
  48       this.val = val; this.t1 = t1; this.t2 = t2;\r
  49     }\r
  50 \r
  51     public static void DepthFirst(Tree<T> t, Act<T> act)\r
  52     {\r
  53       IStack<Tree<T>> work = new ArrayList<Tree<T>>();\r
  54       work.Push(t);\r
  55       while (!work.IsEmpty)\r
  56       {\r
  57         Tree<T> cur = work.Pop();\r
  58         if (cur != null)\r
  59         {\r
  60           work.Push(cur.t2);\r
  61           work.Push(cur.t1);\r
  62           act(cur.val);\r
  63         }\r
  64       }\r
  65     }\r
  66 \r
  67     public static void BreadthFirst(Tree<T> t, Act<T> act)\r
  68     {\r
  69       IQueue<Tree<T>> work = new CircularQueue<Tree<T>>();\r
  70       work.Enqueue(t);\r
  71       while (!work.IsEmpty)\r
  72       {\r
  73         Tree<T> cur = work.Dequeue();\r
  74         if (cur != null)\r
  75         {\r
  76           work.Enqueue(cur.t1);\r
  77           work.Enqueue(cur.t2);\r
  78           act(cur.val);\r
  79         }\r
  80       }\r
  81     }\r
  82 \r
  83     public static void Traverse(Tree<T> t, Act<T> act, IList<Tree<T>> work)\r
  84     {\r
  85       work.Clear();\r
  86       work.Add(t);\r
  87       while (!work.IsEmpty)\r
  88       {\r
  89         Tree<T> cur = work.Remove();\r
  90         if (cur != null)\r
  91         {\r
  92           if (work.FIFO)\r
  93           {\r
  94             work.Add(cur.t1);\r
  95             work.Add(cur.t2);\r
  96           }\r
  97           else\r
  98           {\r
  99             work.Add(cur.t2);\r
 100             work.Add(cur.t1);\r
 101           }\r
 102           act(cur.val);\r
 103         }\r
 104       }\r
 105     }\r
 106   }\r
 107 }