二叉树
二叉树
本篇纯属娱乐，源于整理代码，发现还曾实现过遍历二叉树。
虽然.NET/C#中的各种集合类已经实现了最优的排序设计，但了解基本的算法实现有助于软件开发中的各种权衡和选择。
比如，如果你实现过B+树排序和查找，并将树节点序列化至二进制文件块，则你应该已经了解了各种数据库索引的基本设计。
什么是二叉树？
http://en.wikipedia.org/wiki/Binary_tree
二叉树节点类定义
View Code
1 /// <summary>
2 /// 二叉树节点
3 /// </summary>
4 /// <typeparam name="T"> The item type </typeparam>
5 public class BinaryTreeNode<T>
6 {
7 #region Constructors
8
9 /// <summary>
10 /// 二叉树节点
11 /// </summary>
12 public BinaryTreeNode()
13 {
14 }
15
16 /// <summary>
17 /// 二叉树节点
18 /// </summary>
19 /// <param name="value"> 节点中的值 </param>
20 public BinaryTreeNode(T value)
21 {
22 this .Value = value;
23 }
24
25 /// <summary>
26 /// 二叉树节点
27 /// </summary>
28 /// <param name="value"> 节点中的值 </param>
29 /// <param name="parent"> 节点的父节点 </param>
30 public BinaryTreeNode(T value, BinaryTreeNode<T> parent)
31 {
32 this .Value = value;
33 this .Parent = parent;
34 }
35
36 /// <summary>
37 /// 二叉树节点
38 /// </summary>
39 /// <param name="value"> 节点中的值 </param>
40 /// <param name="parent"> 节点的父节点 </param>
41 /// <param name="left"> 节点的左节点 </param>
42 /// <param name="right"> 节点的右节点 </param>
43 public BinaryTreeNode(T value,
44 BinaryTreeNode<T> parent,
45 BinaryTreeNode<T> left,
46 BinaryTreeNode<T> right)
47 {
48 this .Value = value;
49 this .Right = right;
50 this .Left = left;
51 this .Parent = parent;
52 }
53
54 #endregion
55
56 #region Properties
57
58 /// <summary>
59 /// 节点值
60 /// </summary>
61 public T Value { get ; set ; }
62
63 /// <summary>
64 /// 父节点
65 /// </summary>
66 public BinaryTreeNode<T> Parent { get ; set ; }
67
68 /// <summary>
69 /// 左节点
70 /// </summary>
71 public BinaryTreeNode<T> Left { get ; set ; }
72
73 /// <summary>
74 /// 右节点
75 /// </summary>
76 public BinaryTreeNode<T> Right { get ; set ; }
77
78 /// <summary>
79 /// 是否为根节点
80 /// </summary>
81 public bool IsRoot { get { return Parent == null ; } }
82
83 /// <summary>
84 /// 是否为叶子节点
85 /// </summary>
86 public bool IsLeaf { get { return Left == null && Right == null ; } }
87
88 /// <summary>
89 /// 是否为可访问的
90 /// </summary>
91 internal bool Visited { get ; set ; }
92
93 #endregion
94
95 #region Public Overridden Functions
96
97 /// <summary>
98 /// Returns a <see cref="System.String"/> that represents this instance.
99 /// </summary>
100 /// <returns>
101 /// A <see cref="System.String"/> that represents this instance.
102 /// </returns>
103 public override string ToString()
104 {
105 return Value.ToString();
106 }
107
108 #endregion
109 }
二叉树类实现
View Code
1 /// <summary>
2 /// 二叉树
3 /// </summary>
4 /// <typeparam name="T"> 二叉树中节点内容类型 </typeparam>
5 [SuppressMessage( " Microsoft.Naming " , " CA1710:IdentifiersShouldHaveCorrectSuffix " )]
6 public class BinaryTree<T> : ICollection<T>, IEnumerable<T> where T : IComparable<T>
7 {
8 #region Constructor
9
10 /// <summary>
11 /// 二叉树
12 /// </summary>
13 public BinaryTree()
14 {
15 NumberOfNodes = 0 ;
16 }
17
18 /// <summary>
19 /// 二叉树
20 /// </summary>
21 /// <param name="root"> 二叉树根节点 </param>
22 public BinaryTree(BinaryTreeNode<T> root)
23 : this ()
24 {
25 this .Root = root;
26 }
27
28 #endregion
29
30 #region Properties
31
32 /// <summary>
33 /// 树的根节点
34 /// </summary>
35 public BinaryTreeNode<T> Root { get ; set ; }
36
37 /// <summary>
38 /// 树中节点的数量
39 /// </summary>
40 protected int NumberOfNodes { get ; set ; }
41
42 /// <summary>
43 /// 树是否为空
44 /// </summary>
45 public bool IsEmpty { get { return Root == null ; } }
46
47 /// <summary>
48 /// 获取树中节点的最小值
49 /// </summary>
50 public T MinValue
51 {
52 get
53 {
54 if (IsEmpty)
55 return default (T);
56
57 BinaryTreeNode<T> minNode = Root;
58 while (minNode.Left != null )
59 minNode = minNode.Left;
60
61 return minNode.Value;
62 }
63 }
64
65 /// <summary>
66 /// 获取树中节点的最大值
67 /// </summary>
68 public T MaxValue
69 {
70 get
71 {
72 if (IsEmpty)
73 return default (T);
74
75 BinaryTreeNode<T> maxNode = Root;
76 while (maxNode.Right != null )
77 maxNode = maxNode.Right;
78
79 return maxNode.Value;
80 }
81 }
82
83 #endregion
84
85 #region IEnumerable<T> Members
86
87 /// <summary>
88 /// Returns an enumerator that iterates through the collection.
89 /// </summary>
90 /// <returns>
91 /// A <see cref="T:System.Collections.Generic.IEnumerator`1"></see>
92 /// that can be used to iterate through the collection.
93 /// </returns>
94 public IEnumerator<T> GetEnumerator()
95 {
96 foreach (BinaryTreeNode<T> node in Traverse(Root))
97 {
98 yield return node.Value;
99 }
100 }
101
102 #endregion
103
104 #region IEnumerable Members
105
106 /// <summary>
107 /// Returns an enumerator that iterates through a collection.
108 /// </summary>
109 /// <returns>
110 /// An <see cref="T:System.Collections.IEnumerator"/>
111 /// object that can be used to iterate through the collection.
112 /// </returns>
113 IEnumerator IEnumerable.GetEnumerator()
114 {
115 foreach (BinaryTreeNode<T> node in Traverse(Root))
116 {
117 yield return node.Value;
118 }
119 }
120
121 #endregion
122
123 #region ICollection<T> Members
124
125 /// <summary>
126 /// 新增节点
127 /// </summary>
128 /// <param name="item"> The object to add to the
129 /// <see cref="T:System.Collections.Generic.ICollection`1"></see> . </param>
130 /// <exception cref="T:System.NotSupportedException"> The
131 /// <see cref="T:System.Collections.Generic.ICollection`1"></see>
132 /// is read-only. </exception>
133 public void Add(T item)
134 {
135 if (Root == null )
136 {
137 Root = new BinaryTreeNode<T> (item);
138 ++ NumberOfNodes;
139 }
140 else
141 {
142 Insert(item);
143 }
144 }
145
146 /// <summary>
147 /// 清除树
148 /// </summary>
149 public void Clear()
150 {
151 Root = null ;
152 }
153
154 /// <summary>
155 /// 树中是否包含此节点
156 /// </summary>
157 /// <param name="item"> The object to locate in the
158 /// <see cref="T:System.Collections.Generic.ICollection`1"></see> . </param>
159 /// <returns>
160 /// true if item is found in the
161 /// <see cref="T:System.Collections.Generic.ICollection`1"></see> ; otherwise, false.
162 /// </returns>
163 public bool Contains(T item)
164 {
165 if (IsEmpty)
166 return false ;
167
168 BinaryTreeNode<T> currentNode = Root;
169 while (currentNode != null )
170 {
171 int comparedValue = currentNode.Value.CompareTo(item);
172 if (comparedValue == 0 )
173 return true ;
174 else if (comparedValue < 0 )
175 currentNode = currentNode.Left;
176 else
177 currentNode = currentNode.Right;
178 }
179
180 return false ;
181 }
182
183 /// <summary>
184 /// 将树中节点拷贝至目标数组
185 /// </summary>
186 /// <param name="array"> The array. </param>
187 /// <param name="arrayIndex"> Index of the array. </param>
188 public void CopyTo(T[] array, int arrayIndex)
189 {
190 T[] tempArray = new T[NumberOfNodes];
191 int counter = 0 ;
192 foreach (T value in this )
193 {
194 tempArray[counter] = value;
195 ++ counter;
196 }
197 Array.Copy(tempArray, 0 , array, arrayIndex, Count);
198 }
199
200 /// <summary>
201 /// 树中节点的数量
202 /// </summary>
203 public int Count
204 {
205 get { return NumberOfNodes; }
206 }
207
208 /// <summary>
209 /// 树是否为只读
210 /// </summary>
211 public bool IsReadOnly
212 {
213 get { return false ; }
214 }
215
216 /// <summary>
217 /// 移除节点
218 /// </summary>
219 /// <param name="item"> 节点值 </param>
220 /// <returns> 是否移除成功 </returns>
221 public bool Remove(T item)
222 {
223 BinaryTreeNode<T> node = Find(item);
224 if (node == null )
225 return false ;
226
227 List<T> values = new List<T> ();
228 foreach (BinaryTreeNode<T> l in Traverse(node.Left))
229 {
230 values.Add(l.Value);
231 }
232 foreach (BinaryTreeNode<T> r in Traverse(node.Right))
233 {
234 values.Add(r.Value);
235 }
236
237 if (node.Parent.Left == node)
238 {
239 node.Parent.Left = null ;
240 }
241 else
242 {
243 node.Parent.Right = null ;
244 }
245
246 node.Parent = null ;
247
248 foreach (T v in values)
249 {
250 this .Add(v);
251 }
252
253 return true ;
254 }
255
256 #endregion
257
258 #region Private Functions
259
260 /// <summary>
261 /// 查找指定值的节点
262 /// </summary>
263 /// <param name="value"> 指定值 </param>
264 /// <returns>
265 /// 指定值的节点
266 /// </returns>
267 protected BinaryTreeNode<T> Find(T value)
268 {
269 foreach (BinaryTreeNode<T> node in Traverse(Root))
270 if (node.Value.Equals(value))
271 return node;
272 return null ;
273 }
274
275 /// <summary>
276 /// 遍历树
277 /// </summary>
278 /// <param name="node"> 遍历搜索的起始节点 </param>
279 /// <returns>
280 /// The individual items from the tree
281 /// </returns>
282 [SuppressMessage( " Microsoft.Design " , " CA1006:DoNotNestGenericTypesInMemberSignatures " )]
283 protected IEnumerable<BinaryTreeNode<T>> Traverse(BinaryTreeNode<T> node)
284 {
285 // 遍历左子树
286 if (node.Left != null )
287 {
288 foreach (BinaryTreeNode<T> left in Traverse(node.Left))
289 yield return left;
290 }
291
292 // 中序遍历二叉树, 顺序是 左子树，根，右子树
293 yield return node;
294
295 // 遍历右子树
296 if (node.Right != null )
297 {
298 foreach (BinaryTreeNode<T> right in Traverse(node.Right))
299 yield return right;
300 }
301 }
302
303 /// <summary>
304 /// 插入节点
305 /// </summary>
306 /// <param name="value"> 插入的节点值 </param>
307 protected void Insert(T value)
308 {
309 // 从根节点开始比较
310 BinaryTreeNode<T> currentNode = Root;
311
312 while ( true )
313 {
314 if (currentNode == null )
315 throw new InvalidProgramException( " The current tree node cannot be null. " );
316
317 // 比较当前节点与新节点的值
318 int comparedValue = currentNode.Value.CompareTo(value);
319 if (comparedValue < 0 )
320 {
321 // 当前节点值小于新节点值
322 if (currentNode.Left == null )
323 {
324 currentNode.Left = new BinaryTreeNode<T> (value, currentNode);
325 ++ NumberOfNodes;
326 return ;
327 }
328 else
329 {
330 currentNode = currentNode.Left;
331 }
332 }
333 else if (comparedValue > 0 )
334 {
335 // 当前节点值大于新节点值
336 if (currentNode.Right == null )
337 {
338 currentNode.Right = new BinaryTreeNode<T> (value, currentNode);
339 ++ NumberOfNodes;
340 return ;
341 }
342 else
343 {
344 currentNode = currentNode.Right;
345 }
346 }
347 else
348 {
349 // 当前节点值等于新节点值
350 currentNode = currentNode.Right;
351 }
352 }
353 }
354
355 #endregion
356 }
使用举例
1 class Program
2 {
3 static void Main( string [] args)
4 {
5 Console.ForegroundColor = ConsoleColor.Green;
6
7 BinaryTree< string > tree = new BinaryTree< string > ();
8 tree.Add( " Dennis " );
9 tree.Add( " Gao " );
10 tree.Add( " Is " );
11 tree.Add( " A " );
12 tree.Add( " C# " );
13 tree.Add( " Programmer " );
14
15 Console.WriteLine( " Root Node Is : " + tree.Root.ToString());
16 Console.WriteLine();
17
18 foreach ( var node in tree)
19 {
20 Console.WriteLine(node);
21 }
22
23 Console.ReadKey();
24 }
25 }
中序遍历二叉树
C#生成MongoDB中的ObjectId
ObjectId介绍
在MongoDB中，文档（document）在集合（collection）中的存储需要一个唯一的_id字段作为主键。这个_id默认使用ObjectId来定义，因为ObjectId定义的足够短小，并尽最大可能的保持唯一性，同时能被快速的生成。
ObjectId 是一个 12 Bytes 的 BSON 类型，其包含：
4 Bytes 自纪元时间开始的秒数 3 Bytes 机器描述符 2 Bytes 进程ID 3 Bytes 随机数从定义可以看出，在同一秒内，在不同的机器上相同进程ID条件下，非常有可能生成相同的ObjectId。
同时可以根据定义判断出，在给定条件下，ObjectId本身即可描述生成的时间顺序
ObjectId的存储使用Byte数组，而其展现需将Byte数组转换成字符串进行显示，所以通常我们看到的ObjectId都类似于：
ObjectId("507f191e810c19729de860ea")
C#定义ObjectId类
View Code
1 public class ObjectId 2 { 3 private string _string; 4 5 public ObjectId() 6 { 7 } 8 9 public ObjectId( string value) 10 : this (DecodeHex(value)) 11 { 12 } 13 14 internal ObjectId( byte [] value) 15 { 16 Value = value; 17 } 18 19 public static ObjectId Empty 20 { 21 get { return new ObjectId( " 000000000000000000000000 " ); } 22 } 23 24 public byte [] Value { get ; private set ; } 25 26 public static ObjectId NewObjectId() 27 { 28 return new ObjectId { Value = ObjectIdGenerator.Generate() }; 29 } 30 31 public static bool TryParse( string value, out ObjectId objectId) 32 { 33 objectId = Empty; 34 if (value == null || value.Length != 24 ) 35 { 36 return false ; 37 } 38 39 try 40 { 41 objectId = new ObjectId(value); 42 return true ; 43 } 44 catch (FormatException) 45 { 46 return false ; 47 } 48 } 49 50 protected static byte [] DecodeHex( string value) 51 { 52 if ( string .IsNullOrEmpty(value)) 53 throw new ArgumentNullException( " value " ); 54 55 var chars = value.ToCharArray(); 56 var numberChars = chars.Length; 57 var bytes = new byte [numberChars / 2 ]; 58 59 for ( var i = 0 ; i < numberChars; i += 2 ) 60 { 61 bytes[i / 2 ] = Convert.ToByte( new string (chars, i, 2 ), 16 ); 62 } 63 64 return bytes; 65 } 66 67 public override int GetHashCode() 68 { 69 return Value != null ? ToString().GetHashCode() : 0 ; 70 } 71 72 public override string ToString() 73 { 74 if (_string == null && Value != null ) 75 { 76 _string = BitConverter.ToString(Value) 77 .Replace( " - " , string .Empty) 78 .ToLowerInvariant(); 79 } 80 81 return _string; 82 } 83 84 public override bool Equals( object obj) 85 { 86 var other = obj as ObjectId; 87 return Equals(other); 88 } 89 90 public bool Equals(ObjectId other) 91 { 92 return other != null && ToString() == other.ToString(); 93 } 94 95 public static implicit operator string (ObjectId objectId) 96 { 97 return objectId == null ? null : objectId.ToString(); 98 } 99 100 public static implicit operator ObjectId( string value) 101 { 102 return new ObjectId(value); 103 } 104 105 public static bool operator == (ObjectId left, ObjectId right) 106 { 107 if (ReferenceEquals(left, right)) 108 { 109 return true ; 110 } 111 112 if ((( object )left == null ) || (( object )right == null )) 113 { 114 return false ; 115 } 116 117 return left.Equals(right); 118 } 119 120 public static bool operator != (ObjectId left, ObjectId right) 121 { 122 return !(left == right); 123 } 124 }C#实现ObjectId的生成器
View Code
1 internal static class ObjectIdGenerator 2 { 3 private static readonly DateTime Epoch = 4 new DateTime( 1970 , 1 , 1 , 0 , 0 , 0 , DateTimeKind.Utc); 5 private static readonly object _innerLock = new object (); 6 private static int _counter; 7 private static readonly byte [] _machineHash = GenerateHostHash(); 8 private static readonly byte [] _processId = 9 BitConverter.GetBytes(GenerateProcessId()); 10 11 public static byte [] Generate() 12 { 13 var oid = new byte [ 12 ]; 14 var copyidx = 0 ; 15 16 Array.Copy(BitConverter.GetBytes(GenerateTime()), 0 , oid, copyidx, 4 ); 17 copyidx += 4 ; 18 19 Array.Copy(_machineHash, 0 , oid, copyidx, 3 ); 20 copyidx += 3 ; 21 22 Array.Copy(_processId, 0 , oid, copyidx, 2 ); 23 copyidx += 2 ; 24 25 Array.Copy(BitConverter.GetBytes(GenerateCounter()), 0 , oid, copyidx, 3 ); 26 27 return oid; 28 } 29 30 private static int GenerateTime() 31 { 32 var now = DateTime.UtcNow; 33 var nowtime = new DateTime(Epoch.Year, Epoch.Month, Epoch.Day, 34 now.Hour, now.Minute, now.Second, now.Millisecond); 35 var diff = nowtime - Epoch; 36 return Convert.ToInt32(Math.Floor(diff.TotalMilliseconds)); 37 } 38 39 private static byte [] GenerateHostHash() 40 { 41 using ( var md5 = MD5.Create()) 42 { 43 var host = Dns.GetHostName(); 44 return md5.ComputeHash(Encoding.Default.GetBytes(host)); 45 } 46 } 47 48 private static int GenerateProcessId() 49 { 50 var process = Process.GetCurrentProcess(); 51 return process.Id; 52 } 53 54 private static int GenerateCounter() 55 { 56 lock (_innerLock) 57 { 58 return _counter++ ; 59 } 60 } 61 }使用举例
1 class Program 2 { 3 static void Main( string [] args) 4 { 5 Console.ForegroundColor = ConsoleColor.Red; 6 7 ObjectId emptyOid = ObjectId.Empty; 8 Console.WriteLine(emptyOid); 9 10 Console.WriteLine(); 11 Console.ForegroundColor = ConsoleColor.Green; 12 13 for ( int i = 0 ; i < 10 ; i++ ) 14 { 15 ObjectId oid = ObjectId.NewObjectId(); 16 Console.WriteLine(oid); 17 } 18 19 Console.WriteLine(); 20 Console.ForegroundColor = ConsoleColor.Blue; 21 22 ObjectId existingOid; 23 ObjectId.TryParse( " 507f191e810c19729de860ea " , out existingOid); 24 Console.WriteLine(existingOid); 25 26 Console.ReadKey(); 27 } 28 }
标签: C# , MongoDB
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://haodehen.cn/did46006