《数据结构与算法分析C++描述》 搜索二叉树的C++实现
《数据结构与算法分析C++描述》
搜索二叉树的C++实现**
**
write by 九天雁翎(JTianLing) – www.jtianling.com
《数据结构与算法分析c++描述》 Mark Allen Weiss著
人民邮电大学出版
中文版第93-100面，搜索二叉树
需要说明一点的是，此搜索二叉树并没有平衡算法，所以可能会导致有可能出现O(M logN)的最坏情况。
并且几乎所有代码都用递归实现，所以效率并不是太高，并且当N足够大的时候，很多操作都可能导致栈溢出。但是因为对于树的操作用递归描述起来理解上还是比循环好的多，并且以后可以用平衡算法，所以这里都用递归了。
搜索二叉树的实现：
1
2 #ifndef __BINARY_SEARCH_TREE_H__
3 #define __BINARY_SEARCH_TREE_H__
4
5 **template** <**typename** T>
6 **class** CBinarySearchTree
7 {
8 **public** :
9 CBinarySearchTree():mpRoot(NULL) { }
10 CBinarySearchTree(**const** CBinarySearchTree& aOrig)
11 {
12 mpRoot = Clone(aOrig.mpRoot);
13 }
14 ~CBinarySearchTree()
15 {
16 MakeEmpty();
17 }
18
19 ////////////////////////////////////////////
20 // const member function
21 ////////////////////////////////////////////
22 **const** T* FindMin() **const** ;
23 **const** T* FindMax() **const** ;
24
25 **bool** Contains( **const** T& aElement) **const** ;
26 **bool** IsEmpty() **const**
27 {
28 **return** (mpRoot != NULL) ? true : false;
29 }
30
31 // I don't know how to print it in a good format
32 //void PrintTree() const;
33
34 ////////////////////////////////////////////
35 // non-const member function
36 ////////////////////////////////////////////
37 **void** MakeEmpty();
38 **void** Insert( **const** T& aElement);
39 **void** Remove( **const** T& aElement);
40
41 **const** CBinarySearchTree& **operator** =(**const** CBinarySearchTree& aOrig);
42
43 **private** :
44 **struct** CBinaryNode
45 {
46 CBinaryNode(**const** T& aElement, CBinaryNode* apLeft, CBinaryNode* apRight)
47 : mElement(aElement),mpLeft(apLeft),mpRight(apRight) { }
48
49 T mElement;
50 CBinaryNode *mpLeft;
51 CBinaryNode *mpRight;
52 };
53
54 // Root Node
55 CBinaryNode *mpRoot;
56
57 ////////////////////////////////////////////
58 // private member function to call recursively
59 ////////////////////////////////////////////
60
61 // I don't like to use reference to pointer
62 // so I used pointer to pointer instead
63 **void** Insert(**const** T& aElement, CBinaryNode** appNode) **const** ;
64 **void** Remove(**const** T& aElement, CBinaryNode** appNode) **const** ;
65
66 CBinaryNode* FindMin(CBinaryNode* apNode) **const** ;
67 CBinaryNode* FindMax(CBinaryNode* apNode) **const** ;
68 **bool** Contains(**const** T& aElement, CBinaryNode * apNode) **const** ;
69 **void** MakeEmpty(CBinaryNode** apNode);
70 //void PrintTree(CBinaryNode* apNode) const;
71 CBinaryNode* Clone(CBinaryNode* apNode) **const** ;
72
73 };
74
75
76 **template** <**typename** T>
77 **bool** CBinarySearchTree::Contains(**const** T& aElement) **const**
78 {
79 **return** Contains(aElement, mpRoot);
80 }
81
82 **template** <**typename** T>
83 **bool** CBinarySearchTree::Contains(**const** T &aElement;, CBinaryNode *apNode) **const**
84 {
85 **if**( NULL == apNode )
86 {
87 **return** false;
88 }
89 **else** **if** ( aElement < apNode->mElement )
90 {
91 **return** Contains(aElement, apNode->mpLeft);
92 }
93 **else** **if** ( aElement > apNode->mElement )
94 {
95 **return** Contains(aElement, apNode->mpRight);
96 }
97 **else**
98 {
99 **return** true; // Find it
100 }
101 }
102
103 **template** <**typename** T>
104 **void** CBinarySearchTree::Insert(**const** T &aElement;)
105 {
106 Insert(aElement, &mpRoot;);
107 }
108
109 **template** <**typename** T>
110 **void** CBinarySearchTree::Insert(**const** T& aElement, CBinaryNode** appNode) **const**
111 {
112 CBinaryNode *lpNode = *appNode;
113 **if**(NULL == lpNode)
114 {
115 *appNode = **new** CBinaryNode(aElement, NULL, NULL);
116 }
117 **else** **if**( aElement < lpNode->mElement )
118 {
119 Insert(aElement, &(lpNode->mpLeft) );
120 }
121 **else** **if**( aElement > lpNode->mElement)
122 {
123 Insert(aElement, &(lpNode->mpRight) );
124 }
125
126 // had not deal with duplicate
127 }
128
129 **template** <**typename** T>
130 **void** CBinarySearchTree::Remove(**const** T &aElement;)
131 {
132 Remove(aElement, &mpRoot;);
133 }
134
135 **template** <**typename** T>
136 **void** CBinarySearchTree::Remove(**const** T &aElement;, CBinaryNode** appNode) **const**
137 {
138 CBinaryNode* lpNode = *appNode;
139 **if**(NULL == lpNode)
140 {
141 **return** ; // Item removing is not exist
142 }
143
144 **if**( aElement < lpNode->mElement )
145 {
146 Remove(aElement, &(lpNode->mpLeft) );
147 }
148 **else** **if**( aElement > lpNode->mElement )
149 {
150 Remove(aElement, &(lpNode->mpRight) );
151 }
152 **else** **if**( NULL != lpNode->mpLeft && NULL != lpNode->mpRight) // Two children
153 {
154 lpNode->mElement = FindMin(lpNode->mpRight)->mElement;
155 Remove( lpNode->mElement, &(lpNode->mpRight) );
156 }
157 **else**
158 {
159 CBinaryNode *lpOldNode = lpNode;
160 // Even if lpNode equal NULL, this is still the right behavior we need
161 // Yeah,When lpNode have no children,we make lpNode equal NULL
162 *appNode = (lpNode->mpLeft != NULL) ? lpNode->mpLeft : lpNode->mpRight;
163 **delete** lpOldNode;
164 }
165 }
166
167
168 **template** <**typename** T>
169 **const** T* CBinarySearchTree::FindMin() **const**
170 {
171 CBinaryNode* lpNode = FindMin(mpRoot);
172 **return** (lpNode != NULL) ? &(lpNode->mElement) : NULL;
173 }
174
175
176 // damn it! So redundant words to fit to C++ syntax
177 // the only way to fix this problom is compositing defines and declares
178 // I even doubt that are there programmers could write it right
179 **template** <**typename** T>
180 **typename** CBinarySearchTree::CBinaryNode * CBinarySearchTree::FindMin(CBinaryNode* apNode) **const**
181 {
182 **if**( NULL == apNode)
183 {
184 **return** NULL;
185 }
186 **else** **if**( NULL == apNode->mpLeft)
187 {
188 // Find it
189 **return** apNode;
190 }
191 **else**
192 {
193 **return** FindMin(apNode->mpLeft);
194 }
195 }
196
197 **template** <**typename** T>
198 **const** T* CBinarySearchTree::FindMax() **const**
199 {
200 CBinaryNode* lpNode = FindMax(mpRoot);
201 **return** (lpNode != NULL) ? &(lpNode->mElement) : NULL;
202 }
203
204 **template** <**typename** T>
205 **typename** CBinarySearchTree::CBinaryNode * CBinarySearchTree::FindMax(CBinaryNode* apNode) **const**
206 {
207 **if**( NULL == apNode)
208 {
209 **return** NULL;
210 }
211 **else** **if**( NULL == apNode->mpRight)
212 {
213 // Find it
214 **return** apNode;
215 }
216 **else**
217 {
218 **return** FindMax(apNode->mpRight);
219 }
220 }
221
222 **template** <**typename** T>
223 **void** CBinarySearchTree::MakeEmpty()
224 {
225 MakeEmpty(&mpRoot;);
226 }
227
228
229 **template** <**typename** T>
230 **void** CBinarySearchTree::MakeEmpty(CBinaryNode** appNode)
231 {
232 CBinaryNode* lpNode = *appNode;
233 **if**( lpNode != NULL)
234 {
235 MakeEmpty( &(lpNode->mpLeft) );
236 MakeEmpty( &(lpNode->mpRight) );
237 **delete** lpNode;
238 }
239
240 *appNode = NULL;
241 }
242
243 // how long the syntax is...............
244 **template** <**typename** T>
245 **const** CBinarySearchTree& CBinarySearchTree::**operator** =(**const** CBinarySearchTree &aOrig;)
246 {
247 **if**(&aOrig; == **this**)
248 {
249 **return** * **this** ;
250 }
251
252 MakeEmpty();
253 mpRoot = Clone(aOrig.mpRoot);
254
255 **return** * **this** ;
256
257 }
258
259 // when you use nest class and template both,you will find out how long the C++ syntax is.....
260 // I use it once,I ask why couldn't we have a short once again.
261 **template** <**typename** T>
262 **typename** CBinarySearchTree::CBinaryNode* CBinarySearchTree::Clone(CBinaryNode *apNode) **const**
263 {
264 **if**(NULL == apNode)
265 {
266 **return** NULL;
267 }
268
269 // abuse recursion
270 **return** **new** CBinaryNode(apNode->mElement, Clone(apNode->mpLeft), Clone(apNode->mpRight));
271 }
272
273
274
275
276 #endif // __BINARY_SEARCH_TREE_H__
测试代码：
1 #include
2 #include "BinarySearchTree.h"
3 **using** **namespace** std;
4
5 **int** _tmain(**int** argc, _TCHAR* argv[])
6 {
7 CBinarySearchTree<**int** > loTree;
8
9 loTree.Insert(10);
10 loTree.Insert(20);
11 loTree.Insert(30);
12 loTree.Insert(40);
13 cout <<"Min: " <<*loTree.FindMin() <<" Max: " <<*loTree.FindMax() <<" IsContains(20) "<20) <
14 loTree.Remove(40);
15 cout <<"Min: " <<*loTree.FindMin() <<" Max: " <<*loTree.FindMax() <<" IsContains(20) " <20) <
16 loTree.Remove(30);
17 loTree.Remove(20);
18 loTree.Remove(10);
19
20
21 loTree.Insert(40);
22 cout <<"Min: " <<*loTree.FindMin() <<" Max: " <<*loTree.FindMax() <<" IsContains(20) " <20) <
23 loTree.Insert(30);
24 loTree.Insert(20);
25 loTree.Insert(10);
26 cout <<"Min: " <<*loTree.FindMin() <<" Max: " <<*loTree.FindMax() <<" IsContains(20) " <20) <
27 loTree.Remove(40);
28 loTree.Remove(30);
29 loTree.Remove(20);
30 loTree.Remove(10);
31
32 loTree.Insert(30);
33 loTree.Insert(40);
34 cout <<"Min: " <<*loTree.FindMin() <<" Max: " <<*loTree.FindMax() <<" IsContains(20) " <20) <
35 loTree.Insert(10);
36 loTree.Insert(20);
37 cout <<"Min: " <<*loTree.FindMin() <<" Max: " <<*loTree.FindMax() <<" IsContains(20) " <20) <
38 CBinarySearchTree<**int** > loTree2 = loTree;
39 cout <<"Min: " <<*loTree2.FindMin() <<" Max: " <<*loTree2.FindMax() <<" IsContains(20) " <20) <
40
41 loTree.MakeEmpty();
42
43
44
45 system("pause");
46 **return** 0;
47 }
48
write by 九天雁翎(JTianLing) – www.jtianling.com
分类:
算法
标签:
C++
《数据结构与算法分析C++描述》
二叉树
Posted By 九天雁翎 at 九天雁翎的博客 on 2009年06月14日