structure
Class BinaryTree

java.lang.Object
  structure.BinaryTree

public class BinaryTree
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
protected BinaryTree	left The left child of this node, or EMPTY
protected BinaryTree	parent The parent of this node
protected BinaryTree	right The left child of this node, or EMPTY
protected java.lang.Object	val The value associated with this node

Constructor Summary

BinaryTree(java.lang.Object value)
Constructs a tree node with no children.

BinaryTree(java.lang.Object value, BinaryTree left, BinaryTree 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	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	iterator() Generate an in-order iterator of subtree
BinaryTree	left() Get left subtree of current node
AbstractIterator	levelorderIterator() Method to return a level-order iterator of subtree
BinaryTree	parent() Get reference to parent of this node
AbstractIterator	postorderIterator() Return an iterator to traverse the elements of subtree in post-order
AbstractIterator	preorderIterator() Return an iterator to traverse nodes of subtree in-order
BinaryTree	right() Get right subtree of current node
BinaryTree	root() Returns reference to root of tree containing n
protected void	rotateLeft() Method to perform a left rotation of tree about this node Node must have a right child.
protected void	rotateRight() Method to perform a right rotation of tree about this node Node must have a left child.
void	setLeft(BinaryTree newLeft) Update the left subtree of this node.
protected void	setParent(BinaryTree newParent) Update the parent of this node
void	setRight(BinaryTree newRight) Update the right subtree of this node.
void	setValue(java.lang.Object 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.Object	value() Returns value associated with this node

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

val

protected java.lang.Object val

The value associated with this node

parent

protected BinaryTree parent

The parent of this node

left

protected BinaryTree left

The left child of this node, or EMPTY

right

protected BinaryTree right

The left child of this node, or EMPTY

EMPTY

public static final BinaryTree EMPTY

The unique empty node

Constructor Detail

BinaryTree

public BinaryTree(java.lang.Object 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

Postcondition:

Returns a tree referencing value with two empty subtrees

BinaryTree

public BinaryTree(java.lang.Object value,
                  BinaryTree left,
                  BinaryTree 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

Postcondition:

Returns a tree referencing value and two subtrees

Method Detail

left

public BinaryTree left()

Get left subtree of current node

Returns:

The left subtree of this node

Postcondition:

Returns reference to (possibly empty) left subtree

right

public BinaryTree right()

Get right subtree of current node

Returns:

The right subtree of this node

Postcondition:

Returns reference to (possibly empty) right subtree

parent

public BinaryTree parent()

Get reference to parent of this node

Returns:

Reference to parent of this node

Postcondition:

Returns reference to parent node, or null

setLeft

public void setLeft(BinaryTree 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

Postcondition:

Sets left subtree to newLeft re-parents newLeft

setRight

public void setRight(BinaryTree 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

Postcondition:

Sets left subtree to newRight re-parents newRight

setParent

protected void setParent(BinaryTree newParent)

Update the parent of this node

Parameters:

newParent - A reference to the new parent of this node

Postcondition:

Re-parents this node to parent reference, or null

size

public int size()

Returns the number of descendants of node

Returns:

Size of subtree

Postcondition:

Returns the size of the subtree

root

public BinaryTree root()

Returns reference to root of tree containing n

Returns:

Root of tree

Postcondition:

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

Postcondition:

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

Postcondition:

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

Postcondition:

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

Postcondition:

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

Postcondition:

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

Postcondition:

Returns true iff the tree rooted at node is balanced

iterator

public java.util.Iterator iterator()

Generate an in-order iterator of subtree

Returns:

In-order iterator on subtree rooted at this

Postcondition:

Returns an in-order iterator of the elements

preorderIterator

public AbstractIterator preorderIterator()

Return an iterator to traverse nodes of subtree in-order

Returns:

AbstractIterator to traverse subtree

Postcondition:

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

inorderIterator

public AbstractIterator inorderIterator()

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

Returns:

An in-order iterator over descendants of node

Postcondition:

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

postorderIterator

public AbstractIterator postorderIterator()

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

Returns:

An iterator that traverses descendants of node in postorder

Precondition:

None

Postcondition:

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

levelorderIterator

public AbstractIterator levelorderIterator()

Method to return a level-order iterator of subtree

Returns:

An iterator to traverse subtree in level-order

Precondition:

None

Postcondition:

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

rotateRight

protected void rotateRight()

Method to perform a right rotation of tree about this node Node must have a left child. Relation between left child and node are reversed

Precondition:

This node has a left subtree

Postcondition:

Rotates local portion of tree so left child is root

rotateLeft

protected void rotateLeft()

Method to perform a left rotation of tree about this node Node must have a right child. Relation between right child and node are reversed

Precondition:

This node has a right subtree

Postcondition:

Rotates local portion of tree so right child is root

isLeftChild

public boolean isLeftChild()

Determine if this node is a left child

Returns:

True iff this node is a left child of parent

Postcondition:

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

Postcondition:

Returns true if this is a right child of parent

value

public java.lang.Object value()

Returns value associated with this node

Returns:

The node's value

Postcondition:

Returns value associated with this node

setValue

public void setValue(java.lang.Object value)

Set's value associated with this node

Parameters:

value - The new value of this node

Postcondition:

Sets the value associated with this node

hashCode

public int hashCode()

Overrides:

hashCode in class java.lang.Object

Postcondition:

return sum of hashcodes of the contained values

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

Postcondition:

Returns string representation