二叉搜索树类的C#实现

实现：

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6. /**
  7.  * 二叉搜索树
  8.  * 一棵二叉搜索树是满足以下条件的二叉树
  9.  * 1.所有左节点的值都小于本节点的值
  10.  * 2.所有节点的值都小于右节点的值
  11.  **/
  12. namespace Algorithm {
  14. 	class BSTreeNode <T> where T:IComparable {
  15. 		public BSTreeNode<T> left { get; set; }
  16. 		public BSTreeNode<T> right { get; set; }
  17. 		public BSTreeNode<T> parent { get; set; }
  18. 		public T key { get; set; }
  20. 		public BSTreeNode(T k) {
  21. 			key = k;
  22. 		}
  23. 	}
  25. 	class BSTree<T> where T : IComparable {
  27. 		public BSTreeNode<T> Root;
  28. 		public int Count = 0;
  30. 		public BSTree(T key) {
  31. 			Root = new BSTreeNode<T>(key);
  32. 			Count++;
  33. 		}
  34. 		public BSTree(T[] keys) {
  35. 			if (keys.Length == 0) {
  36. 				return;
  37. 			}
  38. 			Root = new BSTreeNode<T>(keys[0]);
  39. 			for (int i = 1; i < keys.Length; i++) {
  40. 				Insert(keys[i]);
  41. 			}
  42. 		}
  44. 		/**
  45. 		 * 插入
  46. 		 **/
  47. 		public BSTreeNode<T> Insert(T key) {
  48. 			BSTreeNode<T> node = Root;
  49. 			BSTreeNode<T> newNode = new BSTreeNode<T>(key);
  50. 			BSTreeNode<T> parent = null;
  51. 			while (node != null) {
  52. 				parent = node;
  53. 				if (key.CompareTo(node.key) > 0) {
  54. 					node = node.right;
  55. 				} else {
  56. 					node = node.left;
  57. 				}
  58. 			}
  59. 			newNode.parent = parent;
  60. 			if (parent == null) {
  61. 				return newNode;
  62. 			} else if (key.CompareTo(parent.key) > 0) {
  63. 				parent.right = newNode;
  64. 			} else {
  65. 				parent.left = newNode;
  66. 			}
  67. 			Count++;
  68. 			return newNode;
  69. 		}
  71. 		/**
  72. 		 * 递归遍历
  73. 		 * */
  74. 		public void Walk(BSTreeNode<T> node, Action<BSTreeNode<T>> func, string type = "mid") {
  75. 			if (node != null) {
  76. 				if (type == "pre") func(node);
  77. 				Walk(node.left, func, type);
  78. 				if (type == "mid") func(node);
  79. 				Walk(node.right, func, type);
  80. 				if (type == "post") func(node);
  81. 			}
  82. 		}
  84. 		/**
  85. 		 * 非递归 中序遍历
  86. 		 * **/
  87. 		public void InOrderTreeWalk(BSTreeNode<T> root, Action<BSTreeNode<T>> func) {
  88. 			if (root == null) {
  89. 				return;
  90. 			}
  91. 			Stack<BSTreeNode<T>> stack = new Stack<BSTreeNode<T>>((int)(2 * Math.Log(Count + 1)));
  92. 			BSTreeNode<T> current = root;
  94. 			while (current != null) {
  95. 				stack.Push(current);
  96. 				current = current.left;
  97. 			}
  98. 			while (stack.Count != 0) {
  99. 				current = stack.Pop();
  100. 				func(current);
  102. 				BSTreeNode<T> node = current.right;
  103. 				while (node != null) {
  104. 					stack.Push(node);
  105. 					node = node.left;
  106. 				}
  107. 			}
  108. 		}
  110. 		/**
  111. 		 * 搜索
  112. 		 * **/
  113. 		public BSTreeNode<T> Search(BSTreeNode<T> node, T key) {
  114. 			while (node != null && key.CompareTo(node.key) != 0) {
  115. 				if (key.CompareTo(node.key) < 0) {
  116. 					node = node.left;
  117. 				} else {
  118. 					node = node.right;
  119. 				}
  120. 			}
  121. 			return node;
  122. 		}
  124. 		/**
  125. 		 * 最小值
  126. 		 * **/
  127. 		public BSTreeNode<T> Min(BSTreeNode<T> node) {
  128. 			while (node != null && node.left != null) {
  129. 				node = node.left;
  130. 			}
  131. 			return node;
  132. 		}
  134. 		/**
  135. 		 * 最大值
  136. 		 * **/
  137. 		public BSTreeNode<T> Max(BSTreeNode<T> node) {
  138. 			while (node != null && node.right != null) {
  139. 				node = node.right;
  140. 			}
  141. 			return node;
  142. 		}
  144. 		/**
  145. 		 * 后继元素
  146. 		 * **/
  147. 		public BSTreeNode<T> Succ(BSTreeNode<T> node) {
  148. 			if (node.right != null) {
  149. 				return Min(node.right);
  150. 			}
  151. 			BSTreeNode<T> parent = node.parent;
  152. 			while (parent != null && node != parent.left) {
  153. 				node = parent;
  154. 				parent = node.parent;
  155. 			}
  156. 			return parent;
  157. 		}
  159. 		/**
  160. 		 * 前驱元素
  161. 		 * **/
  162. 		public BSTreeNode<T> Pred(BSTreeNode<T> node) {
  163. 			if (node.left != null) {
  164. 				return Max(node.left);
  165. 			}
  166. 			BSTreeNode<T> parent = node.parent;
  167. 			while (parent != null && node != parent.right) {
  168. 				node = parent;
  169. 				parent = node.parent;
  170. 			}
  171. 			return parent;
  172. 		}
  174. 		/**
  175. 		 * 删除节点
  176. 		 * */
  177. 		public BSTreeNode<T> Delete(BSTreeNode<T> t ,BSTreeNode<T> x) {
  178. 			if (x == null) return Root;
  180. 			BSTreeNode<T> root = t;
  181. 			BSTreeNode<T> oldX= x;
  182. 			BSTreeNode<T> parent = x.parent;
  184. 			if (x.left == null) {
  185. 				x = x.right;
  186. 			} else if (x.right == null) {
  187. 				x = x.left;
  188. 			} else {
  189. 				BSTreeNode<T> y = Min(x.right);
  190. 				x.key = y.key;
  191. 				if (y.parent != x) {
  192. 					y.parent.left = y.right;
  193. 				} else {
  194. 					x.right = y.right;
  195. 				}
  196. 				return root;
  197. 			}
  199. 			if (x != null) {
  200. 				x.parent = parent;
  201. 			}
  202. 			if (parent == null) {
  203. 				root = x;
  204. 			} else {
  205. 				if (parent.left == oldX) {
  206. 					parent.left = x;
  207. 				} else {
  208. 					parent.right = x;
  209. 				}
  210. 			}
  212. 			return Root;
  213. 		}
  215. 		public List<T> ToList() {
  216. 			List<T> list = new List<T>();
  217. 			Walk(Root, (BSTreeNode<T> node) => {
  218. 				list.Add(node.key);
  219. 			}, "mid");
  220. 			return list;
  221. 		}
  222. 	}
  223. }





【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/xiejunzhao/p/7fead2a30b116abdf516ae053cd93ab6.html