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

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

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

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

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

下面是代碼：

文件"tree.h"

1. #include<iostream>   
2. #include<stack>   
3. #include<queue>   
4. using namespace std;  
5.   
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. };  
17.   
18. //二叉排序樹   
19. class Bin_Sort_Tree  
20. {  
21. public:   
22.     int Get_data(BSTnode *p)  
23.     {  
24.         return p->data;  
25.     }  
26.   
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.     }  
52.       
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.     }  
71.       
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.         }  
105.   
106.     }  
107.   
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.         }  
118.           
119.         if(num[0]==-1)  
120.         {  
121.             cout<<"排序樹為空"<<endl;  
122.             return;  
123.         }  
124.   
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.     }  
133.   
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.         /---------------------------------------------------------*/  
156.   
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.     }  
212.   
213.     //下面是二叉樹的四種遍歷方式，都是非遞歸方式實現   
214.       
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.     }  
236.   
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.     }  
257.   
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.     }  
287.   
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. };