Package components.binarytree

Class BinaryTree1<T>

java.lang.Object
components.binarytree.BinaryTreeSecondary<T>
components.binarytree.BinaryTree1<T>
Type Parameters:
T - type of BinaryTree labels
All Implemented Interfaces:
BinaryTree<T>, BinaryTreeKernel<T>, Standard<BinaryTree<T>>, Iterable<T>
public class BinaryTree1<T> extends BinaryTreeSecondary<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

    Constructors
    Constructor
    Description
    BinaryTree1()
    No-argument constructor.

  • Method Summary

    Modifier and Type
    Method
    Description
    final void
    assemble(T root, BinaryTree<T> left, BinaryTree<T> right)
    Assembles in this a tree with root label root and subtrees left and right; the declaration notwithstanding, the dynamic type of left and right must be the same as the dynamic type of this.
    final void
    clear()
    Resets this to an initial value.
    final T
    disassemble(BinaryTree<T> left, BinaryTree<T> right)
    Disassembles this into its root label, which is returned as the value of the function, and subtrees left and right; the declaration notwithstanding, the dynamic type of left and right must be the same as the dynamic type of this .
    final int
    height()
    Reports the height of this.
    final Iterator<T>
    iterator()
     
    final BinaryTree<T>
    newInstance()
    Returns a new object with the same dynamic type as this, having an initial value.
    final T
    replaceRoot(T x)
    Replaces the root of this with x, and returns the old root.
    final T
    root()
    Reports the root of this.
    final int
    size()
    Reports the size of this.
    final void
    transferFrom(BinaryTree<T> source)
    Sets this to the incoming value of source, and resets source to an initial value; the declaration notwithstanding, the dynamic type of source must be the same as the dynamic type of this.

    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

      public final BinaryTree<T> newInstance()
      Description copied from interface: Standard
      Returns a new object with the same dynamic type as this, having an initial value. If the type T has a no-argument constructor, then the value of the new returned object satisfies the contract of the no-argument constructor for T. If T 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 initialize this .
      Returns:
      new object "like" this with an initial value

    • clear

      public final void clear()
      Description copied from interface: Standard
      Resets this to an initial value. If the type T has a no-argument constructor, then this satisfies the contract of the no-argument constructor for T. If T does not have a no-argument constructor, then this satisfies the contract of the constructor call that was used to initialize #this.

    • transferFrom

      public final void transferFrom(BinaryTree<T> source)
      Description copied from interface: Standard
      Sets this to the incoming value of source, and resets source to an initial value; the declaration notwithstanding, the dynamic type of source must be the same as the dynamic type of this. If the type T has a no-argument constructor, then source satisfies the contract of the no-argument constructor for T. If T does not have a no-argument constructor, then source satisfies the contract of the constructor call that was used to initialize #source.
      Parameters:
      source - object whose value is to be transferred

    • assemble

      public final void assemble(T root, BinaryTree<T> left, BinaryTree<T> right)
      Description copied from interface: BinaryTreeKernel
      Assembles in this a tree with root label root and subtrees left and right; the declaration notwithstanding, the dynamic type of left and right must be the same as the dynamic type of this.
      Parameters:
      root - the root label
      left - the left subtree
      right - the right subtree

    • disassemble

      public final T disassemble(BinaryTree<T> left, BinaryTree<T> right)
      Description copied from interface: BinaryTreeKernel
      Disassembles this into its root label, which is returned as the value of the function, and subtrees left and right; the declaration notwithstanding, the dynamic type of left and right must be the same as the dynamic type of this .
      Parameters:
      left - the left subtree
      right - the right subtree
      Returns:
      the root label

    • size

      public final int size()
      Description copied from interface: BinaryTreeKernel
      Reports the size of this.
      Returns:
      the size

    • iterator

      public final Iterator<T> iterator()

    • root

      public final T root()
      Description copied from interface: BinaryTree
      Reports the root of this.
      Specified by:
      root in interface BinaryTree<T>
      Overrides:
      root in class BinaryTreeSecondary<T>
      Returns:
      the root entry of this

    • replaceRoot

      public final T replaceRoot(T x)
      Description copied from interface: BinaryTree
      Replaces the root of this with x, and returns the old root.
      Specified by:
      replaceRoot in interface BinaryTree<T>
      Overrides:
      replaceRoot in class BinaryTreeSecondary<T>
      Parameters:
      x - the new root
      Returns:
      the old root

    • height

      public final int height()
      Description copied from interface: BinaryTree
      Reports the height of this.
      Specified by:
      height in interface BinaryTree<T>
      Overrides:
      height in class BinaryTreeSecondary<T>
      Returns:
      the height