Class: BinaryTreeNode

• Inheritance
• Description
• Class protocol
  • instance creation
• Instance protocol
  • accessing
  • enumeration
  • insert & delete
  • printing
  • private helpers
  • queries
• Examples

Inheritance:

   Object
   |
   +--BinaryTreeNode
      |
      +--AATreeNode

Package:

stx:libbasic2

Category:

Collections-Ordered-Trees

Version:

rev: 1.11 date: 2021/01/20 12:59:21

user: cg

file: BinaryTreeNode.st directory: libbasic2

module: stx stc-classLibrary: libbasic2

Description:

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

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.

Class protocol:

 data: data

Returns a new binary tree node, holding data

 empty

Returns a new binary tree with subtrees as binary tree nodes

Instance protocol:

 data

 data: anObject

 leftSubtree

 leftSubtree: aBinaryTree

 nextNodeInOrder

return the node holding the next value

 predecessor

return the previous value

 prevNodeInOrder

return the node holding the previous value

 rightSubtree

 rightSubtree: aBinaryTree

 successor

return the next value

 do: aBlock

applies aBlock to each element's data in the binary tree in inorder

 inOrderDo: aBlock

Traverses the elements of the binary tree in
LEFT - ROOT - RIGHT order,
applying a block to each node.

We use an iterative approach here, to avoid VM stack overflow

 postOrderDo: aBlock

Traverses the elements of the binary tree in
LEFT - RIGHT - ROOT order,
applying a block to each node

 preOrderDo: aBlock

Traverses the elements of the binary tree in
ROOT - LEFT - RIGHT order,
applying a block to each node

 insert: aBinaryTreeNode

insert a node, comparing nodes using a default sort rule

** This is an obsolete interface - do not use it (it may vanish in future versions) **

 insert: newBinaryTreeNode sortBlock: sortBlock

insert a node, comparing nodes using sortBlock

** This is an obsolete interface - do not use it (it may vanish in future versions) **

 insertNode: aBinaryTreeNode

insert a node, comparing nodes using a default sort rule

 insertNode: newBinaryTreeNode sortBlock: sortBlock

insert a node, comparing nodes using sortBlock

Usage example(s):

leftSubtree insertNode:newBinaryTreeNode sortBlock:sortBlock

Usage example(s):

rightSubtree insertNode:newBinaryTreeNode sortBlock:sortBlock

 printDataOn: aStream

 printOn: aStream

Append the ascii representation to aStream

 printOn: aStream indent: i

Append the graphical ascii representation to aStream

 removeLeftMostNode

 removeLeftRightMostNode

|tree|

tree := BinaryTreeNode data:4.
#(2 6 1 3 5 7)
do:[:word |
tree insertNode:(BinaryTreeNode data:word).
].
tree printOn:Transcript indent:0. Transcript cr.
'---------------------------' printOn:Transcript. Transcript cr.
Transcript showCR:tree removeLeftRightMostNode.
tree printOn:Transcript indent:0. Transcript cr.

 removeRightLeftMostNode

|tree|

tree := BinaryTreeNode data:4.
#(2 6 1 3 5 7)
do:[:word |
tree insertNode:(BinaryTreeNode data:word).
].
tree printOn:Transcript indent:0. Transcript cr.
'---------------------------' printOn:Transcript. Transcript cr.
Transcript showCR:tree removeRightLeftMostNode.
tree printOn:Transcript indent:0. Transcript cr.

 removeRightMostNode

|tree|

tree := BinaryTreeNode data:4.
#(2 6 1 3 5 7)
do:[:word |
tree insertNode:(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

 depth

Returns the depth of the binary tree (0 for leafs)

 getTreeWithAnInteger: anInteger

Private - Returns the BinaryTree with data anInteger.
If anInteger not in the tree it returns 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.

 includesIdenticalValue: aValue sortBlock: sortBlock

return true, if aValue is contained as some node's data

 includesValue: aValue sortBlock: sortBlock

return true, if some node's data is equal to aValue

 isEmpty

returns true if the binary tree is empty and false otherwise

 isLeaf

Returns true if self is a leaf

 leftMostNode

Returns the leftMost (smallest-valued) node

 level

Returns the level of the binary tree (1 for leafs)

 rightMostNode

Returns the rightMost (largest-valued) node

 size

Returns the size of the binary tree

Examples:

  |tree|

  tree := BinaryTreeNode data:2.
  tree leftSubtree:(BinaryTreeNode new data:1).
  tree rightSubtree:(BinaryTreeNode new data:3).
  tree printOn:Transcript.

  |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
  ]