structure
Class BinaryTree<ELTTYPE>

java.lang.Object
  structure.BinaryTree<ELTTYPE>

public class BinaryTree<ELTTYPE>
extends java.lang.Object

This class implements a single node of a binary tree. It is a recursive structure. Relationships between nodes are doubly linked, with parent and child references. Many characteristics of trees may be detected with static methods.

See Also:

BinaryTree, BinarySearchTree

Field Summary

static BinaryTree

EMPTY The unique empty node

Constructor Summary

BinaryTree(ELTTYPE value)
Constructs a tree node with no children.

BinaryTree(ELTTYPE value, BinaryTree<ELTTYPE> left, BinaryTree<ELTTYPE> right)
Constructs a tree node with no children.

Method Summary

int	depth() Compute the depth of a node.
int	hashCode()
int	height() Returns height of node in tree.
AbstractIterator<ELTTYPE>	inorderIterator() Return an iterator to traverse the elements of subtree in-order
boolean	isBalanced() Return true iff the tree is height balanced.
boolean	isComplete() Return whether tree is complete.
boolean	isEmpty() Returns true if tree is empty.
boolean	isFull() Returns true if tree is full.
boolean	isLeftChild() Determine if this node is a left child
boolean	isRightChild() Determine if this node is a right child
java.util.Iterator<ELTTYPE>	iterator() Generate an in-order iterator of subtree
BinaryTree<ELTTYPE>	left() Get left subtree of current node
AbstractIterator<ELTTYPE>	levelorderIterator() Method to return a level-order iterator of subtree
BinaryTree<ELTTYPE>	parent() Get reference to parent of this node
AbstractIterator<ELTTYPE>	postorderIterator() Return an iterator to traverse the elements of subtree in post-order
AbstractIterator<ELTTYPE>	preorderIterator() Return an iterator to traverse nodes of subtree in-order
BinaryTree<ELTTYPE>	right() Get right subtree of current node
BinaryTree<ELTTYPE>	root() Returns reference to root of tree containing n
void	setLeft(BinaryTree<ELTTYPE> newLeft) Update the left subtree of this node.
void	setRight(BinaryTree<ELTTYPE> newRight) Update the right subtree of this node.
void	setValue(ELTTYPE value) Set's value associated with this node
int	size() Returns the number of descendants of node
java.lang.String	toString() Returns a representation the subtree rooted at this node
java.lang.String	treeString() Returns a string representing the tree rooted at this node.
ELTTYPE	value() Returns value associated with this node

Methods inherited from class java.lang.Object

equals, getClass, notify, notifyAll, wait, wait, wait

Field Detail

EMPTY

public static final BinaryTree EMPTY

The unique empty node

Constructor Detail

BinaryTree

public BinaryTree(ELTTYPE value)

Constructs a tree node with no children. Value of the node is provided by the user

Parameters:

value - A (possibly null) value to be referenced by node

Post:

Returns a tree referencing value with two null subtrees

BinaryTree

public BinaryTree(ELTTYPE value,
                  BinaryTree<ELTTYPE> left,
                  BinaryTree<ELTTYPE> right)

Constructs a tree node with no children. Value of the node and subtrees are provided by the user

Parameters:

value - A (possibly null) value to be referenced by node

left - The subtree to be left subtree of node

right - The subtree to be right subtree of node

Post:

Returns a tree referencing value and subtree

Method Detail

left

public BinaryTree<ELTTYPE> left()

Get left subtree of current node

Returns:

The left subtree of this node

Post:

Returns reference to left subtree, or null

right

public BinaryTree<ELTTYPE> right()

Get right subtree of current node

Returns:

The right subtree of this node

Post:

Returns reference to right subtree, or null

parent

public BinaryTree<ELTTYPE> parent()

Get reference to parent of this node

Returns:

Reference to parent of this node

Post:

Returns reference to parent node, or null

setLeft

public void setLeft(BinaryTree<ELTTYPE> newLeft)

Update the left subtree of this node. Parent of the left subtree is updated consistently. Existing subtree is detached

Parameters:

newLeft - The root of the new left subtree

Post:

Sets left subtree to newLeft re-parents newLeft if not null

setRight

public void setRight(BinaryTree<ELTTYPE> newRight)

Update the right subtree of this node. Parent of the right subtree is updated consistently. Existing subtree is detached

Parameters:

newRight - A reference to the new right subtree of this node

Post:

Sets left subtree to newRight re-parents newRight if not null

size

public int size()

Returns the number of descendants of node

Returns:

Size of subtree

Post:

Returns the size of the subtree

root

public BinaryTree<ELTTYPE> root()

Returns reference to root of tree containing n

Returns:

Root of tree

Post:

Returns the root of the tree node n

height

public int height()

Returns height of node in tree. Height is maximum path length to descendant

Returns:

The height of the node in the tree

Post:

Returns the height of a node in its tree

depth

public int depth()

Compute the depth of a node. The depth is the path length from node to root

Returns:

The path length to root of tree

Post:

Returns the depth of a node in the tree

isFull

public boolean isFull()

Returns true if tree is full. A tree is full if adding a node to tree would necessarily increase its height

Returns:

True iff tree is full

Post:

Returns true iff the tree rooted at node is full

isEmpty

public boolean isEmpty()

Returns true if tree is empty.

Returns:

True iff tree is empty

Post:

Returns true iff the tree rooted at node is empty

isComplete

public boolean isComplete()

Return whether tree is complete. A complete tree has minimal height and any holes in tree would appear in last level to right.

Returns:

True iff the subtree is complete

Post:

Returns true iff the tree rooted at node is complete

isBalanced

public boolean isBalanced()

Return true iff the tree is height balanced. A tree is height balanced iff at every node the difference in heights of subtrees is no greater than one

Returns:

True if tree is height balanced

Post:

Returns true iff the tree rooted at node is balanced

iterator

public java.util.Iterator<ELTTYPE> iterator()

Generate an in-order iterator of subtree

Returns:

In-order iterator on subtree rooted at this

Post:

Returns an in-order iterator of the elements

preorderIterator

public AbstractIterator<ELTTYPE> preorderIterator()

Return an iterator to traverse nodes of subtree in-order

Returns:

AbstractIterator to traverse subtree

Post:

The elements of the binary tree rooted at node are traversed in preorder

inorderIterator

public AbstractIterator<ELTTYPE> inorderIterator()

Return an iterator to traverse the elements of subtree in-order

Returns:

An in-order iterator over descendants of node

Post:

The elements of the binary tree rooted at node node are traversed in inorder

postorderIterator

public AbstractIterator<ELTTYPE> postorderIterator()

Return an iterator to traverse the elements of subtree in post-order

Returns:

An iterator that traverses descendants of node in postorder

Pre:

None

Post:

The elements of the binary tree rooted at node node are traversed in postorder

levelorderIterator

public AbstractIterator<ELTTYPE> levelorderIterator()

Method to return a level-order iterator of subtree

Returns:

An iterator to traverse subtree in level-order

Pre:

None

Post:

The elements of the binary tree rooted at node node are traversed in levelorder

isLeftChild

public boolean isLeftChild()

Determine if this node is a left child

Returns:

True iff this node is a left child of parent

Post:

Returns true if this is a left child of parent

isRightChild

public boolean isRightChild()

Determine if this node is a right child

Returns:

True iff this node is a right child of parent

Post:

Returns true if this is a right child of parent

value

public ELTTYPE value()

Returns value associated with this node

Returns:

The node's value

Post:

Returns value associated with this node

setValue

public void setValue(ELTTYPE value)

Set's value associated with this node

Parameters:

value - The new value of this node

Post:

Sets the value associated with this node

hashCode

public int hashCode()

Overrides:

hashCode in class java.lang.Object

Post:

return sum of hashcodes of the contained values

treeString

public java.lang.String treeString()

Returns a string representing the tree rooted at this node. WARNING this can be a very long string.

Returns:

A string representing the tree rooted at this node.

toString

public java.lang.String toString()

Returns a representation the subtree rooted at this node

Overrides:

toString in class java.lang.Object

Returns:

String representing this subtree

Post:

Returns string representation