author | Claus Gittinger <cg@exept.de> |
Tue, 26 Feb 2008 11:29:14 +0100 | |
changeset 1930 | 935b2870be2e |
parent 1921 | 8ed4ef884253 |
child 2038 | 5c9febcb5a6a |
permissions | -rw-r--r-- |
1379 | 1 |
"{ Package: 'stx:libbasic2' }" |
2 |
||
1380 | 3 |
Collection subclass:#BinaryTree |
1379 | 4 |
instanceVariableNames:'treeRoot sortBlock' |
5 |
classVariableNames:'' |
|
6 |
poolDictionaries:'' |
|
7 |
category:'Collections-Ordered' |
|
8 |
! |
|
9 |
||
10 |
Object subclass:#BinaryTreeNode |
|
11 |
instanceVariableNames:'data leftSubtree rightSubtree' |
|
12 |
classVariableNames:'' |
|
13 |
poolDictionaries:'' |
|
14 |
privateIn:BinaryTree |
|
15 |
! |
|
16 |
||
17 |
!BinaryTree class methodsFor:'documentation'! |
|
18 |
||
19 |
documentation |
|
20 |
" |
|
21 |
Loosely based on the Public Domain BinaryTreeNode class from Steve Chepurny. |
|
22 |
||
23 |
Changes: |
|
24 |
Changed to be Collection-protocol compatible. |
|
25 |
Slight speedup in insert-code. |
|
26 |
||
27 |
[author:] |
|
28 |
Steve Chepurny (original BinaryTreeNode implementation) |
|
29 |
Claus Gittinger (cg@alan) |
|
30 |
||
31 |
[instance variables:] |
|
32 |
||
33 |
[class variables:] |
|
34 |
||
35 |
[see also:] |
|
36 |
||
37 |
" |
|
38 |
! |
|
39 |
||
40 |
examples |
|
41 |
" |
|
42 |
[exBegin] |
|
43 |
|coll| |
|
44 |
||
45 |
coll := BinaryTree new. |
|
1628 | 46 |
(1 to:10) do:[:i | coll add:i]. |
1379 | 47 |
coll addAll:(20 to:30). |
48 |
coll |
|
49 |
[exEnd] |
|
50 |
||
51 |
timing: |
|
52 |
[exBegin] |
|
53 |
|N randomNumbers coll1 coll2 t1 t2| |
|
54 |
||
55 |
N := 1000000. |
|
56 |
randomNumbers := (1 to:N) collect:[:i | Random nextInteger]. |
|
57 |
||
1380 | 58 |
ObjectMemory garbageCollect. |
1379 | 59 |
t1 := Time millisecondsToRun:[ |
60 |
coll1 := BinaryTree new. |
|
61 |
coll1 addAll:randomNumbers |
|
62 |
]. |
|
63 |
||
1380 | 64 |
coll1 := nil. |
65 |
ObjectMemory garbageCollect. |
|
1379 | 66 |
t2 := Time millisecondsToRun:[ |
1380 | 67 |
coll2 := SortedCollection new. |
68 |
coll2 addAll:randomNumbers |
|
1379 | 69 |
]. |
70 |
Transcript show:'Time to insert '; show:N; show:' into BinaryTree: '; show:t1; showCR:'ms'. |
|
71 |
Transcript show:'Time to insert '; show:N; show:' into SortedCollection: '; show:t2; showCR:'ms'. |
|
72 |
[exEnd] |
|
73 |
||
1380 | 74 |
timing 2: |
75 |
[exBegin] |
|
76 |
|allSelectors coll1 coll2 t0 t1 t2| |
|
77 |
||
78 |
allSelectors := OrderedCollection new. |
|
79 |
Smalltalk allClassesDo:[:cls | |
|
80 |
cls instAndClassSelectorsAndMethodsDo:[:sel :mthd | |
|
81 |
allSelectors add:sel. |
|
82 |
]. |
|
83 |
]. |
|
84 |
||
85 |
t1 := Time millisecondsToRun:[ |
|
86 |
coll1 := SortedCollection new. |
|
87 |
allSelectors do:[:sel | |
|
88 |
coll1 add:sel |
|
89 |
]. |
|
90 |
]. |
|
91 |
Transcript show:'Time to insert '; show:coll1 size; show:' selectors into SortedCollection: '; show:t1; showCR:'ms'. |
|
92 |
||
93 |
t2 := Time millisecondsToRun:[ |
|
94 |
coll2 := BinaryTree new. |
|
95 |
allSelectors do:[:sel | |
|
96 |
coll2 add:sel |
|
97 |
]. |
|
98 |
]. |
|
99 |
Transcript show:'Time to insert '; show:coll2 size; show:' selectors into BinaryTree: '; show:t2; showCR:'ms'. |
|
100 |
||
101 |
t1 := Time millisecondsToRun:[ |
|
102 |
allSelectors do:[:sel | |
|
103 |
coll1 remove:sel |
|
104 |
]. |
|
105 |
]. |
|
106 |
self assert:(coll1 isEmpty). |
|
107 |
Transcript show:'Time to remove selectors from SortedCollection: '; show:t1; showCR:'ms'. |
|
108 |
||
109 |
t2 := Time millisecondsToRun:[ |
|
110 |
allSelectors do:[:sel | |
|
111 |
coll2 remove:sel |
|
112 |
]. |
|
113 |
]. |
|
114 |
self assert:(coll2 isEmpty). |
|
115 |
Transcript show:'Time to remove selectors from BinaryTree: '; show:t2; showCR:'ms'. |
|
116 |
[exEnd] |
|
117 |
||
1379 | 118 |
" |
119 |
! ! |
|
120 |
||
121 |
!BinaryTree class methodsFor:'instance creation'! |
|
122 |
||
123 |
new |
|
1921
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
124 |
^ self sortBlock:[:a :b | a < b] |
1379 | 125 |
! |
126 |
||
127 |
new:n |
|
128 |
^ self new |
|
1921
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
129 |
! |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
130 |
|
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
131 |
sortBlock:aTwoArgBlock |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
132 |
^ self basicNew sortBlock:aTwoArgBlock |
1379 | 133 |
! ! |
134 |
||
1625 | 135 |
!BinaryTree methodsFor:'accessing'! |
136 |
||
137 |
sortBlock:something |
|
1921
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
138 |
"set the sort block. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
139 |
This is allowed only before any elements are stored in the tree" |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
140 |
|
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
141 |
self assert:treeRoot isNil message:'changing sortBlock in BinaryTree'. |
1625 | 142 |
sortBlock := something. |
143 |
! ! |
|
144 |
||
1379 | 145 |
!BinaryTree methodsFor:'adding & removing'! |
146 |
||
147 |
add:anObject |
|
148 |
|newNode| |
|
149 |
||
150 |
newNode := BinaryTreeNode data:anObject. |
|
151 |
treeRoot isNil ifTrue:[ |
|
152 |
treeRoot := newNode. |
|
153 |
] ifFalse:[ |
|
154 |
treeRoot insert:newNode sortBlock:sortBlock |
|
155 |
]. |
|
156 |
^ anObject "sigh - collection protocol" |
|
157 |
||
158 |
" |
|
1921
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
159 |
BinaryTree withAll:#(16 3 1 0 4 7 9) |
1379 | 160 |
BinaryTree new add:1; add:2; yourself |
161 |
BinaryTree with:1 with:2 with:3 |
|
162 |
" |
|
163 |
! |
|
164 |
||
1380 | 165 |
includesIdentical:anElement |
166 |
treeRoot isNil ifTrue:[ |
|
167 |
^ false. |
|
168 |
]. |
|
169 |
^ treeRoot includesIdenticalValue:anElement sortBlock:sortBlock. |
|
170 |
||
171 |
" |
|
172 |
BinaryTree new |
|
173 |
addAll:#(4 2 1 3 6 5 7); |
|
174 |
includesIdentical:4 |
|
175 |
" |
|
176 |
||
177 |
" |
|
178 |
BinaryTree new |
|
179 |
addAll:#(4 2 1 3 6 5 7); |
|
180 |
includesIdentical:8 |
|
181 |
" |
|
182 |
! |
|
183 |
||
184 |
remove:oldObject ifAbsent:exceptionValue |
|
185 |
|newRoot| |
|
186 |
||
187 |
treeRoot isNil ifTrue:[ |
|
188 |
^ exceptionValue value. |
|
189 |
]. |
|
190 |
newRoot := treeRoot removeValue:oldObject sortBlock:sortBlock. |
|
191 |
newRoot isNil ifTrue:[ |
|
192 |
treeRoot data = oldObject ifFalse:[ |
|
193 |
^ exceptionValue value. |
|
194 |
]. |
|
195 |
]. |
|
196 |
treeRoot := newRoot |
|
197 |
||
198 |
" |
|
199 |
BinaryTree new |
|
200 |
addAll:#(4 2 1 3 6 5 7); |
|
201 |
removeIdentical:4; |
|
202 |
yourself |
|
203 |
" |
|
204 |
||
205 |
" |
|
206 |
BinaryTree new |
|
207 |
addAll:#(4 2 1 3 6 5 7); |
|
208 |
removeIdentical:7; |
|
209 |
yourself |
|
210 |
" |
|
211 |
! |
|
212 |
||
213 |
removeIdentical:oldObject ifAbsent:exceptionValue |
|
214 |
|newRoot| |
|
215 |
||
216 |
treeRoot isNil ifTrue:[ |
|
217 |
^ exceptionValue value. |
|
218 |
]. |
|
219 |
newRoot := treeRoot removeIdenticalValue:oldObject sortBlock:sortBlock. |
|
220 |
newRoot isNil ifTrue:[ |
|
221 |
^ exceptionValue value. |
|
222 |
]. |
|
223 |
treeRoot := newRoot |
|
224 |
||
225 |
" |
|
226 |
BinaryTree new |
|
227 |
addAll:#(4 2 1 3 6 5 7); |
|
228 |
removeIdentical:4; |
|
229 |
yourself |
|
230 |
" |
|
231 |
||
232 |
" |
|
233 |
BinaryTree new |
|
234 |
addAll:#(4 2 1 3 6 5 7); |
|
235 |
removeIdentical:7; |
|
236 |
yourself |
|
237 |
" |
|
1379 | 238 |
! ! |
239 |
||
1921
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
240 |
!BinaryTree methodsFor:'enumerating'! |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
241 |
|
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
242 |
do:aBlock |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
243 |
"enumerate the tree in order" |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
244 |
|
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
245 |
treeRoot notNil ifTrue:[ |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
246 |
treeRoot inOrderDo:[:eachNode | aBlock value:(eachNode data)]. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
247 |
]. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
248 |
|
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
249 |
" |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
250 |
|coll| |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
251 |
|
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
252 |
coll:= OrderedCollection new. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
253 |
(BinaryTree withAll:#(5 4 3 2 1 6 7 8 9 0)) do:[:each| coll add:each]. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
254 |
coll |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
255 |
" |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
256 |
|
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
257 |
" |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
258 |
|coll| |
1379 | 259 |
|
1921
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
260 |
coll:= OrderedCollection new. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
261 |
(BinaryTree withAll:#(5 4 3 2 1 6 7 8 9 0)) preOrderDo:[:each| coll add:each]. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
262 |
coll |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
263 |
" |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
264 |
|
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
265 |
" |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
266 |
|coll| |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
267 |
|
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
268 |
coll:= OrderedCollection new. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
269 |
(BinaryTree withAll:#(5 4 3 2 1 6 7 8 9 0)) postOrderDo:[:each| coll add:each]. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
270 |
coll |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
271 |
" |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
272 |
! |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
273 |
|
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
274 |
postOrderDo:aBlock |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
275 |
"enumerate in postOrder - Left, Right, Root" |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
276 |
|
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
277 |
treeRoot notNil ifTrue:[ |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
278 |
treeRoot postOrderDo:[:eachNode | aBlock value:(eachNode data)]. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
279 |
]. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
280 |
! |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
281 |
|
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
282 |
preOrderDo:aBlock |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
283 |
"enumerate in preOrder - Root, Left, Right" |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
284 |
|
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
285 |
treeRoot notNil ifTrue:[ |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
286 |
treeRoot preOrderDo:[:eachNode | aBlock value:(eachNode data)]. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
287 |
]. |
1379 | 288 |
! ! |
289 |
||
290 |
!BinaryTree methodsFor:'queries'! |
|
291 |
||
292 |
size |
|
293 |
^ treeRoot size |
|
294 |
! ! |
|
295 |
||
296 |
!BinaryTree::BinaryTreeNode class methodsFor:'documentation'! |
|
297 |
||
298 |
copyright |
|
299 |
" |
|
300 |
Public domain (I guess, as it was published in c.l.s) |
|
301 |
no limitation on use. |
|
302 |
||
303 |
This class is provided as-is, without any warranty. |
|
304 |
It is not part of or covered by the ST/X copyright. |
|
305 |
" |
|
306 |
! |
|
307 |
||
308 |
documentation |
|
309 |
" |
|
310 |
goody from comp.lang.smalltalk; |
|
311 |
original header: |
|
312 |
||
313 |
Here's a complete implementation of a binary tree class: |
|
314 |
||
315 |
||
316 |
claus: |
|
317 |
I would have called this a BinaryTreeNode .... |
|
318 |
||
319 |
||
320 |
[organization:] |
|
321 |
The National Capital FreeNet, Ottawa, Ontario, Canada |
|
322 |
||
323 |
[author:] |
|
324 |
al938@FreeNet.Carleton.CA (Steve Chepurny) |
|
325 |
||
326 |
[see also:] |
|
327 |
LinkedList Chain |
|
328 |
Link ValueLink ChainLink |
|
329 |
" |
|
330 |
! |
|
331 |
||
332 |
examples |
|
333 |
" |
|
334 |
manual building of a tree: |
|
335 |
[exBegin] |
|
336 |
|tree| |
|
337 |
||
338 |
tree := BinaryTreeNode data:2. |
|
339 |
tree leftSubtree:(BinaryTreeNode new data:1). |
|
340 |
tree rightSubtree:(BinaryTreeNode new data:3). |
|
341 |
tree printOn:Transcript. |
|
342 |
[exEnd] |
|
343 |
||
344 |
insertion: |
|
345 |
[exBegin] |
|
346 |
|tree| |
|
347 |
||
348 |
tree := BinaryTreeNode data:'hello'. |
|
349 |
#('the' 'quick' 'brown' 'fox' 'jumps' 'over' 'the' 'lazy' 'dogs') |
|
350 |
do:[:word | |
|
351 |
tree insert:(BinaryTreeNode data:word). |
|
352 |
]. |
|
353 |
tree inOrderDo:[:node | |
|
354 |
Transcript showCR:node data |
|
355 |
] |
|
356 |
[exEnd] |
|
357 |
" |
|
358 |
! ! |
|
359 |
||
360 |
!BinaryTree::BinaryTreeNode class methodsFor:'instance creation'! |
|
361 |
||
362 |
data:data |
|
363 |
"Returns a new binary tree node, holding data" |
|
364 |
||
365 |
^ self basicNew initialize data:data |
|
366 |
||
367 |
"Modified: 10.5.1996 / 15:00:13 / cg" |
|
368 |
"Created: 10.5.1996 / 15:00:35 / cg" |
|
369 |
! |
|
370 |
||
371 |
empty |
|
372 |
"Returns a new binary tree with subtrees as binary tree nodes" |
|
373 |
||
374 |
^ self new |
|
375 |
leftSubtree: self new; |
|
376 |
rightSubtree: self new |
|
377 |
||
378 |
"Modified: 10.5.1996 / 15:00:02 / cg" |
|
379 |
! |
|
380 |
||
381 |
new |
|
382 |
"Returns a new empty binary tree node" |
|
383 |
||
384 |
^ self basicNew initialize |
|
385 |
||
386 |
"Modified: 10.5.1996 / 15:00:13 / cg" |
|
387 |
! ! |
|
388 |
||
389 |
!BinaryTree::BinaryTreeNode methodsFor:'accessing'! |
|
390 |
||
391 |
data |
|
392 |
^data |
|
393 |
! |
|
394 |
||
395 |
data: anObject |
|
396 |
data := anObject |
|
397 |
! |
|
398 |
||
399 |
leftSubtree |
|
400 |
^leftSubtree |
|
401 |
! |
|
402 |
||
403 |
leftSubtree: aBinaryTree |
|
404 |
leftSubtree := aBinaryTree |
|
405 |
! |
|
406 |
||
407 |
rightSubtree |
|
408 |
^rightSubtree |
|
409 |
! |
|
410 |
||
411 |
rightSubtree: aBinaryTree |
|
412 |
rightSubtree := aBinaryTree |
|
413 |
! ! |
|
414 |
||
415 |
!BinaryTree::BinaryTreeNode methodsFor:'enumeration'! |
|
416 |
||
417 |
do: aBlock |
|
418 |
"applies aBlock to each elements data in the binary tree in inorder" |
|
419 |
||
420 |
self inOrderDo:[:eachNode | aBlock value:eachNode data] |
|
421 |
! |
|
422 |
||
423 |
inOrderDo:aBlock |
|
424 |
"Traverses the elements of the binary tree in |
|
425 |
LEFT - ROOT - RIGHT order, |
|
1921
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
426 |
applying a block to each node. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
427 |
|
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
428 |
We use an interative approach here, to avoid VM stack overflow" |
1379 | 429 |
|
1921
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
430 |
|nextNode stack| |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
431 |
|
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
432 |
stack := Stack new. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
433 |
nextNode := self. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
434 |
[ |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
435 |
|left| |
1379 | 436 |
|
1921
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
437 |
stack push:nextNode. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
438 |
left := nextNode leftSubtree. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
439 |
left isNil ifTrue:[ |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
440 |
[ |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
441 |
stack isEmpty ifTrue:[ |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
442 |
^ self |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
443 |
]. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
444 |
nextNode := stack pop. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
445 |
aBlock value:nextNode. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
446 |
nextNode := nextNode rightSubtree. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
447 |
] doWhile:[nextNode isNil] |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
448 |
] ifFalse:[ |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
449 |
nextNode := left. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
450 |
]. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
451 |
] loop. |
1379 | 452 |
|
1921
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
453 |
" |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
454 |
BinaryTree withAll:#(2 16 3 1 0 4 7 9) |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
455 |
" |
1379 | 456 |
! |
457 |
||
458 |
postOrderDo: aBlock |
|
459 |
"Traverses the elements of the binary tree in |
|
460 |
LEFT - RIGHT - ROOT order, |
|
461 |
applying a block to each node" |
|
462 |
||
463 |
leftSubtree notNil ifTrue:[ |
|
464 |
leftSubtree postOrderDo: aBlock |
|
465 |
]. |
|
466 |
rightSubtree notNil ifTrue:[ |
|
467 |
rightSubtree postOrderDo: aBlock |
|
468 |
]. |
|
469 |
||
470 |
aBlock value: self. |
|
471 |
! |
|
472 |
||
473 |
preOrderDo: aBlock |
|
474 |
"Traverses the elements of the binary tree in |
|
475 |
ROOT - LEFT - RIGHT order, |
|
476 |
applying a block to each node" |
|
477 |
||
478 |
aBlock value: self. |
|
479 |
||
480 |
leftSubtree notNil ifTrue:[ |
|
481 |
leftSubtree preOrderDo: aBlock |
|
482 |
]. |
|
483 |
rightSubtree notNil ifTrue:[ |
|
484 |
rightSubtree preOrderDo: aBlock |
|
485 |
]. |
|
486 |
! ! |
|
487 |
||
1380 | 488 |
!BinaryTree::BinaryTreeNode methodsFor:'insert & delete'! |
1379 | 489 |
|
490 |
insert:aBinaryTreeNode |
|
491 |
"insert a node, comparing nodes using a default sort rule" |
|
492 |
||
493 |
^ self |
|
494 |
insert:aBinaryTreeNode |
|
495 |
sortBlock:[:a :b | a < b] |
|
496 |
||
497 |
"Modified: 10.5.1996 / 15:08:30 / cg" |
|
498 |
"Created: 10.5.1996 / 15:09:44 / cg" |
|
499 |
! |
|
500 |
||
501 |
insert:newBinaryTreeNode sortBlock:sortBlock |
|
502 |
"insert a node, comparing nodes using sortBlock" |
|
503 |
||
1921
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
504 |
"/ the following might be ugly - however, it it slightly faster than the stuff below. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
505 |
"/ AND it does not suffer stack exhaustion.... |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
506 |
"/ (we MUST have LCO in smalltalk for this to be automatically faster |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
507 |
|
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
508 |
|
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
509 |
|node newValue left right| |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
510 |
|
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
511 |
node := self. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
512 |
newValue := newBinaryTreeNode data. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
513 |
[true] whileTrue:[ |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
514 |
"newValue is less the node data" |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
515 |
(sortBlock value:newValue value:node data) ifTrue:[ |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
516 |
left := node leftSubtree. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
517 |
left isNil ifTrue:[ |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
518 |
node leftSubtree:newBinaryTreeNode. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
519 |
^ self |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
520 |
]. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
521 |
node := left |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
522 |
] ifFalse:[ |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
523 |
"newValue is larger or equal than node data" |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
524 |
right := node rightSubtree. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
525 |
"if right data is less than node, we would be jumping back..." |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
526 |
right isNil ifTrue:[ |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
527 |
node rightSubtree:newBinaryTreeNode. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
528 |
^ self |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
529 |
]. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
530 |
node := right |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
531 |
] |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
532 |
]. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
533 |
"not reached" |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
534 |
|
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
535 |
"/ (sortBlock value:newBinaryTreeNode data value:data) ifTrue:[ |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
536 |
"/ leftSubtree isNil ifTrue:[ |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
537 |
"/ leftSubtree := newBinaryTreeNode. |
1380 | 538 |
"/ ] ifFalse:[ |
1921
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
539 |
"/ leftSubtree insert:newBinaryTreeNode sortBlock:sortBlock |
1380 | 540 |
"/ ] |
1921
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
541 |
"/ ] ifFalse:[ |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
542 |
"/ rightSubtree isNil ifTrue:[ |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
543 |
"/ rightSubtree := newBinaryTreeNode. |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
544 |
"/ ] ifFalse:[ |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
545 |
"/ rightSubtree insert:newBinaryTreeNode sortBlock:sortBlock |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
546 |
"/ ] |
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
547 |
"/ ] |
1379 | 548 |
|
1921
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
549 |
BinaryTree withAll:#(16 3 1 0 4 7 9) |
1380 | 550 |
! |
551 |
||
552 |
removeIdenticalValue:oldValue sortBlock:sortBlock |
|
553 |
"remove a value - returns a new treeNode, or nil if the value is not in the tree" |
|
554 |
||
1475 | 555 |
^ self removeValue:oldValue using:#== sortBlock:sortBlock |
556 |
! |
|
557 |
||
558 |
removeValue:oldValue sortBlock:sortBlock |
|
559 |
"remove a value - returns a new treeNode, or nil if the value is not in the tree" |
|
560 |
||
561 |
^ self removeValue:oldValue using:#= sortBlock:sortBlock |
|
562 |
! |
|
563 |
||
564 |
removeValue:oldValue using:compareOp sortBlock:sortBlock |
|
565 |
"remove a value - returns a new treeNode, or nil if the value is not in the tree" |
|
1380 | 566 |
|
1475 | 567 |
|thisIsMyNode newTop| |
568 |
||
569 |
"/ speed hack - avoids message sends |
|
570 |
compareOp == #== ifTrue:[ |
|
571 |
thisIsMyNode := (data == oldValue). |
|
572 |
] ifFalse:[ |
|
573 |
compareOp == #= ifTrue:[ |
|
574 |
thisIsMyNode := (data = oldValue). |
|
575 |
] ifFalse:[ |
|
576 |
thisIsMyNode := data perform:compareOp with:oldValue. |
|
577 |
]. |
|
578 |
]. |
|
579 |
||
580 |
thisIsMyNode ifTrue:[ |
|
1380 | 581 |
leftSubtree isNil ifTrue:[ |
582 |
^ rightSubtree |
|
583 |
]. |
|
584 |
rightSubtree isNil ifTrue:[ |
|
585 |
^ leftSubtree |
|
586 |
]. |
|
587 |
newTop := self removeLeftRightMostNode. |
|
588 |
newTop leftSubtree:leftSubtree. |
|
589 |
newTop rightSubtree:rightSubtree. |
|
590 |
^ newTop. |
|
1379 | 591 |
]. |
592 |
||
1380 | 593 |
(sortBlock value:oldValue value:data) ifTrue:[ |
1475 | 594 |
"/ the value should be in the left half. |
1380 | 595 |
leftSubtree isNil ifTrue:[ |
596 |
^ nil |
|
597 |
]. |
|
1475 | 598 |
leftSubtree := leftSubtree removeValue:oldValue using:compareOp sortBlock:sortBlock. |
599 |
] ifFalse:[ |
|
600 |
"/ the value should be in the right half. |
|
1380 | 601 |
rightSubtree isNil ifTrue:[ |
602 |
^ nil |
|
603 |
]. |
|
1475 | 604 |
rightSubtree := rightSubtree removeValue:oldValue using:compareOp sortBlock:sortBlock. |
1380 | 605 |
]. |
606 |
^ self. |
|
1379 | 607 |
! ! |
608 |
||
609 |
!BinaryTree::BinaryTreeNode methodsFor:'printing'! |
|
610 |
||
611 |
printOn: aStream |
|
612 |
"Append the ascii representation to aStream" |
|
613 |
||
614 |
data isNil |
|
615 |
ifTrue: [aStream nextPutAll: '--'] |
|
616 |
ifFalse: [ |
|
617 |
aStream nextPut: $(. |
|
618 |
data printOn: aStream. aStream nextPut: $ . |
|
619 |
leftSubtree printOn: aStream. aStream nextPut: $ . |
|
620 |
rightSubtree printOn: aStream. |
|
621 |
aStream nextPut: $)] |
|
1475 | 622 |
! |
623 |
||
624 |
printOn:aStream indent:i |
|
625 |
"Append the graphical ascii representation to aStream" |
|
626 |
||
627 |
data isNil |
|
628 |
ifTrue: [aStream spaces:i. aStream nextPutAll: '--'] |
|
629 |
ifFalse: [ |
|
630 |
aStream spaces:i. aStream nextPut: $(. |
|
631 |
data printOn: aStream. |
|
632 |
aStream cr. |
|
633 |
leftSubtree isNil |
|
634 |
ifTrue:[ aStream spaces:i+2. '--' printOn: aStream] |
|
635 |
ifFalse:[ leftSubtree printOn: aStream indent:i+2 ]. |
|
636 |
aStream cr. |
|
637 |
rightSubtree isNil |
|
638 |
ifTrue:[ aStream spaces:i+2. '--' printOn: aStream] |
|
639 |
ifFalse:[ rightSubtree printOn: aStream indent:i+2 ]. |
|
640 |
aStream nextPut: $) |
|
641 |
] |
|
1379 | 642 |
! ! |
643 |
||
1380 | 644 |
!BinaryTree::BinaryTreeNode methodsFor:'private helpers'! |
645 |
||
646 |
removeLeftRightMostNode |
|
647 |
|rightMost| |
|
648 |
||
649 |
leftSubtree rightSubtree isNil ifTrue:[ |
|
650 |
rightMost := leftSubtree. |
|
651 |
leftSubtree := leftSubtree leftSubtree. |
|
652 |
^ rightMost. |
|
653 |
]. |
|
654 |
||
655 |
^ leftSubtree removeRightMostNode |
|
656 |
||
657 |
" |
|
658 |
|tree| |
|
659 |
||
660 |
tree := BinaryTreeNode data:4. |
|
661 |
#(2 6 1 3 5 7) |
|
662 |
do:[:word | |
|
663 |
tree insert:(BinaryTreeNode data:word). |
|
664 |
]. |
|
1475 | 665 |
tree printOn:Transcript indent:0. Transcript cr. |
666 |
'---------------------------' printOn:Transcript. Transcript cr. |
|
1380 | 667 |
tree removeLeftRightMostNode. |
1475 | 668 |
tree printOn:Transcript indent:0. Transcript cr. |
1380 | 669 |
" |
670 |
! |
|
671 |
||
672 |
removeRightMostNode |
|
673 |
|removedNode| |
|
674 |
||
675 |
rightSubtree isNil ifTrue:[ |
|
676 |
self error:'should not happen' |
|
677 |
]. |
|
678 |
rightSubtree rightSubtree notNil ifTrue:[ |
|
679 |
^ rightSubtree removeRightMostNode. |
|
680 |
]. |
|
681 |
removedNode := rightSubtree. |
|
682 |
rightSubtree := nil. |
|
683 |
^ removedNode |
|
684 |
||
685 |
" |
|
686 |
|tree| |
|
687 |
||
688 |
tree := BinaryTreeNode data:4. |
|
689 |
#(2 6 1 3 5 7) |
|
690 |
do:[:word | |
|
691 |
tree insert:(BinaryTreeNode data:word). |
|
692 |
]. |
|
693 |
Transcript showCR:tree. |
|
694 |
Transcript showCR:(tree removeLeftRightMostNode). |
|
695 |
Transcript showCR:tree. |
|
696 |
" |
|
697 |
! ! |
|
698 |
||
1379 | 699 |
!BinaryTree::BinaryTreeNode methodsFor:'queries'! |
700 |
||
701 |
depth |
|
702 |
"Returns the depth of the binary list" |
|
703 |
||
704 |
^ self level - 1. |
|
705 |
! |
|
706 |
||
707 |
getTreeWithAnInteger: anInteger |
|
708 |
"Private - Returns the BinaryTree with data anInteger. |
|
709 |
If anInteger not in the tree it returns nil." |
|
710 |
||
711 |
self inOrderDo: [:each| each data = anInteger ifTrue:[^each]]. |
|
712 |
^nil. |
|
713 |
! |
|
714 |
||
715 |
inOrderSuccessor |
|
1380 | 716 |
"Returns the in-order successor the of receiver. |
717 |
(that is the leftMost node on the right side) |
|
1379 | 718 |
If receiver is empty then returns the receiver." |
719 |
||
720 |
rightSubtree isNil ifTrue:[^ self]. |
|
1380 | 721 |
^ rightSubtree leftMostNode |
722 |
! |
|
723 |
||
724 |
includesIdenticalValue:aValue sortBlock:sortBlock |
|
725 |
"return true, if aValue is contained as some node's data" |
|
726 |
||
727 |
data == aValue ifTrue:[ ^ true ]. |
|
728 |
(sortBlock value:aValue value:data) ifTrue:[ |
|
729 |
leftSubtree isNil ifTrue:[ |
|
730 |
^ false |
|
731 |
]. |
|
732 |
^ leftSubtree includesIdenticalValue:aValue sortBlock:sortBlock. |
|
733 |
]. |
|
734 |
rightSubtree isNil ifTrue:[ |
|
735 |
^ false |
|
736 |
]. |
|
737 |
^ rightSubtree includesIdenticalValue:aValue sortBlock:sortBlock. |
|
738 |
! |
|
739 |
||
740 |
includesValue:aValue sortBlock:sortBlock |
|
741 |
"return true, if some node's data is equal to aValue" |
|
742 |
||
743 |
data = aValue ifTrue:[ ^ true ]. |
|
744 |
||
745 |
(sortBlock value:aValue value:data) ifTrue:[ |
|
746 |
leftSubtree isNil ifTrue:[ |
|
747 |
^ false |
|
748 |
]. |
|
749 |
^ leftSubtree includesIdenticalValue:aValue. |
|
750 |
]. |
|
751 |
rightSubtree isNil ifTrue:[ |
|
752 |
^ false |
|
753 |
]. |
|
754 |
^ rightSubtree includesIdenticalValue:aValue. |
|
1379 | 755 |
! |
756 |
||
757 |
isEmpty |
|
758 |
"returns true if the binary tree is empty and false otherwise" |
|
759 |
||
760 |
^ data isNil |
|
761 |
! |
|
762 |
||
763 |
isLeaf |
|
764 |
"Returns true if self is a leaf" |
|
765 |
||
766 |
^ ((leftSubtree isNil) and: [rightSubtree isNil]) |
|
767 |
! |
|
768 |
||
1380 | 769 |
leftMostNode |
770 |
"Returns the leftMost (smallest-valued) node" |
|
771 |
||
772 |
leftSubtree isNil ifTrue:[^ self]. |
|
773 |
^ leftSubtree leftMostNode |
|
774 |
! |
|
775 |
||
1379 | 776 |
level |
777 |
"Returns the depth of the binary tree" |
|
778 |
||
779 |
|l| |
|
780 |
||
781 |
l := 0. |
|
782 |
leftSubtree notNil ifTrue:[ |
|
783 |
l := leftSubtree level |
|
784 |
]. |
|
785 |
rightSubtree notNil ifTrue:[ |
|
786 |
l := l max:(rightSubtree level) |
|
787 |
]. |
|
788 |
^ l + 1 |
|
789 |
! |
|
790 |
||
1380 | 791 |
rightMostNode |
792 |
"Returns the rightMost (largest-valued) node" |
|
793 |
||
794 |
rightSubtree isNil ifTrue:[^ self]. |
|
795 |
^ rightSubtree rightMostNode |
|
796 |
! |
|
797 |
||
1379 | 798 |
size |
799 |
"Returns the size of the binary tree by traversing each element inorder" |
|
800 |
||
801 |
|count| |
|
802 |
||
803 |
count := 0. |
|
804 |
self inOrderDo: [:each | count := count + 1]. |
|
805 |
^ count |
|
806 |
! ! |
|
807 |
||
808 |
!BinaryTree class methodsFor:'documentation'! |
|
809 |
||
810 |
version |
|
1921
8ed4ef884253
Use non-recursive algorithms to add and enumerate
Stefan Vogel <sv@exept.de>
parents:
1628
diff
changeset
|
811 |
^ '$Header: /cvs/stx/stx/libbasic2/BinaryTree.st,v 1.6 2007-12-06 21:51:49 stefan Exp $' |
1379 | 812 |
! ! |