二叉查找树

  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         /// <summary>
 32         /// 增
 33         /// </summary>
 34         /// <param name="value"></param>
 35         /// <returns></returns>
 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         /// <summary>
 67         /// 删
 68         /// </summary>
 69         /// <param name="value"></param>
 70         /// <exception cref="Exception"/>
 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         /// <summary>
132         /// 改
133         /// </summary>
134         /// <param name="newValue"></param>
135         public void ChangeNoodTo(int newValue)
136         {
137             RemoveNode(value);
138             root.InsertNode(newValue);
139         }
140 
141         /// <summary>
142         /// 查
143         /// </summary>
144         /// <param name="value"></param>
145         /// <returns></returns>
146         /// <exception cref="Exception"/>
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                 else
157                 {
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                 else
169                 {
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         /// <summary>
182         /// 输出这棵二叉搜索树
183         /// </summary>
184         public void ShowTree()
185         {
186             Console.Write("(");
187             Console.Write(this.value);
188             if(left == null)
189             {
190                 Console.Write("()");
191             }
192             else
193             {
194                 left.ShowTree();
195             }
196 
197             if(right == null)
198             {
199                 Console.Write("()");
200             }
201             else
202             {
203                 right.ShowTree();
204             }
205 
206             Console.Write(")");
207         }
208 
209         /// <summary>
210         /// 复写 ToString() 方法
211         /// </summary>
212         /// <returns></returns>
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     }