eXept Software AG Logo

Smalltalk/X Webserver

Documentation of class 'BinaryTreeNode':

Home

Documentation
www.exept.de
Everywhere
for:
[back]

Class: BinaryTreeNode


Inheritance:

   Object
   |
   +--BinaryTreeNode
      |
      +--AATreeNode

Package:
stx:libbasic2
Category:
Collections-Ordered-Trees
Version:
rev: 1.10 date: 2017/02/02 20:15:17
user: mawalch
file: BinaryTreeNode.st directory: libbasic2
module: stx stc-classLibrary: libbasic2
Author:
al938@FreeNet.Carleton.CA (Steve Chepurny)

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


Related information:

    LinkedList
    Chain
    Link
    ValueLink
    ChainLink

Class protocol:

instance creation
o  data: data
Returns a new binary tree node, holding data

o  empty
Returns a new binary tree with subtrees as binary tree nodes


Instance protocol:

accessing
o  data

o  data: anObject

o  leftSubtree

o  leftSubtree: aBinaryTree

o  nextNodeInOrder
return the node holding the next value

o  predecessor
return the previous value

o  prevNodeInOrder
return the node holding the previous value

o  rightSubtree

o  rightSubtree: aBinaryTree

o  successor
return the next value

enumeration
o  do: aBlock
applies aBlock to each element's data in the binary tree in inorder

o  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

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

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

insert & delete
o  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) **

o  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) **

o  insertNode: aBinaryTreeNode
insert a node, comparing nodes using a default sort rule

o  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

printing
o  printDataOn: aStream

o  printOn: aStream
Append the ascii representation to aStream

o  printOn: aStream indent: i
Append the graphical ascii representation to aStream

private helpers
o  removeLeftMostNode

o  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.

o  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.

o  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.

o  removeValue: oldValue using: compareOp sortBlock: sortBlock
remove a value - returns a new treeNode, or nil if the value is not in the tree

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

o  getTreeWithAnInteger: anInteger
Private - Returns the BinaryTree with data anInteger.
If anInteger not in the tree it returns nil.

o  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.

o  includesIdenticalValue: aValue sortBlock: sortBlock
return true, if aValue is contained as some node's data

o  includesValue: aValue sortBlock: sortBlock
return true, if some node's data is equal to aValue

o  isEmpty
returns true if the binary tree is empty and false otherwise

o  isLeaf
Returns true if self is a leaf

o  leftMostNode
Returns the leftMost (smallest-valued) node

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

o  rightMostNode
Returns the rightMost (largest-valued) node

o  size
Returns the size of the binary tree


Examples:


manual building of a tree (but see BinaryTree for a collection-facade):
  |tree|

  tree := BinaryTreeNode data:2.
  tree leftSubtree:(BinaryTreeNode new data:1).
  tree rightSubtree:(BinaryTreeNode new data:3).
  tree printOn:Transcript.
insertion:
  |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
  ]


ST/X 7.1.0.0; WebServer 1.663 at exept.de:8081; Thu, 19 Jul 2018 06:03:50 GMT