C# 二叉排序树

二叉排序树，又称为二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树：

• 若它的左子树不为空。则左子树上所有的结点的值均小于跟的结点值
• 若它的右子树部位空，则右子树的所有结点值均大于它的根结点的值
• 它的左右子树也分别是二叉排序树

1，排序方便
2，查找方便
3，便于插入和删除

C#链式存储二叉排序树，实现简单的排序，以及查找，，具体代码如下：

namespace _2_1_3二叉排序树
{ /// <summary> /// 结点类 /// </summary> class BSNode { //结点 public BSNode LeftChild { get; set; } public BSNode RightChild { get; set; } public BSNode Parent { get; set; } public int Data { get; set; } // 构造方法 public BSNode(){} public BSNode(int item) { this.Data = item; } }
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
 

using System;

namespace _2_1_3二叉排序树
{ /// <summary> /// 二叉排序树 /// </summary> class BSTree { BSNode root = null; /// <summary> /// 添加数据 /// </summary> public void Add(int item) { //创建新结点 BSNode newNode = new BSNode(item); if (root == null) //若为空，则创建为根结点 { root = newNode; } else { BSNode temp = root; while (true) { if (item >= temp.Data)  //放在temp结点的右边 { if (temp.RightChild == null) { temp.RightChild = newNode; newNode.Parent = temp; break; } else { temp = temp.RightChild; } } else //放在temp结点的左边 { if (temp.LeftChild == null) { temp.LeftChild = newNode; newNode.Parent = temp; break; } else { temp = temp.LeftChild; } } } } } /// <summary> /// 中序遍历二叉树 /// </summary> public void MiddleBianli() { MiddleBianli(root); } //递归方式中序遍历树 private void MiddleBianli(BSNode node) { if (node == null) return; MiddleBianli(node.LeftChild); Console.Write(node.Data + " "); MiddleBianli(node.RightChild); } /// <summary> ///查找方法-1 /// </summary> public bool Find1(int item) { return Find(item, root); } private bool Find(int item, BSNode node) { if (node == null) { return false; } if (node.Data == item) { return true; } else { //利用二叉排序树的便利 if (item > node.Data) { return Find(item, node.RightChild); } else { return Find(item, node.LeftChild); } } } /// <summary> /// 查找方法-2 /// </summary> /// <param name="item"></param> /// <returns></returns> public bool Find2(int item) { BSNode temp = root; while (true) { if (temp == null) return false; if (temp.Data == item) return true; if (item > temp.Data) { temp = temp.RightChild; } else { temp = temp.LeftChild; } } } public bool Delete(int item) { BSNode temp = root; while (true) { if (temp == null) return false; if (temp.Data == item) { Delete(temp); return true; } if (item > temp.Data) { temp = temp.RightChild; } else { temp = temp.LeftChild; } } } public void Delete(BSNode node) { //叶子结点，即无子树情况 if (node.LeftChild == null && node.RightChild == null) { if (node.Parent == null) { root = null; } else if (node.Parent.LeftChild == node) { node.Parent.LeftChild = null; } else if (node.Parent.RightChild == node) { node.Parent.RightChild = null; } return; } //只有右子树的情况 if (node.LeftChild == null && node.RightChild != null) { node.Data = node.RightChild.Data; node.RightChild = null; return; } //只有左子树的情况 if (node.LeftChild != null && node.RightChild == null) { node.Data = node.LeftChild.Data; node.LeftChild = null; return; } //删除的结点有左，右子树 BSNode temp = node.RightChild; while (true) { if (temp.LeftChild != null) { temp = temp.LeftChild; } else { break; } } node.Data = temp.Data; Delete(temp); } }
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
  
104
  
105
  
106
  
107
  
108
  
109
  
110
  
111
  
112
  
113
  
114
  
115
  
116
  
117
  
118
  
119
  
120
  
121
  
122
  
123
  
124
  
125
  
126
  
127
  
128
  
129
  
130
  
131
  
132
  
133
  
134
  
135
  
136
  
137
  
138
  
139
  
140
  
141
  
142
  
143
  
144
  
145
  
146
  
147
  
148
  
149
  
150
  
151
  
152
  
153
  
154
  
155
  
156
  
157
  
158
  
159
  
160
  
161
  
162
  
163
  
164
  
165
  
166
  
167
  
168
  
169
  
170
  
171
  
172
  
173
  
174
  
175
  
176
  
177
  
178
  
179
  
180
  
181
  
182
  
183
  
184
  
185
  
186
  
187
  
188
  
189
  
190
  
191
  
192
  
193
  
194
  
195
  
196
  
197
  
198
  
199
  
200
  
201
  
202
 

using System;

namespace _2_1_3二叉排序树
{ /// <summary> /// 测试类 /// </summary> class Program { static void Main(string[] args) { BSTree tree = new BSTree(); int[] data = {62,58,28,47,73,99,35,51,93,37 }; foreach (int item in data) { tree.Add(item); } Console.Write("中序遍历的结果："); tree.MiddleBianli(); Console.WriteLine(); Console.WriteLine("Find-1方法查找62是否存在：" + tree.Find1(62)); Console.WriteLine("Find-2方法查找62是否存在：" + tree.Find2(62)); Console.WriteLine("Find-1方法查找63是否存在：" + tree.Find1(63)); Console.WriteLine("Find-2方法查找63是否存在：" + tree.Find2(63)); Console.WriteLine("删除根结点后的结果："); tree.Delete(62); tree.MiddleBianli(); Console.ReadKey(); } }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
 

文章来源: czhenya.blog.csdn.net，作者：陈言必行，版权归原作者所有，如需转载，请联系作者。

原文链接：czhenya.blog.csdn.net/article/details/78887679