net.datastructures
Class LinkedBinaryTree<E>

java.lang.Object
  net.datastructures.LinkedBinaryTree<E>

All Implemented Interfaces:

BinaryTree<E>, Tree<E>

Direct Known Subclasses:

BinarySearchTree

public class LinkedBinaryTree<E>
extends Object
implements BinaryTree<E>

An implementation of the BinaryTree interface by means of a linked structure. //end#fragment LinkedBinaryTree This class serves as a superclass for the BinarySearchTree implementation. This design decision was made to emphasize the conceptual relationship that a BinarySearchTree is a specialized LinkedBinaryTree. An unwanted side-effect of this is that the size method returns the number of total nodes whereas the size method in the BinarySearchTree class returns the number of internal nodes only. For this reason, the the size variable instead of the size method is used within this class.

Author:

Luca Vismara, Roberto Tamassia, Michael Goodrich, Eric Zamore

See Also:

//begin#fragment LinkedBinaryTree

Field Summary

protected BTPosition<E>	root
protected int	size

Constructor Summary

LinkedBinaryTree()
Creates an empty binary tree.

Method Summary

Position<E>	addRoot(E e) Adds a root node to an empty tree
void	attach(Position<E> v, BinaryTree<E> T1, BinaryTree<E> T2) Attaches two trees to be subtrees of an external node.
protected BTPosition<E>	checkPosition(Position<E> v) If v is a good binary tree node, cast to BTPosition, else throw exception
Iterable<Position<E>>	children(Position<E> v) Returns an iterable collection of the children of a node.
protected BTPosition<E>	createNode(E element, BTPosition<E> parent, BTPosition<E> left, BTPosition<E> right) Creates a new binary tree node
void	expandExternal(Position<E> v, E l, E r) Expand an external node into an internal node with two external node children
boolean	hasLeft(Position<E> v) Returns whether a node has a left child.
boolean	hasRight(Position<E> v) Returns whether a node has a right child.
protected void	inorderPositions(Position<E> v, PositionList<Position<E>> pos) Creates a list storing the the nodes in the subtree of a node, ordered according to the inorder traversal of the subtree.
Position<E>	insertLeft(Position<E> v, E e) Inserts a left child at a given node.
Position<E>	insertRight(Position<E> v, E e) Inserts a right child at a given node.
boolean	isEmpty() Returns whether the tree is empty.
boolean	isExternal(Position<E> v) Returns whether a node is external.
boolean	isInternal(Position<E> v) Returns whether a node is internal.
boolean	isRoot(Position<E> v) Returns whether a node is the root.
Iterator<E>	iterator() Returns an iterator of the elements stored at the nodes
Position<E>	left(Position<E> v) Returns the left child of a node.
Position<E>	parent(Position<E> v) Returns the parent of a node.
Iterable<Position<E>>	positions() Returns an iterable collection of the tree nodes.
protected void	preorderPositions(Position<E> v, PositionList<Position<E>> pos) Creates a list storing the the nodes in the subtree of a node, ordered according to the preorder traversal of the subtree.
E	remove(Position<E> v) Removes a node with zero or one child.
void	removeAboveExternal(Position<E> v) Remove an external node v and replace its parent with v's sibling
E	replace(Position<E> v, E o) Replaces the element at a node.
Position<E>	right(Position<E> v) Returns the right child of a node.
Position<E>	root() Returns the root of the tree.
Position<E>	sibling(Position<E> v) Return the sibling of a node
int	size() Returns the number of nodes in the tree.
void	swapElements(Position<E> v, Position<E> w) Swap the elements at two nodes

Methods inherited from class java.lang.Object

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

Field Detail

root

protected BTPosition<E> root

size

protected int size

Constructor Detail

LinkedBinaryTree

public LinkedBinaryTree()

Creates an empty binary tree.

Method Detail

size

public int size()

Returns the number of nodes in the tree.

Specified by:

size in interface Tree<E>

isEmpty

public boolean isEmpty()

Returns whether the tree is empty.

Specified by:

isEmpty in interface Tree<E>

isInternal

public boolean isInternal(Position<E> v)
                   throws InvalidPositionException

Returns whether a node is internal.

Specified by:

isInternal in interface Tree<E>

Throws:

InvalidPositionException

isExternal

public boolean isExternal(Position<E> v)
                   throws InvalidPositionException

Returns whether a node is external.

Specified by:

isExternal in interface Tree<E>

Throws:

InvalidPositionException

isRoot

public boolean isRoot(Position<E> v)
               throws InvalidPositionException

Returns whether a node is the root.

Specified by:

isRoot in interface Tree<E>

Throws:

InvalidPositionException

hasLeft

public boolean hasLeft(Position<E> v)
                throws InvalidPositionException

Returns whether a node has a left child.

Specified by:

hasLeft in interface BinaryTree<E>

Throws:

InvalidPositionException

hasRight

public boolean hasRight(Position<E> v)
                 throws InvalidPositionException

Returns whether a node has a right child.

Specified by:

hasRight in interface BinaryTree<E>

Throws:

InvalidPositionException

root

public Position<E> root()
                 throws EmptyTreeException

Returns the root of the tree.

Specified by:

root in interface Tree<E>

Throws:

EmptyTreeException

left

public Position<E> left(Position<E> v)
                 throws InvalidPositionException,
                        BoundaryViolationException

Returns the left child of a node.

Specified by:

left in interface BinaryTree<E>

Throws:

InvalidPositionException

BoundaryViolationException

right

public Position<E> right(Position<E> v)
                  throws InvalidPositionException,
                         BoundaryViolationException

Returns the right child of a node.

Specified by:

right in interface BinaryTree<E>

Throws:

InvalidPositionException

BoundaryViolationException

parent

public Position<E> parent(Position<E> v)
                   throws InvalidPositionException,
                          BoundaryViolationException

Returns the parent of a node.

Specified by:

parent in interface Tree<E>

Throws:

InvalidPositionException

BoundaryViolationException

children

public Iterable<Position<E>> children(Position<E> v)
                               throws InvalidPositionException

Returns an iterable collection of the children of a node.

Specified by:

children in interface Tree<E>

Throws:

InvalidPositionException

positions

public Iterable<Position<E>> positions()

Returns an iterable collection of the tree nodes.

Specified by:

positions in interface Tree<E>

iterator

public Iterator<E> iterator()

Returns an iterator of the elements stored at the nodes

Specified by:

iterator in interface Tree<E>

replace

public E replace(Position<E> v,
                 E o)
          throws InvalidPositionException

Replaces the element at a node.

Specified by:

replace in interface Tree<E>

Throws:

InvalidPositionException

sibling

public Position<E> sibling(Position<E> v)
                    throws InvalidPositionException,
                           BoundaryViolationException

Return the sibling of a node

Throws:

InvalidPositionException

BoundaryViolationException

addRoot

public Position<E> addRoot(E e)
                    throws NonEmptyTreeException

Adds a root node to an empty tree

Throws:

NonEmptyTreeException

insertLeft

public Position<E> insertLeft(Position<E> v,
                              E e)
                       throws InvalidPositionException

Inserts a left child at a given node.

Throws:

InvalidPositionException

insertRight

public Position<E> insertRight(Position<E> v,
                               E e)
                        throws InvalidPositionException

Inserts a right child at a given node.

Throws:

InvalidPositionException

remove

public E remove(Position<E> v)
         throws InvalidPositionException

Removes a node with zero or one child.

Throws:

InvalidPositionException

attach

public void attach(Position<E> v,
                   BinaryTree<E> T1,
                   BinaryTree<E> T2)
            throws InvalidPositionException

Attaches two trees to be subtrees of an external node.

Throws:

InvalidPositionException

swapElements

public void swapElements(Position<E> v,
                         Position<E> w)
                  throws InvalidPositionException

Swap the elements at two nodes

Throws:

InvalidPositionException

expandExternal

public void expandExternal(Position<E> v,
                           E l,
                           E r)
                    throws InvalidPositionException

Expand an external node into an internal node with two external node children

Throws:

InvalidPositionException

removeAboveExternal

public void removeAboveExternal(Position<E> v)
                         throws InvalidPositionException

Remove an external node v and replace its parent with v's sibling

Throws:

InvalidPositionException

checkPosition

protected BTPosition<E> checkPosition(Position<E> v)
                               throws InvalidPositionException

If v is a good binary tree node, cast to BTPosition, else throw exception

Throws:

InvalidPositionException

createNode

protected BTPosition<E> createNode(E element,
                                   BTPosition<E> parent,
                                   BTPosition<E> left,
                                   BTPosition<E> right)

Creates a new binary tree node

preorderPositions

protected void preorderPositions(Position<E> v,
                                 PositionList<Position<E>> pos)
                          throws InvalidPositionException

Creates a list storing the the nodes in the subtree of a node, ordered according to the preorder traversal of the subtree.

Throws:

InvalidPositionException

inorderPositions

protected void inorderPositions(Position<E> v,
                                PositionList<Position<E>> pos)
                         throws InvalidPositionException

Creates a list storing the the nodes in the subtree of a node, ordered according to the inorder traversal of the subtree.

Throws:

InvalidPositionException