net.datastructures
Class ArrayListCompleteBinaryTree<E>

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

All Implemented Interfaces:

BinaryTree<E>, CompleteBinaryTree<E>, Tree<E>

public class ArrayListCompleteBinaryTree<E>
extends java.lang.Object
implements CompleteBinaryTree<E>

A speedy implementation of the CompleteBinaryTree interface using a vector. Within the vector, there is a null element at rank 0, the root of the tree at rank 1, and the rest of the tree is contained as follows. If node n has rank i, then the left child of n will have rank 2*i, and the right child of n will have rank 2*i + 1. Traversing the contents of the vector in order of increasing rank yields a level-order traversal

Author:

Michael Goodrich, Eric Zamore

See Also:

BinaryTree, CompleteBinaryTree

Constructor Summary

ArrayListCompleteBinaryTree()
default constructor

Method Summary

Position<E>	add(E e) Adds an element just after the last node (in a level numbering).
java.lang.Iterable<Position<E>>	children(Position<E> v) Returns an iterable collection of the children of v.
boolean	hasLeft(Position<E> v) Returns whether v has a left child.
boolean	hasRight(Position<E> v) Returns whether v has a right child.
boolean	isEmpty() Returns whether the tree is empty.
boolean	isExternal(Position<E> v) Returns whether v is an external node.
boolean	isInternal(Position<E> v) Returns whether v is an internal node.
boolean	isRoot(Position<E> v) Returns whether v is the root node.
java.util.Iterator<E>	iterator() Returns an iterator of the elements stored at all nodes in the tree.
Position<E>	left(Position<E> v) Returns the left child of v.
Position<E>	parent(Position<E> v) Returns the parent of v.
java.lang.Iterable<Position<E>>	positions() Returns an iterable collection of all the nodes in the tree.
E	remove() Removes and returns the element at the last node.
E	replace(Position<E> v, E o) Replaces the element at v.
Position<E>	right(Position<E> v) Returns the right child of v.
Position<E>	root() Returns the root of the tree.
Position<E>	sibling(Position<E> v) Returns the sibling of v.
int	size() Returns the number of (internal and external) nodes.
void	swapElements(Position<E> v, Position<E> w) Swaps the elements at two nodes.
java.lang.String	toString() Returns a String representing this complete binary tree.

Methods inherited from class java.lang.Object

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

Constructor Detail

ArrayListCompleteBinaryTree

public ArrayListCompleteBinaryTree()

default constructor

Method Detail

size

public int size()

Returns the number of (internal and external) nodes.

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 v is an internal node.

Specified by:

isInternal in interface Tree<E>

Throws:

InvalidPositionException

isExternal

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

Returns whether v is an external node.

Specified by:

isExternal in interface Tree<E>

Throws:

InvalidPositionException

isRoot

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

Returns whether v is the root node.

Specified by:

isRoot in interface Tree<E>

Throws:

InvalidPositionException

hasLeft

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

Returns whether v has a left child.

Specified by:

hasLeft in interface BinaryTree<E>

Throws:

InvalidPositionException

hasRight

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

Returns whether v 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 v.

Specified by:

left in interface BinaryTree<E>

Throws:

InvalidPositionException

BoundaryViolationException

right

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

Returns the right child of v.

Specified by:

right in interface BinaryTree<E>

Throws:

InvalidPositionException

parent

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

Returns the parent of v.

Specified by:

parent in interface Tree<E>

Throws:

InvalidPositionException

BoundaryViolationException

children

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

Returns an iterable collection of the children of v.

Specified by:

children in interface Tree<E>

Throws:

InvalidPositionException

positions

public java.lang.Iterable<Position<E>> positions()

Returns an iterable collection of all the nodes in the tree.

Specified by:

positions in interface Tree<E>

replace

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

Replaces the element at v.

Specified by:

replace in interface Tree<E>

Throws:

InvalidPositionException

add

public Position<E> add(E e)

Adds an element just after the last node (in a level numbering).

Specified by:

add in interface CompleteBinaryTree<E>

remove

public E remove()
         throws EmptyTreeException

Removes and returns the element at the last node.

Specified by:

remove in interface CompleteBinaryTree<E>

Throws:

EmptyTreeException

sibling

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

Returns the sibling of v.

Throws:

InvalidPositionException

BoundaryViolationException

swapElements

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

Swaps the elements at two nodes.

Throws:

InvalidPositionException

iterator

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

Returns an iterator of the elements stored at all nodes in the tree.

Specified by:

iterator in interface Tree<E>

toString

public java.lang.String toString()

Returns a String representing this complete binary tree.

Overrides:

toString in class java.lang.Object