二叉搜索树类的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 {
  13. class BSTreeNode <T> where T:IComparable {
  14. public BSTreeNode<T> left { get; set; }
  15. public BSTreeNode<T> right { get; set; }
  16. public BSTreeNode<T> parent { get; set; }
  17. public T key { get; set; }
  18. public BSTreeNode(T k) {
  19. key = k;
  20. }
  21. }
  22. class BSTree<T> where T : IComparable {
  23. public BSTreeNode<T> Root;
  24. public BSTree(T key) {
  25. Root = new BSTreeNode<T>(key);
  26. }
  27. public BSTree(T[] keys) {
  28. if (keys.Length == 0) {
  29. return;
  30. }
  31. Root = new BSTreeNode<T>(keys[0]);
  32. for (int i = 1; i < keys.Length; i++) {
  33. Insert(keys[i]);
  34. }
  35. }
  36. /**
  37. * 插入
  38. **/
  39. public BSTreeNode<T> Insert(T key) {
  40. BSTreeNode<T> node = Root;
  41. BSTreeNode<T> newNode = new BSTreeNode<T>(key);
  42. BSTreeNode<T> parent = null;
  43. while (node != null) {
  44. parent = node;
  45. if (key.CompareTo(node.key) > 0) {
  46. node = node.right;
  47. } else {
  48. node = node.left;
  49. }
  50. }
  51. newNode.parent = parent;
  52. if (parent == null) {
  53. return newNode;
  54. } else if (key.CompareTo(parent.key) > 0) {
  55. parent.right = newNode;
  56. } else {
  57. parent.left = newNode;
  58. }
  59. return newNode;
  60. }
  61. /**
  62. * 遍历
  63. * */
  64. public void Walk(BSTreeNode<T> node, Action<T> func, string type = "mid") {
  65. if (node != null) {
  66. if (type == "pre") func(node.key);
  67. Walk(node.left, func, type);
  68. if (type == "mid") func(node.key);
  69. Walk(node.right, func, type);
  70. if (type == "post") func(node.key);
  71. }
  72. }
  73. /**
  74. * 搜索
  75. * **/
  76. public BSTreeNode<T> Search(BSTreeNode<T> node, T key) {
  77. while (node != null && key.CompareTo(node.key) != 0) {
  78. if (key.CompareTo(node.key) < 0) {
  79. node = node.left;
  80. } else {
  81. node = node.right;
  82. }
  83. }
  84. return node;
  85. }
  86. /**
  87. * 最小值
  88. * **/
  89. public BSTreeNode<T> Min(BSTreeNode<T> node) {
  90. while (node != null && node.left != null) {
  91. node = node.left;
  92. }
  93. return node;
  94. }
  95. /**
  96. * 最大值
  97. * **/
  98. public BSTreeNode<T> Max(BSTreeNode<T> node) {
  99. while (node != null && node.right != null) {
  100. node = node.right;
  101. }
  102. return node;
  103. }
  104. /**
  105. * 后继元素
  106. * **/
  107. public BSTreeNode<T> Succ(BSTreeNode<T> node) {
  108. if (node.right != null) {
  109. return Min(node.right);
  110. }
  111. BSTreeNode<T> parent = node.parent;
  112. while (parent != null && node != parent.left) {
  113. node = parent;
  114. parent = node.parent;
  115. }
  116. return parent;
  117. }
  118. /**
  119. * 前驱元素
  120. * **/
  121. public BSTreeNode<T> Pred(BSTreeNode<T> node) {
  122. if (node.left != null) {
  123. return Max(node.left);
  124. }
  125. BSTreeNode<T> parent = node.parent;
  126. while (parent != null && node != parent.right) {
  127. node = parent;
  128. parent = node.parent;
  129. }
  130. return parent;
  131. }
  132. /**
  133. * 删除节点
  134. * */
  135. public BSTreeNode<T> Delete(BSTreeNode<T> t ,BSTreeNode<T> x) {
  136. if (x == null) return Root;
  137. BSTreeNode<T> root = t;
  138. BSTreeNode<T> oldX= x;
  139. BSTreeNode<T> parent = x.parent;
  140. if (x.left == null) {
  141. x = x.right;
  142. } else if (x.right == null) {
  143. x = x.left;
  144. } else {
  145. BSTreeNode<T> y = Min(x.right);
  146. x.key = y.key;
  147. if (y.parent != x) {
  148. y.parent.left = y.right;
  149. } else {
  150. x.right = y.right;
  151. }
  152. return root;
  153. }
  154. if (x != null) {
  155. x.parent = parent;
  156. }
  157. if (parent == null) {
  158. root = x;
  159. } else {
  160. if (parent.left == oldX) {
  161. parent.left = x;
  162. } else {
  163. parent.right = x;
  164. }
  165. }
  166. return Root;
  167. }
  168. }
  169. }

测试:
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6. namespace Algorithm {
  7. class Program {
  8. static void Main(string[] args) {
  9. int[] arr = { 4, 3, 8, 1, 7, 16, 2, 10, 9, 14 };
  10. BSTree tree = new BSTree(arr);
  11. tree.Insert(20);
  12. Console.WriteLine("Walk");
  13. tree.Walk(tree.Root, (int key) => {
  14. Console.WriteLine(key);
  15. });
  16. Console.WriteLine("Search");
  17. BSTreeNode node = tree.Search(tree.Root, 16);
  18. Console.WriteLine(node.key);
  19. Console.WriteLine(node.parent.key);
  20. Console.WriteLine("Min");
  21. Console.WriteLine(tree.Min(tree.Root).key);
  22. Console.WriteLine("Max");
  23. Console.WriteLine(tree.Max(tree.Root).key);
  24. Console.WriteLine("Pred");
  25. BSTreeNode preNode = tree.Pred(node);
  26. if(preNode!=null) Console.WriteLine(preNode.key);
  27. Console.WriteLine("Succ");
  28. BSTreeNode succNode = tree.Succ(node);
  29. if(succNode != null) Console.WriteLine(succNode.key);
  30. Console.WriteLine("Delete");
  31. tree.Delete(tree.Root, preNode);
  32. Console.WriteLine("Walk");
  33. tree.Walk(tree.Root, (int key) => {
  34. Console.WriteLine(key);
  35. });
  36. }
  37. }
  38. }

null

相关内容推荐