structure
Class BinaryTree

java.lang.Object
  |
  +--structure.BinaryTree

public class BinaryTree

extends 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 Object	val The value associated with this node

Constructor Summary

private	BinaryTree() A one-time constructor, for constructing empty trees.
	BinaryTree(Object value) Constructs a tree node with no children.
	BinaryTree(Object value, BinaryTree left, BinaryTree right) Constructs a tree node with no children.

Method Summary

int	depth() Compute the depth of a node.
private String	getHand() Support method for toString().
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
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(Object value) Set's value associated with this node
int	size() Returns the number of descendants of node
String	toString() Returns a representation the subtree rooted at this node
String	treeString() Returns a string representing the tree rooted at this node.
Object	value() Returns value associated with this node

Methods inherited from class java.lang.Object

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

Field Detail

val

protected 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

private BinaryTree()

A one-time constructor, for constructing empty trees.

BinaryTree

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

BinaryTree

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

Method Detail

left

public BinaryTree left()

Get left subtree of current node

Postcondition:

Returns reference to left subtree, or null

Returns:

The left subtree of this node

right

public BinaryTree right()

Get right subtree of current node

Postcondition:

Returns reference to right subtree, or null

Returns:

The right subtree of this node

parent

public BinaryTree parent()

Get reference to parent of this node

Postcondition:

Returns reference to parent node, or null

Returns:

Reference to parent of this node

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 if not null

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 if not null

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

Postcondition:

Returns the size of the subtree

Returns:

Size of subtree

root

public BinaryTree root()

Returns reference to root of tree containing n

Postcondition:

Returns the root of the tree node n

Returns:

Root of tree

height

public int height()

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

Postcondition:

Returns the height of a node in its tree

Returns:

The height of the node in the tree

depth

public int depth()

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

Postcondition:

Returns the depth of a node in the tree

Returns:

The path length to root of 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

Postcondition:

Returns true iff the tree rooted at node is full

Returns:

True iff tree is full

isEmpty

public boolean isEmpty()

Returns true if tree is empty.

Postcondition:

Returns true iff the tree rooted at node is empty

Returns:

True iff tree 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.

Postcondition:

Returns true iff the tree rooted at node is complete

Returns:

True iff the subtree 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

Postcondition:

Returns true iff the tree rooted at node is balanced

Returns:

True if tree is height balanced

iterator

public Iterator iterator()

Generate an in-order iterator of subtree

Postcondition:

Returns an in-order iterator of the elements

Returns:

In-order iterator on subtree rooted at this

preorderIterator

public AbstractIterator preorderIterator()

Return an iterator to traverse nodes of subtree in-order

Postcondition:

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

Returns:

AbstractIterator to traverse subtree

inorderIterator

public AbstractIterator inorderIterator()

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

Postcondition:

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

Returns:

An in-order iterator over descendants of node

postorderIterator

public AbstractIterator postorderIterator()

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

Precondition:

None

Postcondition:

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

Returns:

An iterator that traverses descendants of node in postorder

levelorderIterator

public AbstractIterator levelorderIterator()

Method to return a level-order iterator of subtree

Precondition:

None

Postcondition:

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

Returns:

An iterator to traverse subtree in level-order

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

Postcondition:

Returns true if this is a left child of parent

Returns:

True iff this node is a left child of parent

isRightChild

public boolean isRightChild()

Determine if this node is a right child

Postcondition:

Returns true if this is a right child of parent

Returns:

True iff this node is a right child of parent

value

public Object value()

Returns value associated with this node

Postcondition:

Returns value associated with this node

Returns:

The node's value

setValue

public void setValue(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 Object

Postcondition:

return sum of hashcodes of the contained values

treeString

public 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.

getHand

private String getHand()

Support method for toString(). Returns R if this is node is a right child, L if this node is a left child and Root if this node is the root.

Returns:

R if this is node is a right child, L if this node is a left child and Root if this node is the root.

toString

public String toString()

Returns a representation the subtree rooted at this node

Overrides:

toString in class Object

Postcondition:

Returns string representation

Returns:

String representing this subtree