'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].! !