二叉树、多叉树子路径遍历

  1  ///   <summary>
  2       ///  二叉树
  3       ///   </summary>
  4       ///   <typeparam name="T"></typeparam>
  5       class Road<T>
  6     {
  7         T data;
  8         Road<T> Lnode, rnode, pnode;
  9          public T Data
 10         {
 11              get {  return data; }
 12              set { data = value; }
 13         }
 14          public Road<T> LNode
 15         {
 16              get {  return Lnode; }
 17              set { Lnode = value; }
 18         }
 19          public Road<T> RNode
 20         {
 21              get {  return rnode; }
 22              set { rnode = value; }
 23         }
 24          public Road<T> PNode
 25         {
 26              get {  return pnode; }
 27              set { pnode = value; }
 28         }
 29          public Road() { }
 30          public Road(T data)
 31         {
 32              this.data = data;
 33         }
 34     }
 35 
 36      class 叉树测试
 37     {
 38          // 测试的主方法   
 39           static  void Main( string[] args)
 40         {
 41              Road<string> rootNode = BinTree();
 42               Stack<string> stack = new Stack<string>();
 43               findPathNode<string>(rootNode, stack);
 44               Console.WriteLine("");
 45 
 46             RoadLink< string> roadNode = BinRoad();
 47             Stack< string> roadStack =  new Stack< string>();
 48             findPath< string>(roadNode, roadStack);
 49             Console.WriteLine( " over ");
 50             Console.Read();
 51         }
 52        
 53          static Road< string> BinTree()
 54         {
 55             Road< string>[] binTree =  new Road< string>[ 8];
 56 
 57              // 创建节点  
 58              binTree[ 0] =  new Road< string>( " A ");
 59             binTree[ 1] =  new Road< string>( " B ");
 60             binTree[ 2] =  new Road< string>( " C ");
 61             binTree[ 3] =  new Road< string>( " D ");
 62             binTree[ 4] =  new Road< string>( " E ");
 63             binTree[ 5] =  new Road< string>( " F ");
 64             binTree[ 6] =  new Road< string>( " G ");
 65             binTree[ 7] =  new Road< string>( " H ");
 66 
 67              // 使用层次遍历二叉树的思想，构造一个已知的二叉树  
 68              binTree[ 0].LNode = binTree[ 1];
 69             binTree[ 0].RNode = binTree[ 2];
 70             binTree[ 1].RNode = binTree[ 3];
 71             binTree[ 2].LNode = binTree[ 4];
 72             binTree[ 2].RNode = binTree[ 5];
 73             binTree[ 3].LNode = binTree[ 6];
 74             binTree[ 3].RNode = binTree[ 7];
 75 
 76              // 返回二叉树根节点  
 77               return binTree[ 0];
 78         }
 79               
 80          static  void findPathNode<T>(Road<T> root, Stack<T> stack)
 81         {
 82              if (root ==  null)
 83             {
 84                  return;
 85             }
 86              //  把当前结点进栈  
 87              stack.Push(root.Data);
 88              //  如果是叶子结点，而且和为给定的值，则打印路径  
 89               bool isLeaf = root.LNode ==  null && root.RNode ==  null;
 90              if (isLeaf)
 91             {
 92                 List< object> tmpDatas =  new List< object>();
 93                  foreach ( var item  in stack)
 94                 {
 95                     tmpDatas.Add(item);
 96                 }
 97                 tmpDatas.Reverse();
 98 
 99                  foreach ( var item  in tmpDatas)
100                 {
101                     Console.Write(item +  " - ");
102                 }
103                 Console.WriteLine( "");
104                 
105             }
106 
107              //  如果不是叶子结点，则遍历它的子结点  
108               if (root.LNode !=  null)
109             {
110                 findPathNode(root.LNode, stack);
111             }
112              if (root.RNode !=  null)
113             {
114                 findPathNode(root.RNode, stack);
115             }
116              //  在返回到父结点之前，在路径上删除当前结点  
117              stack.Pop();
118         }
119 
120          static RoadLink< string> BinRoad()
121         {
122             RoadLink< string>[] binTree =  new RoadLink< string>[ 10];
123 
124              // 创建节点  
125              binTree[ 0] =  new RoadLink< string>( " A ");
126             binTree[ 1] =  new RoadLink< string>( " B ");
127             binTree[ 2] =  new RoadLink< string>( " C ");
128             binTree[ 3] =  new RoadLink< string>( " D ");
129             binTree[ 4] =  new RoadLink< string>( " E ");
130             binTree[ 5] =  new RoadLink< string>( " F ");
131             binTree[ 6] =  new RoadLink< string>( " G ");
132             binTree[ 7] =  new RoadLink< string>( " H ");
133             binTree[ 8] =  new RoadLink< string>( " I ");
134             binTree[ 9] =  new RoadLink< string>( " J ");
135 
136              // 使用层次遍历二叉树的思想，构造一个已知的二叉树  
137              binTree[ 0].SubRoads =  new List< object>();
138             binTree[ 0].SubRoads.Add(binTree[ 1]);
139             binTree[ 0].SubRoads.Add(binTree[ 2]);
140 
141             binTree[ 1].SubRoads =  new List< object>();
142             binTree[ 1].SubRoads.Add(binTree[ 3]);
143 
144             binTree[ 2].SubRoads =  new List< object>();
145             binTree[ 2].SubRoads.Add(binTree[ 3]);
146 
147             binTree[ 3].SubRoads =  new List< object>();
148             binTree[ 3].SubRoads.Add(binTree[ 4]);
149             binTree[ 3].SubRoads.Add(binTree[ 5]);
150             binTree[ 3].SubRoads.Add(binTree[ 7]);
151 
152             binTree[ 4].SubRoads =  new List< object>();
153             binTree[ 4].SubRoads.Add(binTree[ 6]);
154 
155             binTree[ 5].SubRoads =  new List< object>();
156             binTree[ 5].SubRoads.Add(binTree[ 6]);
157 
158             binTree[ 7].SubRoads =  new List< object>();
159             binTree[ 7].SubRoads.Add(binTree[ 8]);
160             binTree[ 7].SubRoads.Add(binTree[ 9]);
161 
162             binTree[ 8].SubRoads =  new List< object>();
163             binTree[ 8].SubRoads.Add(binTree[ 6]);
164 
165             binTree[ 9].SubRoads =  new List< object>();
166             binTree[ 9].SubRoads.Add(binTree[ 6]);
167 
168              // 返回二叉树根节点  
169               return binTree[ 0];
170         }
171 
172          static  void findPath<T>(RoadLink<T> root, Stack<T> stack)
173         {
174              if (root ==  null)
175             {
176                  return;
177             }
178              //  把当前结点进栈  
179              stack.Push(root.Data);
180              //  如果是叶子结点，而且和为给定的值，则打印路径  
181               bool isLeaf = root.SubRoads ==  null;
182              // bool isLeaf = root.Data.Equals("E"); // 寻找的点
183               if (isLeaf)
184             {
185                 List< object> tmpDatas =  new List< object>();
186                  foreach ( var item  in stack)
187                 {
188                     tmpDatas.Add(item);
189                 }
190                 tmpDatas.Reverse();
191 
192                  foreach ( var item  in tmpDatas)
193                 {
194                     Console.Write(item +  " - ");
195                 }
196                 Console.WriteLine( "");
197 
198             }
199              //  如果不是叶子结点，则遍历它的子结点  
200               if (root.SubRoads !=  null)
201             {
202                  foreach ( var item  in root.SubRoads)
203                 {
204                      var obj = item  as RoadLink<T>;
205                     findPath(obj, stack);
206                 }
207 
208             }
209              //  在返回到父结点之前，在路径上删除当前结点  
210              stack.Pop();
211         }
212     }
213 
214      ///   <summary>
215       ///  多叉树
216       ///   </summary>
217       ///   <typeparam name="T"></typeparam>
218       class RoadLink<T>
219     {
220         T data;
221          ///   <summary>
222           ///  子节点
223           ///   </summary>
224          List< object> subRoads =  null;
225          public T Data
226         {
227              get {  return data; }
228              set { data = value; }
229         }
230          ///   <summary>
231           ///  子节点
232           ///   </summary>
233           public List< object> SubRoads
234         {
235              get {  return subRoads; }
236              set { subRoads = value; }
237         }
238          public RoadLink() { }
239          public RoadLink(T data)
240         {
241              this.data = data;
242         }
243 
244          public  void AddSubRoad( object subRoad)
245         {
246              if (subRoads ==  null) subRoads =  new List< object>();
247              if (subRoads.Contains(subRoad)) subRoads.Add(subRoad);
248         }
249     }