FlexOr.container
Class BinaryTree

java.lang.Object
  FlexOr.container.BinaryTree

All Implemented Interfaces:

Container, java.lang.Cloneable

Direct Known Subclasses:

OrderedBinaryTree

public abstract class BinaryTree
extends java.lang.Object
implements Container

Binary Tree is an abstract class implementing container. It is abstract because the following methods which depend upon different policies on node ordering.
-- add
-- contains
-- remove
-- clone -- needs a non abstract class to create an instance.

Version:

1.0 1999 Jan 15

Author:

Gunnar Gotshalks

Constructor Summary

BinaryTree()

Method Summary

abstract void	add(java.lang.Object obj) Adds obj at the default location.
abstract java.lang.Object	clone() Return a copy of the tree that points to the same objects as in the original tree.
boolean	contains(java.lang.Object obj) Determines whether an element is in the tree.
java.util.Enumeration<java.lang.Object>	elements() Returns an enumerator using inorder traversal -- left subtree first.
boolean	equals(java.lang.Object container) Check for equality of contents of two containers.
java.util.Enumeration<java.lang.Object>	inOrderLRtraversal() Return an enumerator using inorder traversal -- left subtree first.
java.util.Enumeration<java.lang.Object>	inOrderRLtraversal() Return an enumerator using inorder traversal -- right subtree first.
boolean	isEmpty() Check if the container is empty.
boolean	isFull() Check if the container is full.
java.util.Enumeration<java.lang.Object>	levelOrderLRtraversal() Return an enumerator using levelorder traversal -- left subtree first.
java.util.Enumeration<java.lang.Object>	levelOrderRLtraversal() Return an enumerator using levelorder traversal -- right subtree first.
java.util.Enumeration<java.lang.Object>	postOrderLRtraversal() Return an enumerator using postorder traversal -- left subtree first.
java.util.Enumeration<java.lang.Object>	postOrderRLtraversal() Return an enumerator using postorder traversal -- right subtree first.
java.util.Enumeration<java.lang.Object>	preOrderLRtraversal() Return an enumerator using preorder traversal -- left subtree first.
java.util.Enumeration<java.lang.Object>	preOrderRLtraversal() Return an enumerator using preorder traversal -- right subtree first.
java.lang.Object	remove() Remove the first element based on an inorder traversal of the tree contents.
abstract boolean	remove(java.lang.Object obj) Remove the specified element.
void	removeAll() Empty the container.
int	size() Returns the number of elements in the container.
java.lang.String	toString() Return a string representation of the contents of the tree.

Methods inherited from class java.lang.Object

getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

BinaryTree

public BinaryTree()

Method Detail

contains

public boolean contains(java.lang.Object obj)

Determines whether an element is in the tree. Default uses the O(size) levelOrderLRtraversal to search the tree. Subclasses may want to override this method.

Requires: True
Ensures: contains(obj) => result = true
            not contains(obj) => result = false

Specified by:

contains in interface Container

isEmpty

public boolean isEmpty()

Check if the container is empty.

Requires: True
Ensures: isEmpty = (count = 0)

Specified by:

isEmpty in interface Container

isFull

public boolean isFull()

Check if the container is full. Binary trees cannot be full.

Requires: True
Ensures: isFull = false

Specified by:

isFull in interface Container

size

public int size()

Returns the number of elements in the container.

Requires: True
Ensures: result = size

Specified by:

size in interface Container

elements

public java.util.Enumeration<java.lang.Object> elements()

Returns an enumerator using inorder traversal -- left subtree first.

Specified by:

elements in interface Container

Throws:

java.util.NoSuchElementException - when nextElement is called with an empty enumeration sequence.

preOrderLRtraversal

public java.util.Enumeration<java.lang.Object> preOrderLRtraversal()

Return an enumerator using preorder traversal -- left subtree first.

Throws:

java.util.NoSuchElementException - when nextElement is called with an empty enumeration sequence.

preOrderRLtraversal

public java.util.Enumeration<java.lang.Object> preOrderRLtraversal()

Return an enumerator using preorder traversal -- right subtree first.

Throws:

java.util.NoSuchElementException - when nextElement is called with an empty enumeration sequence.

inOrderLRtraversal

public java.util.Enumeration<java.lang.Object> inOrderLRtraversal()

Return an enumerator using inorder traversal -- left subtree first.

Throws:

java.util.NoSuchElementException - when nextElement is called with an empty enumeration sequence.

inOrderRLtraversal

public java.util.Enumeration<java.lang.Object> inOrderRLtraversal()

Return an enumerator using inorder traversal -- right subtree first.

Throws:

java.util.NoSuchElementException - when nextElement is called with an empty enumeration sequence.

postOrderLRtraversal

public java.util.Enumeration<java.lang.Object> postOrderLRtraversal()

Return an enumerator using postorder traversal -- left subtree first.

Throws:

java.util.NoSuchElementException - when nextElement is called with an empty enumeration sequence.

postOrderRLtraversal

public java.util.Enumeration<java.lang.Object> postOrderRLtraversal()

Return an enumerator using postorder traversal -- right subtree first.

Throws:

java.util.NoSuchElementException - when nextElement is called with an empty enumeration sequence.

levelOrderLRtraversal

public java.util.Enumeration<java.lang.Object> levelOrderLRtraversal()

Return an enumerator using levelorder traversal -- left subtree first.

Throws:

java.util.NoSuchElementException - when nextElement is called with an empty enumeration sequence.

levelOrderRLtraversal

public java.util.Enumeration<java.lang.Object> levelOrderRLtraversal()

Return an enumerator using levelorder traversal -- right subtree first.

Throws:

java.util.NoSuchElementException - when nextElement is called with an empty enumeration sequence.

add

public abstract void add(java.lang.Object obj)

Adds obj at the default location.

Requires: True
Ensures: contains(obj) = true
                size = old size + 1

Specified by:

add in interface Container

Throws:

ContainerFullException - if container already contains MaxLength elements for finite size containers.

removeAll

public void removeAll()

Empty the container.

Requires: True
Ensures: size = 0

Specified by:

removeAll in interface Container

remove

public java.lang.Object remove()

Remove the first element based on an inorder traversal of the tree contents.

Requires: size >= 0
Ensures: size = old size - 1
                old inorderSequence = obj ^ inorderSequence

Specified by:

remove in interface Container

Throws:

ContainerEmptyException - if removing from an empty container.

remove

public abstract boolean remove(java.lang.Object obj)

Remove the specified element.

Requires: size >= 0
Ensures: 
    old binaryTree.contains(obj) =>
        binaryTree = old binaryTree / obj and result = true 
not old binaryTree.contains(obj) =>
        binaryTree = old binaryTree and result = false

Throws:

ContainerEmptyException - if removing from an empty container.

clone

public abstract java.lang.Object clone()

Return a copy of the tree that points to the same objects as in the original tree. Part way between a shallow and deep copy. This is equivalent to how a Vector is cloned.

Requires: True
Ensures: result = copy of BinaryTree

Specified by:

clone in interface Container

Overrides:

clone in class java.lang.Object

toString

public java.lang.String toString()

Return a string representation of the contents of the tree. Shows the structure.

Requires: true
Ensures: result = string representation of tree

Specified by:

toString in interface Container

Overrides:

toString in class java.lang.Object

equals

public boolean equals(java.lang.Object container)

Check for equality of contents of two containers. By equality we mean an equal sequence of elements as returned by an inorder traversal.

Requires: True
Ensures: result = true => container contents are equal
                result = false => container contents are not equal

Specified by:

equals in interface Container

Overrides:

equals in class java.lang.Object