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

Nested Class Summary

protected static class

ArrayListCompleteBinaryTree.BTPos<E> Nested class for a index list-based complete binary tree node.

Field Summary

protected ArrayList<ArrayListCompleteBinaryTree.BTPos<E>>

T

Constructor Summary

ArrayListCompleteBinaryTree()
default constructor

Method Summary

Position<E>	add(E e) Adds an element just after the last node (in a level numbering).
protected ArrayListCompleteBinaryTree.BTPos<E>	checkPosition(Position<E> v) Determines whether the given position is a valid node.
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.
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.
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.
String	toString() Returns a String representing this complete binary tree.

Methods inherited from class java.lang.Object

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

Field Detail

T

protected ArrayList<ArrayListCompleteBinaryTree.BTPos<E>> T

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

checkPosition

protected ArrayListCompleteBinaryTree.BTPos<E> checkPosition(Position<E> v)
                                                      throws InvalidPositionException

Determines whether the given position is a valid node.

Throws:

InvalidPositionException

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 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 String toString()

Returns a String representing this complete binary tree.

Overrides:

toString in class Object