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

 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 }