'From VisualWorks(TM), Release 1.0 of 8 October 1992 on 4 November 1994 at 2:09:13 pm'!
Object subclass: #BinaryNode
instanceVariableNames: 'left right value '
classVariableNames: ''
poolDictionaries: ''
category: 'Kernel-Objects'!
!BinaryNode methodsFor: 'predicates'!
max
" find the max node value, ie. the rightmost node of the tree"
right = nil ifTrue:
[ ^value ]
ifFalse:
[ ^right max ]! !
!BinaryNode methodsFor: 'constructors'!
add: item
" note that this binary tree does not take duplicates !!"
item < value ifTrue: "go left"
[left = nil ifTrue:
[left := BinaryNode new. left setValue: item.]
ifFalse:
[left add: item.] ].
item > value ifTrue: "go right"
[right = nil ifTrue:
[right := BinaryNode new. right setValue: item.]
ifFalse:
[right add: item.] ]!
remove: item ifAbsent: aBlock
item = value ifTrue: " we've found the node we want "
[ left = right = nil ifTrue: [^nil]. " if we're at a leaf node, it's easy "
right = nil ifTrue: [^left ]. " no right children, also easy "
left = nil ifTrue: [^right ]. " no left children, also easy"
left ~= nil & right ~= nil ifTrue: " both children, it is a little trickier "
[ | maximum |
maximum := left max. value := maximum.
left := left remove: maximum ifAbsent: [^self]. ^self ] ].
item ~= value ifTrue: " we haven't found the value "
[ (left = right = nil) | (item < value & left = nil) | (item >= value & right = nil) ifTrue:
[ ^(aBlock value) ]. " the value doesn't exist, apparently "
item < value ifTrue: " the value is to the left, maybe "
[ left := left remove: item ifAbsent: aBlock ].
item >= value ifTrue: " the value is to the right, maybe "
[ right := right remove: item ifAbsent: aBlock] ]!
setValue: item
value := item.! !
!BinaryNode methodsFor: 'accessors'!
includes: item
value = item ifTrue:
[^true]
ifFalse:
[item < value ifTrue:
[left = nil ifTrue:
[^false.]
ifFalse:
[^(left includes: item)] ]
ifFalse:
[right = nil ifTrue:
[^false.]
ifFalse:
[^(right includes: item)] ] ]!
value
^value! !
!BinaryNode methodsFor: 'traversals'!
inorder: aBlock
left = nil ifFalse:
[left inorder: aBlock. aBlock value: self.
right = nil ifFalse:
[right inorder: aBlock] ]
ifTrue:
[aBlock value: self.
right = nil ifFalse:
[right inorder: aBlock] ]!
postorder: aBlock
left = nil ifFalse:
[left preorder: aBlock].
right = nil ifFalse:
[right preorder: aBlock].
aBlock value: self.!
preorder: aBlock
aBlock value: self.
left = nil ifFalse:
[left preorder: aBlock].
right = nil ifFalse:
[right preorder: aBlock].! !