1 using System; 2 3 public class BinarySearchTree 4 { 5 public int value; 6 7 public BinarySearchTree left = null; 8 public BinarySearchTree right = null; 9 public BinarySearchTree parent = null; 10 public BinarySearchTree root = null; 11 12 private bool _isRoot; 13 public bool isRoot 14 { 15 get { return _isRoot; } 16 set 17 { 18 _isRoot = value; 19 root = _isRoot ? this : null; 20 } 21 } 22 23 public BinarySearchTree(int value,BinarySearchTree parent,BinarySearchTree root) 24 { 25 this.value = value; 26 this.parent = parent; 27 this.root = root; 28 } 29 public BinarySearchTree(int value) : this(value, null, null) { } 30 31 /// 32 /// 增 33 /// 34 /// 35 /// 36 public void InsertNode(int value) 37 { 38 if(value <= this.value) 39 { 40 if(left == null) 41 { 42 left = new BinarySearchTree(value,this,root); 43 return; 44 } 45 else if(left != null) 46 { 47 left.InsertNode(value); 48 return; 49 } 50 } 51 else if(value > this.value) 52 { 53 if(right == null) 54 { 55 right = new BinarySearchTree(value,this,root); 56 return; 57 } 58 else if(right != null) 59 { 60 right.InsertNode(value); 61 return; 62 } 63 } 64 } 65 66 /// 67 /// 删 68 /// 69 /// 70 /// 71 public void RemoveNode(int value) 72 { 73 BinarySearchTree beRemove = null; 74 try 75 { 76 beRemove = Find(value); 77 } 78 catch (Exception) 79 { 80 throw new Exception("被删除的数字不存在"); 81 } 82 83 if (beRemove.left == null && beRemove.right == null) 84 { 85 if (beRemove.parent.left == beRemove) 86 { 87 beRemove.parent.left = null; 88 } 89 else if (beRemove.parent.right == beRemove) 90 { 91 beRemove.parent.right = null; 92 } 93 } 94 else if(beRemove.left != null && beRemove.right == null) 95 { 96 if (beRemove.parent.left == beRemove) 97 { 98 beRemove.parent.left = beRemove.left; 99 }100 else if (beRemove.parent.right == beRemove)101 {102 beRemove.parent.right = beRemove.left;103 }104 }105 else if(beRemove.left == null && beRemove.right != null)106 {107 if (beRemove.parent.left == beRemove)108 {109 beRemove.parent.left = beRemove.right;110 }111 else if (beRemove.parent.right == beRemove)112 {113 beRemove.parent.right = beRemove.right;114 }115 }116 else if(beRemove.left != null && beRemove.right != null)117 {118 if (beRemove.parent.left == beRemove)119 {120 beRemove.parent.left = beRemove.right;121 }122 else if (beRemove.parent.right == beRemove)123 {124 beRemove.parent.right = beRemove.right;125 }126 127 beRemove.right.left = beRemove.left;128 }129 }130 131 /// 132 /// 改133 /// 134 /// 135 public void ChangeNoodTo(int newValue)136 {137 RemoveNode(value);138 root.InsertNode(newValue);139 }140 141 /// 142 /// 查143 /// 144 /// 145 /// 146 /// 147 public BinarySearchTree Find(int value)148 {149 if (value < this.value)150 {151 //return left == null ? -1 : left.Find(value);152 if(left == null)153 {154 throw new Exception("被搜索的数字不存在");155 }156 else157 {158 return left.Find(value);159 }160 }161 else if (value > this.value)162 {163 //return right == null ? -1 : right.Find(value);164 if(right == null)165 {166 throw new Exception("被搜索的数字不存在");167 }168 else169 {170 return right.Find(value);171 }172 }173 else if (value == this.value)174 {175 return this;176 }177 178 throw new Exception("被搜索的数字不存在");179 }180 181 /// 182 /// 输出这棵二叉搜索树183 /// 184 public void ShowTree()185 {186 Console.Write("(");187 Console.Write(this.value);188 if(left == null)189 {190 Console.Write("()");191 }192 else193 {194 left.ShowTree();195 }196 197 if(right == null)198 {199 Console.Write("()");200 }201 else202 {203 right.ShowTree();204 }205 206 Console.Write(")");207 }208 209 /// 210 /// 复写 ToString() 方法211 /// 212 /// 213 public override string ToString()214 {215 return value.ToString();216 }217 } 1 class Program 2 { 3 4 private static int[] value = new int[] { 50, 60, 70, 23, 51, 159, 25 }; 5 6 static void Main(string[] args) 7 { 8 BinarySearchTree rootNood = new BinarySearchTree(value[0]); 9 rootNood.isRoot = true;10 11 Console.WriteLine(rootNood.root == null);12 13 for (int i = 1; i < value.Length; i++)14 {15 rootNood.InsertNode(value[i]);16 }17 18 rootNood.ShowTree();19 Console.WriteLine();20 21 rootNood.Find(23).ChangeNoodTo(24);22 rootNood.ShowTree();23 24 25 Console.ReadKey();26 }27 }