/[hs]/btree/btree.cpp
ViewVC logotype

Contents of /btree/btree.cpp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.10 - (show annotations) (download)
Thu Jan 9 17:11:09 2003 UTC (16 years, 4 months ago) by jeremyd
Branch: MAIN
CVS Tags: RELEASE_1_0, HEAD
Changes since 1.9: +3 -0 lines
Release 1

1 //Jeremy Drake
2 //Period 2
3 //Binary tree
4 #include "btree.h"
5
6 treeNode::treeNode (int tempId, int tempInv, treeNode *tempLeft, treeNode *tempRight)
7 : id (tempId), inv(tempInv), left(tempLeft), right(tempRight)
8 {
9 // all values initialized using initializer list
10 }
11
12 void btre::insert(int value, treeNode *tmp)
13 {
14 if(!top)
15 top=new treeNode(value, 1, NULL, NULL);
16 else if( !tmp )
17 insert(value, top);
18 else if(value > tmp->id)
19 if(!tmp->right)
20 tmp->right=new treeNode(value, 1, NULL, NULL);
21 else
22 insert(value, tmp->right);
23 else
24 if(!tmp->left)
25 tmp->left=new treeNode(value, 1, NULL, NULL);
26 else
27 insert(value, tmp->left);
28 }
29
30 /*void btre::clear(treeNode *tmp)
31 {
32 treeNode *foo;
33 if(!top)
34 return;
35
36 if(!tmp)
37 {
38 clear(top);
39 return;
40 }
41
42 if(tmp->left)
43 clear(tmp->left);
44
45 foo=tmp->right;
46 delete tmp;
47 if(foo)
48 clear(foo);
49 }*/
50
51 /*void btre::mirror(treeNode *tmp)
52 {
53 treeNode *foo;
54 if(!top)
55 return;
56
57 if(!tmp)
58 {
59 mirror(top);
60 return;
61 }
62
63 if(tmp->left)
64 mirror(tmp->left);
65
66 if(tmp->right)
67 mirror(tmp->right);
68
69 foo=tmp->right;
70 tmp->right=tmp->left;
71 tmp->left=foo;
72 }*/
73
74 void btre::inorder(treeNode *tmp, void (*pt2Func)(treeNode *, void*), void *param)
75 {
76 if(!top)
77 return;
78
79 if(!tmp)
80 {
81 inorder(top, pt2Func, param);
82 return;
83 }
84
85 if(tmp->left)
86 inorder(tmp->left, pt2Func, param);
87
88 (*pt2Func)(tmp, param);
89
90 if(tmp->right)
91 inorder(tmp->right, pt2Func, param);
92 }
93
94 void btre::preorder(treeNode *tmp, void (*pt2Func)(treeNode *, void*), void *param)
95 {
96 if(!top)
97 return;
98
99 if(!tmp)
100 {
101 preorder(top, pt2Func, param);
102 return;
103 }
104
105 (*pt2Func)(tmp, param);
106
107 if(tmp->left)
108 preorder(tmp->left, pt2Func, param);
109
110 if(tmp->right)
111 preorder(tmp->right, pt2Func, param);
112 }
113
114 void btre::postorder(treeNode *tmp, void (*pt2Func)(treeNode *, void*), void *param)
115 {
116 if(!top)
117 return;
118
119 if(!tmp)
120 {
121 postorder(top, pt2Func, param);
122 return;
123 }
124
125 if(tmp->left)
126 postorder(tmp->left, pt2Func, param);
127
128 if(tmp->right)
129 postorder(tmp->right, pt2Func, param);
130
131 (*pt2Func)(tmp, param);
132 }
133 void btre::inorderLeaves(treeNode *tmp, void (*pt2Func)(treeNode *, void*), void *param)
134 {
135 if(!top)
136 return;
137
138 if(!tmp)
139 {
140 inorderLeaves(top, pt2Func, param);
141 return;
142 }
143
144 if(tmp->left)
145 inorderLeaves(tmp->left, pt2Func, param);
146
147 if(!tmp->left && !tmp->right)
148 (*pt2Func)(tmp, param);
149
150 if(tmp->right)
151 inorderLeaves(tmp->right, pt2Func, param);
152 }
153
154 void btre::preorderLeaves(treeNode *tmp, void (*pt2Func)(treeNode *, void*), void *param)
155 {
156 if(!top)
157 return;
158
159 if(!tmp)
160 {
161 preorderLeaves(top, pt2Func, param);
162 return;
163 }
164
165 if(!tmp->left && !tmp->right)
166 (*pt2Func)(tmp, param);
167
168 if(tmp->left)
169 preorderLeaves(tmp->left, pt2Func, param);
170
171 if(tmp->right)
172 preorderLeaves(tmp->right, pt2Func, param);
173 }
174
175 void btre::postorderLeaves(treeNode *tmp, void (*pt2Func)(treeNode *, void*), void *param)
176 {
177 if(!top)
178 return;
179
180 if(!tmp)
181 {
182 postorderLeaves(top, pt2Func, param);
183 return;
184 }
185
186 if(tmp->left)
187 postorderLeaves(tmp->left, pt2Func, param);
188
189 if(tmp->right)
190 postorderLeaves(tmp->right, pt2Func, param);
191
192 if(!tmp->left && !tmp->right)
193 (*pt2Func)(tmp, param);
194 }
195
196 int btre::height(treeNode *tmp)
197 {
198 if(!top)
199 return 0;
200
201 if(!tmp)
202 return 1+height(top);
203
204 if(!(tmp->left || tmp->right))
205 return 0;
206 else
207 return 1 + btre::maxx(tmp->left ? height(tmp->left) : 0, tmp->right ? height(tmp->right) : 0);
208 }
209
210 int btre::width(treeNode *tmp)
211 {
212 if(!top)
213 return 0;
214
215 if(!tmp)
216 return width(top)+2;
217
218 return maxx(maxx((tmp->left ? height(tmp->left) : 0)+1+(tmp->right ? height(tmp->right) : 0), (tmp->left ? width(tmp->left) : 0)), (tmp->right ? width(tmp->right) : 0));
219 }
220
221 bool btre::search(int data, treeNode *tmp)
222 {
223 if(!top)
224 return false;
225
226 if(!tmp)
227 return search(data, top);
228
229 if(data < tmp->id)
230 {
231 if(tmp->left)
232 return search(data, tmp->left);
233 else
234 return false;
235 }else if(data > tmp->id)
236 {
237 if(tmp->right)
238 return search(data, tmp->right);
239 else
240 return false;
241 }else
242 return true;
243 }
244
245 bool btre::del(int data, treeNode **tmp)
246 {
247 if(!top)
248 return false;
249
250 if(!tmp)
251 return del(data, &top);
252
253 if(data < (*tmp)->id)
254 {
255 if((*tmp)->left)
256 return del(data, &(*tmp)->left);
257 else
258 return false;
259 }else if(data > (*tmp)->id)
260 {
261 if((*tmp)->right)
262 return del(data, &(*tmp)->right);
263 else
264 return false;
265 }else{
266 // Found it
267 if(!((*tmp)->left || (*tmp)->right))
268 {
269 delete *tmp;
270 *tmp=NULL;
271 return true;
272 }else if((bool)((*tmp)->left) ^ (bool)((*tmp)->right))
273 {
274 if((*tmp)->left)
275 {
276 treeNode *t=(*tmp)->left;
277 delete *tmp;
278 *tmp=t;
279 return true;
280 }else{
281 treeNode *t=(*tmp)->right;
282 delete *tmp;
283 *tmp=t;
284 return true;
285 }
286 }else{
287 treeNode *t=(*tmp)->left;
288 treeNode *p=NULL;
289
290 while(t->right && (p=t) && (t=t->right));
291 (*tmp)->id=t->id;
292 p && (p->right=t->left);
293 delete t;
294 return true;
295 }
296 }
297 }

cvs@jdrake.com
ViewVC Help
Powered by ViewVC 1.1.13