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 }