【C++】C++模板实现的二叉排序（查找）树

0x55AA

二叉排序树定义：
二叉排序树是这样的树，结点左边的值都小于结点的值，结点右边的值都大于结点的值，所以按照二叉树的中序遍历的话，得到的的将是按顺序排列的值。
二叉排序树的主要操作：
1：插入
插入的操作非常简单，从根结点开始，如果插入值大于根节点值，则向右遍历，如果小于根节点值，则想左遍历，知道遇到一个叶子结点为止。按插入值大于叶子则将插入值作为叶子结点的右孩子，否则左孩子。中间过程中如果遇到跟插入值相等的，则插入失败。
2：删除
关于有三种情况需要不同对待。
<1>如果是叶子结点，那么直接删除就行（注意相关的孩子指针要变成NULL）。
<2>如果要删除的结点只有左孩子或者右孩子，这样也好办，我们只需要把相应的孩子赋值          给待删除结点的双亲结点的孩子指针即可，孙子升级当儿子。
<3>如果要删除的结点既有左孩子，又有右孩子，那么情况就稍微有点麻烦，在这里我们可以采取两种策略来实现，第一种是“前驱不动，移动右孩子法”，第二种是“右孩子不动，移动前驱法”。具体如下图所示：

3：遍历
遍历采用递归方法，遍历的实现就很简单了。
4：清除
在清除树的所有结点的时候，采取了递归思想，判断左孩子是否为空，如果不空则清空做孩子；再判断右孩子是否为空，不为空则清空右孩子；只有当结点左右孩子结点都为空的时候，才释放该结点的空间。
5：查找
查找要利用二叉排序树的自身优点来进行，每次根据与结点的比较结果选择再继续跟左孩子比较还是跟右孩子比较。

实现代码：
BSTrees.h

1. //BSTrees.h
   
2. #ifndef DDXX_BSTREES_H
   
3. #define DDXX_BSTREES_H
   
4. #include <iostream>
   
5. using namespace std;
   
6. template<typename Type>
   
7. class BSTrees
   
8. {
   
9. public:
   
10.         BSTrees();
    
11.         ~BSTrees();
    
12. public:
    
13.         struct Node
    
14.         {
    
15.                 Type        e;
    
16.                 Node*        leftChild;
    
17.                 Node*        rightChild;
    
18.                 Node()
    
19.                 {
    
20.                 }
    
21.                 Node(Type _e)
    
22.                 {
    
23.                         e                        = _e;
    
24.                         leftChild        = NULL;
    
25.                         rightChild        = NULL;
    
26.                 }
    
27.         };
    
28. public:
    
29.         bool        insert(Type e);
    
30.         bool        erase1(Type e);
    
31.         bool        erase2(Type e);
    
32.         void        clear();
    
33.         bool        isEmpty();
    
34.         int                getLength();
    
35.         Node*        find(Type e);
    
36.         Node*        getRoot();
    
37.         Node*        getParent(Node* p);
    
38.         void        traverse(Node* ptr);
    
39. private:
    
40.         void        clears(Node* &p);
    
41. private:
    
42.         Node*        m_root;
    
43.         int                m_Length;
    
44. };
    
45. 
    
46. template<typename Type> BSTrees<Type>::BSTrees()
    
47. {
    
48.         m_root = NULL;
    
49.         m_Length = 0;
    
50. }
    
51. 
    
52. template<typename Type> bool BSTrees<Type>::insert(Type e)
    
53. {
    
54.         Node* ptr = new Node(e);
    
55.         if ( ptr == NULL )
    
56.         {
    
57.                 cout<<"Allocate memory for the element failed"<<endl;
    
58.                 return false;
    
59.         }
    
60. 
    
61.         if( m_root == NULL)
    
62.         {
    
63.                 m_root = ptr;
    
64.                 m_Length++;
    
65.                 return true;
    
66.         }
    
67. 
    
68.         Node* p                        = m_root;
    
69.         Node* pParent        = m_root;
    
70.         while( p != NULL)
    
71.         {
    
72.                 if( e == p->e)
    
73.                 {
    
74.                         cout<<"the element is already exist"<<endl;
    
75.                         return false;
    
76.                 }
    
77. 
    
78.                 pParent = p;
    
79.                 if( e > p->e)
    
80.                 {
    
81.                         p = p->rightChild;
    
82.                 }
    
83.                 else
    
84.                 {
    
85.                         p = p->leftChild;
    
86.                 }
    
87.         }
    
88.        
    
89.         if( e < pParent->e )
    
90.         {
    
91.                 pParent->leftChild = ptr;
    
92.         }
    
93.         if( e > pParent->e)
    
94.         {
    
95.                 pParent->rightChild = ptr;
    
96.         }
    
97. 
    
98.         m_Length++;
    
99.         return true;
    
100. }
     
101. 
     
102. template<typename Type> bool BSTrees<Type>::erase1(Type e)
     
103. {
     
104.         Node *p = find(e);
     
105.         if ( p == NULL )
     
106.         {
     
107.                 cout<<"There's no this element to delete"<<endl;
     
108.                 return false;
     
109.         }
     
110. 
     
111.         if ( p->leftChild == NULL)
     
112.         {
     
113.                 Node* pParent = getParent(p);
     
114.                 if( pParent->leftChild == p )
     
115.                         pParent->leftChild = p->rightChild;
     
116.                 else
     
117.                         pParent->rightChild = p->rightChild;
     
118.                 delete p;
     
119.                 p = NULL;
     
120. 
     
121.                 m_Length--;
     
122.                 return true;
     
123.         }
     
124. 
     
125.         if ( p->rightChild == NULL)
     
126.         {
     
127.                 Node* pParent = getParent(p);
     
128.                 if( pParent->leftChild == p)
     
129.                         pParent->leftChild = p->leftChild;
     
130.                 else
     
131.                         pParent->rightChild = p->leftChild;
     
132.                 delete p;
     
133.                 p = NULL;
     
134. 
     
135.                 m_Length--;
     
136.                 return true;       
     
137.         }
     
138. 
     
139.         if ( p->leftChild != NULL && p->rightChild != NULL)
     
140.         {
     
141.                 Node* pParent = getParent(p);
     
142.                 Node* pPre = p->leftChild;
     
143.                 Node* ptmp = pPre;
     
144.                 while( pPre->rightChild != NULL )
     
145.                 {
     
146.                         ptmp = pPre;
     
147.                         pPre = pPre->rightChild;
     
148.                 }
     
149.                 if( ptmp != pPre)
     
150.                 {        ptmp->rightChild = pPre->leftChild;
     
151.                         pPre->leftChild = p->leftChild;
     
152.                         pPre->rightChild = p->rightChild;
     
153.                 }
     
154.                 else
     
155.                         pPre->rightChild = p->rightChild;
     
156. 
     
157.                 if( pParent == NULL )
     
158.                         m_root = pPre;
     
159.                 else
     
160.                         if( pParent->leftChild == p)  
     
161.                                 pParent->leftChild = pPre;
     
162.                         else
     
163.                                 pParent->rightChild = pPre;
     
164.                
     
165.                 delete p;
     
166.                 p = NULL;
     
167. 
     
168.                 m_Length--;
     
169.                 return true;
     
170.         }
     
171.        
     
172. }
     
173. 
     
174. template<typename Type> bool        BSTrees<Type>::erase2(Type e)
     
175. {
     
176.         Node *p = find(e);
     
177.         if ( p == NULL )
     
178.         {
     
179.                 cout<<"There's no this element to delete"<<endl;
     
180.                 return false;
     
181.         }
     
182. 
     
183.         if ( p->leftChild == NULL)
     
184.         {
     
185.                 Node* pParent = getParent(p);
     
186.                 if( pParent->leftChild == p )
     
187.                         pParent->leftChild = p->rightChild;
     
188.                 else
     
189.                         pParent->rightChild = p->rightChild;
     
190.                 delete p;
     
191.                 p = NULL;
     
192. 
     
193.                 m_Length--;
     
194.                 return true;
     
195.         }
     
196. 
     
197.         if ( p->rightChild == NULL)
     
198.         {
     
199.                 Node* pParent = getParent(p);
     
200.                 if( pParent->leftChild == p)
     
201.                         pParent->leftChild = p->leftChild;
     
202.                 else
     
203.                         pParent->rightChild = p->leftChild;
     
204.                 delete p;
     
205.                 p = NULL;
     
206. 
     
207.                 m_Length--;
     
208.                 return true;       
     
209.         }
     
210.         if( p->leftChild != NULL && p->rightChild != NULL)
     
211.         {
     
212.                 Node* pParent = getParent(p);
     
213.                 Node* ptr = p->leftChild;
     
214.                 while( ptr->rightChild != NULL )
     
215.                         ptr = ptr->rightChild;
     
216.                 ptr->rightChild = p->rightChild;
     
217. 
     
218.                 if( pParent == NULL )
     
219.                         m_root = p->leftChild;
     
220.                 else
     
221.                         if(pParent->leftChild == p)
     
222.                                 pParent->leftChild = p->leftChild;
     
223.                         else
     
224.                                 pParent->rightChild = p->leftChild;
     
225.                 delete p;
     
226.                 p = NULL;
     
227.                 m_Length--;
     
228.                 return true;
     
229.         }
     
230. }
     
231. 
     
232. template<typename Type> void        BSTrees<Type>::clear()
     
233. {
     
234.         if( m_root == NULL )
     
235.                 return;
     
236.         clears(m_root);
     
237.         m_root = NULL;
     
238. }
     
239. 
     
240. template<typename Type> void         BSTrees<Type>::clears(Node* &p)
     
241. {
     
242.         if(p->leftChild != NULL)
     
243.         {
     
244.                 clears(p->leftChild);
     
245.                 p->leftChild = NULL;
     
246.         }
     
247.         if(p->rightChild != NULL)
     
248.         {
     
249.                 clears(p->rightChild);
     
250.                 p->rightChild = NULL;
     
251.         }
     
252.         delete p;
     
253.         p = NULL;
     
254.         m_Length--;
     
255.        
     
256. }
     
257. template<typename Type> typename BSTrees<Type>::Node* BSTrees<Type>::getRoot()
     
258. {
     
259.         return m_root;
     
260. }
     
261. template<typename Type> int                BSTrees<Type>::getLength()
     
262. {
     
263.         return m_Length;
     
264. }
     
265. template<typename Type> typename BSTrees<Type>::Node* BSTrees<Type>::getParent(Node* p)
     
266. {
     
267.         if( p == m_root)
     
268.                 return NULL;
     
269.         Node* ptr = m_root;
     
270.         Node* ptf = ptr;
     
271.         while( ptr != NULL )
     
272.         {
     
273.                 if ( ptr->e == p->e )
     
274.                         return ptf;
     
275.                 if ( ptr->e > p->e )
     
276.                 {
     
277.                         ptf = ptr;
     
278.                         ptr = ptr->leftChild;
     
279.                 }
     
280.                 else
     
281.                 {
     
282.                         ptf = ptr;
     
283.                         ptr = ptr->rightChild;
     
284.                 }
     
285.         }
     
286. 
     
287. }
     
288. 
     
289. template<typename Type> typename BSTrees<Type>::Node* BSTrees<Type>::find(Type e)
     
290. {
     
291.         Node* ptr = m_root;
     
292. 
     
293.         while(ptr != NULL)
     
294.         {
     
295.                 if ( ptr->e == e )
     
296.                         return ptr;
     
297.                 if ( ptr->e > e )
     
298.                         ptr = ptr->leftChild;
     
299.                 else
     
300.                         ptr = ptr->rightChild;
     
301.         }
     
302.         if ( ptr == NULL )
     
303.                 return NULL;
     
304. }
     
305. 
     
306. template<typename Type> void BSTrees<Type>::traverse(Node* ptr)
     
307. {
     
308.         if( ptr == NULL )
     
309.                 return;
     
310.         if( ptr->leftChild != NULL )
     
311.                 traverse(ptr->leftChild);
     
312.         cout<<"Element value:"<<ptr->e<<endl;
     
313.         if( ptr->rightChild != NULL )
     
314.                 traverse(ptr->rightChild);
     
315. }
     
316. 
     
317. template<typename Type> BSTrees<Type>::~BSTrees()
     
318. {
     
319.         clear();
     
320. }
     
321. #endif

复制代码

main.cpp

1. //main.cpp
   
2. #include <iostream>
   
3. #include "BSTrees.h"
   
4. using namespace std;
   
5. void main()
   
6. {
   
7.         cout<<"************************test BSTree insert***********************"<<endl;
   
8.         BSTrees<int> Bst;
   
9.         int Arr[9] = {6,2,8,4,10,0,12,16,14};
   
10.         for (int i=0;i<9;i++)
    
11.                 Bst.insert(Arr[i]);
    
12.         Bst.traverse(Bst.getRoot());
    
13.         cout<<"Tree's length is:"<<Bst.getLength()<<endl;
    
14. 
    
15.         cout<<"************************test BSTree erase1***********************"<<endl;
    
16.         //Bst.erase1(6);
    
17.         //Bst.erase1(16);
    
18.         //Bst.erase1(10);
    
19.         //Bst.erase1(8);
    
20.         Bst.erase2(6);
    
21.         Bst.erase2(16);
    
22.         Bst.erase2(10);
    
23.         Bst.erase2(8);
    
24.         Bst.traverse(Bst.getRoot());
    
25.         cout<<"Tree's length is:"<<Bst.getLength()<<endl;
    
26. 
    
27.         Bst.clear();
    
28.         Bst.traverse(Bst.getRoot());
    
29.         cout<<"Tree's length is:"<<Bst.getLength()<<endl;
    
30. }

复制代码

测试结果：

laxect

这是在屠版么。。。