二叉排序樹（二叉搜索樹）

動態查找表的一種理想數據結構。

二叉排序樹的定義是：二叉排序樹T是一棵樹,它或者是空，或者具備一下三條性質：

（1）、如果T的根節點的左子樹非空，其左子樹所有結點的值均小於T的根節點的值

（2）、如果T的根節點的右子樹非空，其右子樹所有結點的值均大於T的根節點的值
（3）、T的根結點的左右子樹均為二叉排序樹

下面是代碼：

文件"tree.h"

1. #include<iostream>
2. #include<stack>
3. #include<queue>
4. using namespace std;
6. #define MAX_NODE_NUM 20 //樹結點最大值
7. class Bin_Sort_Tree;
8. //樹結點
9. class BSTnode
10. {
11. int tag;//後序遍歷作為訪問標志
12. int data;
13. BSTnode *lchild;
14. BSTnode *rchild;
15. friend class Bin_Sort_Tree;
16. };
18. //二叉排序樹
19. class Bin_Sort_Tree
20. {
21. public:
22. int Get_data(BSTnode *p)
23. {
24. return p->data;
25. }
27. bool Search_BST(BSTnode *T,int a,BSTnode *&f,BSTnode *&p)
28. {
29. /*-----------------------------
30. /在樹中查找值為a的結點，查找到
31. /了，用p保存該結點地址，f指向
32. /p的雙親結點
33. /-----------------------------*/
34. p=T;
35. while(p)
36. {
37. if(p->data==a)
38. return true;
39. else if(p->data>a)
40. {
41. f=p;
42. p=p->lchild;
43. }
44. else
45. {
46. f=p;
47. p=p->rchild;
48. }
49. }
50. return false;
51. }
53. //將值為a的結點插入樹中，若值已存在，就不插入
54. void Insert_BST_1(BSTnode *&T,int a)
55. {
56. BSTnode *f=NULL;
57. BSTnode *p=NULL;
58. if(Search_BST(T,a,f,p))
59. return; //樹中已有值相同結點，不插入
60. else
61. {
62. BSTnode *s=new BSTnode;
63. s->data=a;
64. s->lchild=s->rchild=NULL;
65. if(s->data>f->data)
66. f->rchild=s;
67. else
68. f->lchild=s;
69. }
70. }
72. void Insert_BST_2(BSTnode *&T,int a) //插入算法遞歸實現
73. {
74. if(!T)
75. {
76. cout<<"樹為空"<<endl;
77. return;
78. }
79. if(T->data>a)
80. {
81. if(!T->lchild)
82. {
83. T->lchild=new BSTnode;
84. T->lchild->data=a;
85. T->lchild->lchild=NULL;
86. T->lchild->rchild=NULL;
87. return;
88. }
89. else
90. Insert_BST_2(T->lchild,a);
91. }
92. if(T->data<a)
93. {
94. if(!T->rchild)
95. {
96. T->rchild=new BSTnode;
97. T->rchild->data=a;
98. T->rchild->lchild=NULL;
99. T->rchild->rchild=NULL;
100. return;
101. }
102. else
103. Insert_BST_2(T->rchild,a);
104. }
106. }
108. void Create_BSTree(BSTnode *&T) //建樹
109. {
110. cout<<"輸入二叉排序樹的元素,輸入-1代表結束輸入：";
111. int num[MAX_NODE_NUM];
112. int a,i=0;
113. while(cin>>a && a!=-1)
114. {
115. num[i]=a;
116. i++;
117. }
119. if(num[0]==-1)
120. {
121. cout<<"排序樹為空"<<endl;
122. return;
123. }
125. int k=i;
126. T=new BSTnode;
127. T->data=num[0];
128. T->lchild=T->rchild=NULL;
129. for(i=1;i<k;i++)
130. Insert_BST_1(T,num[i]);
131. cout<<"____建樹完成____"<<endl;
132. }
134. void Delete_BST(BSTnode *&T,int a)//刪除結點值為a的結點
135. {
136. /*---------------------------------------------------------
137. / 從樹中刪除一個節點後，要保證刪後的樹還是一棵二叉排序樹，
138. / 刪除前，首先是在樹中查找是否有這個結點，用p指向該結點，
139. / 用f指向p的雙親結點，這個結點在樹中的位置有下面四種情況:
140. /
141. / 1:如果p指向的結點是葉子結點，那麼直接將f指針的左子樹或者
142. / 右子樹置空，然後刪除p結點即可。
143. /
144. / 2:如果p指向的結點是只有左子樹或右子樹，那麼只需要讓p結點
145. / 原來在f中的位置(左子樹或右子樹)用p的子樹代替即可。
146. /
147. / 3:如果p所指向的結點是根節點，那麼直接將根節點置空
148. /
149. / 4:如果p所指向的結點左右子樹都非空，為了刪除p後原序列的順
150. / 序不變，就需要在原序列中先找出p的直接前驅(或者直接後繼)
151. / 結點用那個結點的值來代替p結點的值，然後再刪掉那個直接前
152. / 驅(或者直接後繼)結點。
153. / 在中序遍歷序列中找結點的直接前驅的方法是順著結點的左孩子
154. / 的右鏈域開始，一直到結點右孩子為空為止。
155. /---------------------------------------------------------*/
157. BSTnode *f=NULL;
158. BSTnode *p=NULL;
159. BSTnode *q=NULL;
160. BSTnode *s=NULL;
161. if(Search_BST(T,a,f,p))
162. {
163. if(p->lchild && p->rchild)
164. {
165. q=p;
166. s=p->lchild;
167. while(s->rchild)
168. {
169. q=s;
170. s=s->rchild;
171. }
172. p->data=s->data;
173. //s指向要刪除結點的直接前驅，且s是一定沒有右子樹的
174. if(q!=p)
175. q->rchild=s->lchild;
176. else
177. q->lchild=s->lchild;//這種情況是,q的左子樹的右子樹為空時
178. delete s;
179. cout<<"結點刪除成功"<<endl;
180. return ;
181. }
182. else
183. {
184. if(!p->lchild) //左子樹為空
185. {
186. q=p;
187. p=p->rchild;
188. }
189. else //右子樹為空
190. {
191. q=p;
192. p=p->lchild;
193. }
194. //下面將p所指向的子樹連接到f所指(被刪結點的雙親)的結點上
195. if(!T) //被刪的結點為根節點
196. T=p;
197. else if(q==f->lchild)
198. f->lchild=p;
199. else
200. f->rchild=p;
201. delete q;
202. cout<<"結點刪除成功"<<endl;
203. return;
204. }
205. }
206. else
207. {
208. cout<<"要刪除的結點不存在"<<endl;
209. return ;
210. }
211. }
213. //下面是二叉樹的四種遍歷方式，都是非遞歸方式實現
215. void PreOrder_Traverse(BSTnode *T) //前序遍歷
216. {
217. stack<BSTnode *> s;
218. BSTnode *p;
219. p=T;
220. while(p || !s.empty())
221. {
222. if(p)
223. {
224. cout<<p->data<<" ";
225. s.push(p);
226. p=p->lchild;
227. }
228. else
229. {
230. p=s.top();
231. s.pop();
232. p=p->rchild;
233. }
234. }
235. }
237. void InOrder_Traverse(BSTnode *T) //中序遍歷
238. {
239. stack<BSTnode *> s;
240. BSTnode *p=T;
241. while(p || !s.empty())
242. {
243. if(p)
244. {
245. s.push(p);
246. p=p->lchild;
247. }
248. else
249. {
250. p=s.top();
251. s.pop();
252. cout<<p->data<<" ";
253. p=p->rchild;
254. }
255. }
256. }
258. void PostOrder_Traverse(BSTnode *T) //後序遍歷
259. {
260. stack<BSTnode *> s;
261. BSTnode *p=T;
262. while(p || !s.empty())
263. {
264. if(p)
265. {
266. p->tag=0;
267. s.push(p);
268. p=p->lchild;
269. }
270. else
271. {
272. p=s.top();
273. if(p->tag)
274. {
275. cout<<p->data<<" ";
276. s.pop();
277. p=NULL;
278. }
279. else
280. {
281. p->tag=1;
282. p=p->rchild;
283. }
284. }
285. }
286. }
288. void LevelOrder_Traverse(BSTnode *T) //層次遍歷
289. {
290. queue<BSTnode *> q;
291. BSTnode *p=T;
292. q.push(p);
293. while(!q.empty())
294. {
295. p=q.front();
296. q.pop();
297. cout<<p->data<<" ";
298. if(p->lchild)
299. q.push(p->lchild);
300. if(p->rchild)
301. q.push(p->rchild);
302. }
303. }
304. };