二叉树
本篇纯属娱乐，源于整理代码，发现还曾实现过遍历二叉树。
虽然.NET/C#中的各种集合类已经实现了最优的排序设计，但了解基本的算法实现有助于软件开发中的各种权衡和选择。
比如，如果你实现过B+树排序和查找，并将树节点序列化至二进制文件块，则你应该已经了解了各种数据库索引的基本设计。
什么是二叉树？
http://en.wikipedia.org/wiki/Binary_tree
二叉树节点类定义
View Code1 /// <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 Code1 /// <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 Code1 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 Code1 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 }
