Package components.binarytree
Class BinaryTree1<T>
java.lang.Object
components.binarytree.BinaryTreeSecondary<T>
components.binarytree.BinaryTree1<T>
- Type Parameters:
T
- type ofBinaryTree
labels
- All Implemented Interfaces:
BinaryTree<T>
,BinaryTreeKernel<T>
,Standard<BinaryTree<T>>
,Iterable<T>
BinaryTree
represented as a recursive data structure, done
"bare-handed", with implementations of primary methods.
Execution-time performance of all methods implemented in this class is O(1).
- Mathematical Subtypes:
TREE_REP is ( size: integer, height: integer, rootLabel: T, leftSubtree: TREE_REP, rightSubtree: TREE_REP )
- Mathematical Definitions:
IS_LEGAL_REP ( tr: TREE_REP ): boolean is 0 <= tr.height <= tr.size <= (2^tr.height - 1) and (if tr.size > 0 then tr.size = 1 + tr.leftSubtree.size + tr.rightSubtree.size and tr.height = 1 + max(tr.leftSubtree.height, tr.rightSubtree.height) and [tr.rootLabel is not null] and [tr.leftSubtree is not null] and [tr.rightSubtree is not null] and [tr.leftSubtree and tr.rightSubtree are not aliases] and IS_LEGAL_REP(tr.leftSubtree) and IS_LEGAL_REP(tr.rightSubtree)) ABSTRACT_TREE ( tr: TREE_REP ): binary tree of T satisfies if IS_LEGAL_REP(tr) then (if tr.size = 0 then ABSTRACT_TREE(tr) = empty_tree else ABSTRACT_TREE(tr) = compose(tr.rootLabel, ABSTRACT_TREE(tr.leftSubtree), ABSTRACT_TREE(tr.rightSubtree)))
- Representation Invariant (concrete invariant of $this):
IS_LEGAL_REP($this)
- Abstraction Relation (interpretation mapping between $this and this):
this = ABSTRACT_TREE($this)
-
Constructor Summary
-
Method Summary
Modifier and TypeMethodDescriptionfinal void
assemble
(T root, BinaryTree<T> left, BinaryTree<T> right) Assembles inthis
a tree with root labelroot
and subtreesleft
andright
; the declaration notwithstanding, the dynamic type ofleft
andright
must be the same as the dynamic type ofthis
.final void
clear()
Resetsthis
to an initial value.final T
disassemble
(BinaryTree<T> left, BinaryTree<T> right) Disassemblesthis
into its root label, which is returned as the value of the function, and subtreesleft
andright
; the declaration notwithstanding, the dynamic type ofleft
andright
must be the same as the dynamic type ofthis
.final int
height()
Reports the height ofthis
.iterator()
final BinaryTree<T>
Returns a new object with the same dynamic type asthis
, having an initial value.final T
replaceRoot
(T x) Replaces the root ofthis
withx
, and returns the old root.final T
root()
Reports the root ofthis
.final int
size()
Reports the size ofthis
.final void
transferFrom
(BinaryTree<T> source) Setsthis
to the incoming value ofsource
, and resetssource
to an initial value; the declaration notwithstanding, the dynamic type ofsource
must be the same as the dynamic type ofthis
.Methods inherited from class components.binarytree.BinaryTreeSecondary
equals, hashCode, inOrderAssemble, toString
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.lang.Iterable
forEach, spliterator
-
Constructor Details
-
BinaryTree1
public BinaryTree1()No-argument constructor.
-
-
Method Details
-
newInstance
Description copied from interface:Standard
Returns a new object with the same dynamic type asthis
, having an initial value. If the typeT
has a no-argument constructor, then the value of the new returned object satisfies the contract of the no-argument constructor forT
. IfT
does not have a no-argument constructor, then the value of the new returned object satisfies the contract of the constructor call that was used to initializethis
.- Returns:
- new object "like"
this
with an initial value
-
clear
Description copied from interface:Standard
Resetsthis
to an initial value. If the typeT
has a no-argument constructor, thenthis
satisfies the contract of the no-argument constructor forT
. IfT
does not have a no-argument constructor, thenthis
satisfies the contract of the constructor call that was used to initialize#this
. -
transferFrom
Description copied from interface:Standard
Setsthis
to the incoming value ofsource
, and resetssource
to an initial value; the declaration notwithstanding, the dynamic type ofsource
must be the same as the dynamic type ofthis
. If the typeT
has a no-argument constructor, thensource
satisfies the contract of the no-argument constructor forT
. IfT
does not have a no-argument constructor, thensource
satisfies the contract of the constructor call that was used to initialize#source
.- Parameters:
source
- object whose value is to be transferred
-
assemble
Description copied from interface:BinaryTreeKernel
Assembles inthis
a tree with root labelroot
and subtreesleft
andright
; the declaration notwithstanding, the dynamic type ofleft
andright
must be the same as the dynamic type ofthis
.- Parameters:
root
- the root labelleft
- the left subtreeright
- the right subtree
-
disassemble
Description copied from interface:BinaryTreeKernel
Disassemblesthis
into its root label, which is returned as the value of the function, and subtreesleft
andright
; the declaration notwithstanding, the dynamic type ofleft
andright
must be the same as the dynamic type ofthis
.- Parameters:
left
- the left subtreeright
- the right subtree- Returns:
- the root label
-
size
Description copied from interface:BinaryTreeKernel
Reports the size ofthis
.- Returns:
- the size
-
iterator
-
root
Description copied from interface:BinaryTree
Reports the root ofthis
.- Specified by:
root
in interfaceBinaryTree<T>
- Overrides:
root
in classBinaryTreeSecondary<T>
- Returns:
- the root entry of
this
-
replaceRoot
Description copied from interface:BinaryTree
Replaces the root ofthis
withx
, and returns the old root.- Specified by:
replaceRoot
in interfaceBinaryTree<T>
- Overrides:
replaceRoot
in classBinaryTreeSecondary<T>
- Parameters:
x
- the new root- Returns:
- the old root
-
height
Description copied from interface:BinaryTree
Reports the height ofthis
.- Specified by:
height
in interfaceBinaryTree<T>
- Overrides:
height
in classBinaryTreeSecondary<T>
- Returns:
- the height
-