实现了如下基本功能:
1。添加节点
2。删除节点
3。查找最小值
4。查找最大值
5。中序遍历
1using System;2using System.Collections.Generic;
3using System.Text;
4
5namespace BinarySearchTree
6{
7 class Program
8 {
9 static void Main(string[] args)
10 {
11 BinarySearchTree bTree = new BinarySearchTree();
12 bTree.Insert(5);
13 bTree.Insert(8);
14 bTree.Insert(39);
15 bTree.Insert(23);
16 bTree.Insert(12);
17
18 bTree.InOrder();
19 bTree.Delete(8);
20 bTree.InOrder();
21 // Console.WriteLine(bTree.GetSuccessor(8));
22 //Console.WriteLine(bTree.FindMax());
23 //Console.WriteLine(bTree.FindMin());
24 //Console.WriteLine(bTree.Delete(99));
25 }
26 }
27
28 public class Node
29 {
30 int date;
31 //节点数据
32 public int Date
33 {
34 get { return date; }
35 set { date = value; }
36 }
37 Node left;
38//左子树
39 public Node Left
40 {
41 get { return left; }
42 set { left = value; }
43 }
44 Node right;
45//右子树
46 public Node Right
47 {
48 get { return right; }
49 set { right = value; }
50 }
51
52 public Node()
53 {
54 }
55 public Node(int date)
56 {
57 this.date = date;
58 }
59 }
60
61 public class BinarySearchTree//排序二叉树
62 {
63 Node root;
64 public BinarySearchTree()
65 {
66 root = null;
67 }
68
69//插入数据
70 public void Insert(int i)
71 {
72 Node newNode = new Node(i);
73 if (root == null)
74 {
75 root = newNode;
76 return;
77 }
78 Node current = root;
79 Node parent;
80 while (true)
81 {
82 parent = current;
83 if (i < current.Date)
84 {
85 current = current.Left;
86 if (current == null)
87 {
88 parent.Left = newNode;
89 break;
90 }
91 }
92 else
93 {
94 current = current.Right;
95 if (current == null)
96 {
97 parent.Right = newNode;
98 break;
99 }
100 }
101 }
102 }
103
104 public void InOrder()//中序遍历
105 {
106 InOrder(root);
107 }
108 private void InOrder(Node root)
109 {
110 if(root!=null)
111 {
112 InOrder(root.Left);
113 Console.WriteLine(root.Date);
114 InOrder(root.Right);
115 }
116 }
117
118 public int FindMax()//查找最大值
119 {
120 Node current = root;
121 while (current.Right!= null)
122 {
123 current = current.Right;
124 }
125 return current.Date;
126 }
127
128 public int FindMin()//查找最小值
129 {
130 Node current = root;
131 while (current.Left != null)
132 {
133 current = current.Left;
134 }
135 return current.Date;
136 }
137
138
139 public Node GetSuccessor(Node delNode)//获得当前节点的下一个节点(中序位置)
140 {
141 Node parent = delNode;
142 Node current = delNode.Right;
143 while (current.Left != null)
144 {
145 parent = current;
146 current = current.Left;
147 }//找到要删除节点右子树的最小节点
148 if (current != delNode.Right)
149 {
150 parent.Left = current.Right;
151 current.Right = delNode.Right;
152 }//将最小节点从原位置移出,并将拟删除节点的右子树挂到其右子树上
153 return current;
154
155 }
156
157 public bool Delete(int key)
158 {
159 Node current = root;
160 Node parent = root;
161 bool isLeft = false;
162 //找到要删除的节点
163 while (current.Date != key)
164 {
165 parent = current;
166 if (current.Date > key)
167 {
168 current = current.Left;
169 isLeft = true;
170 }
171 else
172 {
173 current = current.Right;
174 isLeft = false;
175 }
176 if (current == null)
177 return false;
178 }
179 //如果要删除的是叶子节点
180 if (current.Left == null && current.Right == null)
181 {
182 if (current == root)
183 {
184 root = null;
185 }
186 else if (isLeft)
187 {
188 parent.Left = null;
189 }
190 else
191 {
192 parent.Right = null;
193 }
194 }
195 //如果要删除的节点只有右子树
196 else if (current.Left == null)
197 {
198 if (current == root)
199 {
200 root = current.Right;
201 }
202 else if (isLeft)
203 {
204 parent.Left = current.Right;
205 }
206 else
207 {
208 parent.Right = current.Right;
209 }
210 }
211 //如果拟删除的节点只有左子树
212 else if (current.Right == null)
213 {
214 if (current == root)
215 {
216 root = current.Left;
217 }
218 else if (isLeft)
219 {
220 parent.Left = current.Left;
221 }
222 else
223 {
224 parent.Right = current.Left;
225 }
226 }//如果删除的节点既有左子树,又有右子树
227 else
228 {
229 Node successor = GetSuccessor(current);
230 if (current == root)
231 {
232 root = successor;
233 }
234 else if (isLeft)
235 {
236 parent.Left = successor;
237 }
238 else
239 {
240 parent.Right = successor;
241 }
242
243 successor.Left = current.Left;
244 }
245
246 return true;
247
248 }
249 }
250
251}
252