--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/BinaryTreeNode.st Sun Aug 05 18:49:40 2012 +0200
@@ -0,0 +1,551 @@
+"
+ Public domain (1996 published in c.l.s) no limitation on use.
+
+ This class is provided as-is, without any warranty.
+ It is not part of or covered by the ST/X copyright.
+"
+'From Smalltalk/X, Version:6.2.2 on 05-08-2012 at 18:49:10' !
+
+"{ Package: 'stx:libbasic2' }"
+
+Object subclass:#BinaryTreeNode
+ instanceVariableNames:'data leftSubtree rightSubtree'
+ classVariableNames:''
+ poolDictionaries:''
+ category:'Collections-Ordered-Trees'
+!
+
+!BinaryTreeNode class methodsFor:'documentation'!
+
+copyright
+"
+ Public domain (1996 published in c.l.s) no limitation on use.
+
+ This class is provided as-is, without any warranty.
+ It is not part of or covered by the ST/X copyright.
+"
+!
+
+documentation
+"
+ goody from comp.lang.smalltalk;
+ original header:
+
+ Here's a complete implementation of a binary tree class:
+
+
+ [organization:]
+ The National Capital FreeNet, Ottawa, Ontario, Canada
+
+ [author:]
+ al938@FreeNet.Carleton.CA (Steve Chepurny)
+
+ [see also:]
+ LinkedList Chain
+ Link ValueLink ChainLink
+"
+!
+
+examples
+"
+ manual building of a tree (but see BinaryTree for a collection-facade):
+ [exBegin]
+ |tree|
+
+ tree := BinaryTreeNode data:2.
+ tree leftSubtree:(BinaryTreeNode new data:1).
+ tree rightSubtree:(BinaryTreeNode new data:3).
+ tree printOn:Transcript.
+ [exEnd]
+
+ insertion:
+ [exBegin]
+ |tree|
+
+ tree := BinaryTreeNode data:'hello'.
+ #('the' 'quick' 'brown' 'fox' 'jumps' 'over' 'the' 'lazy' 'dogs')
+ do:[:word |
+ tree insert:(BinaryTreeNode data:word).
+ ].
+ tree inOrderDo:[:node |
+ Transcript showCR:node data
+ ]
+ [exEnd]
+"
+! !
+
+!BinaryTreeNode class methodsFor:'instance creation'!
+
+data:data
+ "Returns a new binary tree node, holding data"
+
+ ^ self basicNew data:data
+
+ "Modified: 10.5.1996 / 15:00:13 / cg"
+ "Created: 10.5.1996 / 15:00:35 / cg"
+!
+
+empty
+ "Returns a new binary tree with subtrees as binary tree nodes"
+
+ ^ self new
+ leftSubtree: self new;
+ rightSubtree: self new
+
+ "Modified: 10.5.1996 / 15:00:02 / cg"
+! !
+
+!BinaryTreeNode methodsFor:'accessing'!
+
+data
+ ^ data
+!
+
+data:anObject
+ data := anObject
+!
+
+leftSubtree
+ ^leftSubtree
+!
+
+leftSubtree: aBinaryTree
+ leftSubtree := aBinaryTree
+!
+
+nextNodeInOrder
+ "return the node holding the next value"
+
+ ^ rightSubtree leftMostNode
+!
+
+predecessor
+ "return the previous value"
+
+ ^ self prevNodeInOrder data
+!
+
+prevNodeInOrder
+ "return the node holding the previous value"
+
+ ^ leftSubtree rightMostNode
+!
+
+rightSubtree
+ ^rightSubtree
+!
+
+rightSubtree: aBinaryTree
+ rightSubtree := aBinaryTree
+!
+
+successor
+ "return the next value"
+
+ ^ self nextNodeInOrder data
+! !
+
+!BinaryTreeNode methodsFor:'enumeration'!
+
+do: aBlock
+ "applies aBlock to each element's data in the binary tree in inorder"
+
+ self inOrderDo:[:eachNode | aBlock value:eachNode data]
+!
+
+inOrderDo:aBlock
+ "Traverses the elements of the binary tree in
+ LEFT - ROOT - RIGHT order,
+ applying a block to each node.
+
+ We use an interative approach here, to avoid VM stack overflow"
+
+ |nextNode stack|
+
+ stack := Stack new.
+ nextNode := self.
+ [
+ |left|
+
+ stack push:nextNode.
+ left := nextNode leftSubtree.
+ left isNil ifTrue:[
+ [
+ stack isEmpty ifTrue:[
+ ^ self
+ ].
+ nextNode := stack pop.
+ aBlock value:nextNode.
+ nextNode := nextNode rightSubtree.
+ ] doWhile:[nextNode isNil]
+ ] ifFalse:[
+ nextNode := left.
+ ].
+ ] loop.
+
+ "
+ BinaryTree withAll:#(2 16 3 1 0 4 7 9)
+ "
+!
+
+postOrderDo: aBlock
+ "Traverses the elements of the binary tree in
+ LEFT - RIGHT - ROOT order,
+ applying a block to each node"
+
+ leftSubtree notNil ifTrue:[
+ leftSubtree postOrderDo: aBlock
+ ].
+ rightSubtree notNil ifTrue:[
+ rightSubtree postOrderDo: aBlock
+ ].
+
+ aBlock value: self.
+!
+
+preOrderDo: aBlock
+ "Traverses the elements of the binary tree in
+ ROOT - LEFT - RIGHT order,
+ applying a block to each node"
+
+ aBlock value: self.
+
+ leftSubtree notNil ifTrue:[
+ leftSubtree preOrderDo: aBlock
+ ].
+ rightSubtree notNil ifTrue:[
+ rightSubtree preOrderDo: aBlock
+ ].
+! !
+
+!BinaryTreeNode methodsFor:'insert & delete'!
+
+insert:aBinaryTreeNode
+ "insert a node, comparing nodes using a default sort rule"
+
+ ^ self
+ insert:aBinaryTreeNode
+ sortBlock:[:a :b | a < b]
+
+ "Modified: 10.5.1996 / 15:08:30 / cg"
+ "Created: 10.5.1996 / 15:09:44 / cg"
+!
+
+insert:newBinaryTreeNode sortBlock:sortBlock
+ "insert a node, comparing nodes using sortBlock"
+
+ |node newValue left right|
+
+ "/ the following might be ugly - however, it it slightly faster than the stuff below.
+ "/ AND it does not suffer stack exhaustion....
+ "/ (we MUST have LCO in smalltalk for this to be automatically faster
+
+ node := self.
+ newValue := newBinaryTreeNode data.
+ [true] whileTrue:[
+ "newValue is less the node data"
+ (sortBlock value:newValue value:node data) ifTrue:[
+ left := node leftSubtree.
+ left isNil ifTrue:[
+ node leftSubtree:newBinaryTreeNode.
+ ^ self
+ ].
+ node := left
+ ] ifFalse:[
+ "newValue is larger or equal than node data"
+ right := node rightSubtree.
+ "if right data is less than node, we would be jumping back..."
+ right isNil ifTrue:[
+ node rightSubtree:newBinaryTreeNode.
+ ^ self
+ ].
+ node := right
+ ]
+ ].
+ "not reached"
+
+"/ (sortBlock value:newBinaryTreeNode data value:data) ifTrue:[
+"/ leftSubtree isNil ifTrue:[
+"/ leftSubtree := newBinaryTreeNode.
+"/ ] ifFalse:[
+"/ leftSubtree insert:newBinaryTreeNode sortBlock:sortBlock
+"/ ]
+"/ ] ifFalse:[
+"/ rightSubtree isNil ifTrue:[
+"/ rightSubtree := newBinaryTreeNode.
+"/ ] ifFalse:[
+"/ rightSubtree insert:newBinaryTreeNode sortBlock:sortBlock
+"/ ]
+"/ ]
+
+ "
+ BinaryTree withAll:#(16 3 1 0 4 7 9)
+ "
+! !
+
+!BinaryTreeNode methodsFor:'printing'!
+
+printOn: aStream
+ "Append the ascii representation to aStream"
+
+ data isNil
+ ifTrue: [aStream nextPutAll: '--']
+ ifFalse: [
+ aStream nextPut: $(.
+ data printOn: aStream. aStream nextPut: $ .
+ leftSubtree printOn: aStream. aStream nextPut: $ .
+ rightSubtree printOn: aStream.
+ aStream nextPut: $)]
+!
+
+printOn:aStream indent:i
+ "Append the graphical ascii representation to aStream"
+
+ data isNil
+ ifTrue: [aStream spaces:i. aStream nextPutAll: '--']
+ ifFalse: [
+ aStream spaces:i. aStream nextPut: $(.
+ data printOn: aStream.
+ aStream cr.
+ leftSubtree isNil
+ ifTrue:[ aStream spaces:i+2. '--' printOn: aStream]
+ ifFalse:[ leftSubtree printOn: aStream indent:i+2 ].
+ aStream cr.
+ rightSubtree isNil
+ ifTrue:[ aStream spaces:i+2. '--' printOn: aStream]
+ ifFalse:[ rightSubtree printOn: aStream indent:i+2 ].
+ aStream nextPut: $)
+ ]
+! !
+
+!BinaryTreeNode methodsFor:'private helpers'!
+
+removeLeftRightMostNode
+ |rightMost|
+
+ leftSubtree rightSubtree isNil ifTrue:[
+ rightMost := leftSubtree.
+ leftSubtree := leftSubtree leftSubtree.
+ ^ rightMost.
+ ].
+
+ ^ leftSubtree removeRightMostNode
+
+ "
+ |tree|
+
+ tree := BinaryTreeNode data:4.
+ #(2 6 1 3 5 7)
+ do:[:word |
+ tree insert:(BinaryTreeNode data:word).
+ ].
+ tree printOn:Transcript indent:0. Transcript cr.
+ '---------------------------' printOn:Transcript. Transcript cr.
+ tree removeLeftRightMostNode.
+ tree printOn:Transcript indent:0. Transcript cr.
+ "
+!
+
+removeRightMostNode
+ |right rr parent|
+
+ rightSubtree isNil ifTrue:[
+ self error:'should not happen'
+ ].
+
+ parent := self.
+ right := rightSubtree.
+ [ (rr := right rightSubtree) notNil ] whileTrue:[
+ parent := right.
+ right := rr.
+ ].
+ parent rightSubtree:(right leftSubtree).
+ ^ right.
+
+ "
+ |tree|
+
+ tree := BinaryTreeNode data:4.
+ #(2 6 1 3 5 7)
+ do:[:word |
+ tree insert:(BinaryTreeNode data:word).
+ ].
+ Transcript showCR:tree.
+ Transcript showCR:(tree removeLeftRightMostNode).
+ Transcript showCR:tree.
+ "
+!
+
+removeValue:oldValue using:compareOp sortBlock:sortBlock
+ "remove a value - returns a new treeNode, or nil if the value is not in the tree"
+
+ |thisIsMyNode newTop newLeft newRight|
+
+ "/ speed hack - avoids message sends (and also better inline caching)
+ compareOp == #== ifTrue:[
+ thisIsMyNode := (data == oldValue).
+ ] ifFalse:[
+ compareOp == #= ifTrue:[
+ thisIsMyNode := (data = oldValue).
+ ] ifFalse:[
+ thisIsMyNode := data perform:compareOp with:oldValue.
+ ].
+ ].
+
+ thisIsMyNode ifTrue:[
+ leftSubtree isNil ifTrue:[
+ ^ rightSubtree
+ ].
+ rightSubtree isNil ifTrue:[
+ ^ leftSubtree
+ ].
+ newTop := self removeLeftRightMostNode.
+ newTop leftSubtree:leftSubtree.
+ newTop rightSubtree:rightSubtree.
+ ^ newTop.
+ ].
+
+ (sortBlock value:oldValue value:data) ifTrue:[
+ "/ the value should be in the left part.
+ leftSubtree isNil ifTrue:[
+ ^ nil
+ ].
+ newLeft := leftSubtree removeValue:oldValue using:compareOp sortBlock:sortBlock.
+ newLeft isNil ifTrue:[
+ (leftSubtree data perform:compareOp with:oldValue) ifFalse:[
+ ^ nil
+ ].
+ ].
+ leftSubtree := newLeft.
+ ] ifFalse:[
+ "/ the value should be in the right part.
+ rightSubtree isNil ifTrue:[
+ ^ nil
+ ].
+ newRight := rightSubtree removeValue:oldValue using:compareOp sortBlock:sortBlock.
+ newRight isNil ifTrue:[
+ (rightSubtree data perform:compareOp with:oldValue) ifFalse:[
+ ^ nil
+ ].
+ ].
+ rightSubtree := newRight.
+ ].
+ ^ self.
+! !
+
+!BinaryTreeNode methodsFor:'queries'!
+
+depth
+ "Returns the depth of the binary tree (0 for leafs)"
+
+ ^ self level - 1.
+!
+
+getTreeWithAnInteger: anInteger
+ "Private - Returns the BinaryTree with data anInteger.
+ If anInteger not in the tree it returns nil."
+
+ self inOrderDo: [:each| each data = anInteger ifTrue:[^each]].
+ ^nil.
+!
+
+inOrderSuccessor
+ "Returns the in-order successor the of receiver.
+ (that is the leftMost node on the right side)
+ If receiver is empty then returns the receiver."
+
+ rightSubtree isNil ifTrue:[^ self].
+ ^ rightSubtree leftMostNode
+!
+
+includesIdenticalValue:aValue sortBlock:sortBlock
+ "return true, if aValue is contained as some node's data"
+
+ data == aValue ifTrue:[ ^ true ].
+ (sortBlock value:aValue value:data) ifTrue:[
+ leftSubtree isNil ifTrue:[
+ ^ false
+ ].
+ ^ leftSubtree includesIdenticalValue:aValue sortBlock:sortBlock.
+ ].
+ rightSubtree isNil ifTrue:[
+ ^ false
+ ].
+ ^ rightSubtree includesIdenticalValue:aValue sortBlock:sortBlock.
+!
+
+includesValue:aValue sortBlock:sortBlock
+ "return true, if some node's data is equal to aValue"
+
+ data = aValue ifTrue:[ ^ true ].
+
+ (sortBlock value:aValue value:data) ifTrue:[
+ leftSubtree isNil ifTrue:[
+ ^ false
+ ].
+ ^ leftSubtree includesValue:aValue sortBlock:sortBlock.
+ ].
+ rightSubtree isNil ifTrue:[
+ ^ false
+ ].
+ ^ rightSubtree includesValue:aValue sortBlock:sortBlock.
+!
+
+isEmpty
+ "returns true if the binary tree is empty and false otherwise"
+
+ ^ data isNil
+!
+
+isLeaf
+ "Returns true if self is a leaf"
+
+ ^ ((leftSubtree isNil) and: [rightSubtree isNil])
+!
+
+leftMostNode
+ "Returns the leftMost (smallest-valued) node"
+
+ leftSubtree isNil ifTrue:[^ self].
+ ^ leftSubtree leftMostNode
+!
+
+level
+ "Returns the level of the binary tree (1 for leafs)"
+
+ |l|
+
+ l := 0.
+ leftSubtree notNil ifTrue:[
+ l := leftSubtree level
+ ].
+ rightSubtree notNil ifTrue:[
+ l := l max:(rightSubtree level)
+ ].
+ ^ l + 1
+!
+
+rightMostNode
+ "Returns the rightMost (largest-valued) node"
+
+ rightSubtree isNil ifTrue:[^ self].
+ ^ rightSubtree rightMostNode
+!
+
+size
+ "Returns the size of the binary tree"
+
+ ^ 1
+ + (leftSubtree isNil ifTrue: [0] ifFalse:[leftSubtree size])
+ + (rightSubtree isNil ifTrue: [0] ifFalse:[rightSubtree size])
+! !
+
+!BinaryTreeNode class methodsFor:'documentation'!
+
+version
+ ^ '$Header: /cvs/stx/stx/libbasic2/BinaryTreeNode.st,v 1.6 2012-08-05 16:49:40 cg Exp $'
+!
+
+version_CVS
+ ^ '$Header: /cvs/stx/stx/libbasic2/BinaryTreeNode.st,v 1.6 2012-08-05 16:49:40 cg Exp $'
+! !