net.datastructures
Class VectorCompleteBinaryTree

java.lang.Object
  net.datastructures.VectorCompleteBinaryTree

All Implemented Interfaces:

BinaryTree, CompleteBinaryTree, Tree

public class VectorCompleteBinaryTree

extends Object

implements CompleteBinaryTree

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

VectorCompleteBinaryTree.VectorNode Nested class for a vector-based complete binary tree node.

Field Summary

protected Vector

T

Constructor Summary

VectorCompleteBinaryTree()
default constructor

Method Summary

Position	add(Object e) Add an element just after the last node (in a level numbering).
protected VectorCompleteBinaryTree.VectorNode	checkPosition(Position v) Determine whether v is a valid node.
Iterator	children(Position v) Returns an iterator of the children of v.
Iterator	elements() Returns an iterator of the elements stored at all nodes in the tree.
boolean	hasLeft(Position v) Returns whether v has a left child.
boolean	hasRight(Position v) Returns whether v has a right child.
protected int	inorderPositions(Position v, List pos, int i) Fills a list according to an inorder traversal.
boolean	isEmpty() Returns whether the tree is empty.
boolean	isExternal(Position v) Returns whether v is an external node.
boolean	isInternal(Position v) Returns whether v is an internal node.
boolean	isRoot(Position v) Returns whether v is the root node.
Position	left(Position v) Returns the left child of v.
Position	parent(Position v) Returns the parent of v.
Iterator	positions() Returns an iterator of all nodes in the tree.
Object	remove() Removes and returns the element at the last node.
Object	replace(Position v, Object o) Replaces the element at v.
Position	right(Position v) Returns the right child of v.
Position	root() Returns the root of the tree.
Position	sibling(Position v) Returns the sibling of v.
int	size() Returns the number of (internal and external) nodes.
void	swapElements(Position v, Position 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 Vector T

Constructor Detail

VectorCompleteBinaryTree

public VectorCompleteBinaryTree()

default constructor

Method Detail

size

public int size()

Returns the number of (internal and external) nodes.

Specified by:

size in interface Tree

isEmpty

public boolean isEmpty()

Returns whether the tree is empty.

Specified by:

isEmpty in interface Tree

isInternal

public boolean isInternal(Position v)
                   throws InvalidPositionException

Returns whether v is an internal node.

Specified by:

isInternal in interface Tree

Throws:

InvalidPositionException

isExternal

public boolean isExternal(Position v)
                   throws InvalidPositionException

Returns whether v is an external node.

Specified by:

isExternal in interface Tree

Throws:

InvalidPositionException

isRoot

public boolean isRoot(Position v)
               throws InvalidPositionException

Returns whether v is the root node.

Specified by:

isRoot in interface Tree

Throws:

InvalidPositionException

hasLeft

public boolean hasLeft(Position v)
                throws InvalidPositionException

Returns whether v has a left child.

Specified by:

hasLeft in interface BinaryTree

Throws:

InvalidPositionException

hasRight

public boolean hasRight(Position v)
                 throws InvalidPositionException

Returns whether v has a right child.

Specified by:

hasRight in interface BinaryTree

Throws:

InvalidPositionException

root

public Position root()
              throws EmptyTreeException

Returns the root of the tree.

Specified by:

root in interface Tree

Throws:

EmptyTreeException

left

public Position left(Position v)
              throws InvalidPositionException,
                     BoundaryViolationException

Returns the left child of v.

Specified by:

left in interface BinaryTree

Throws:

InvalidPositionException

BoundaryViolationException

right

public Position right(Position v)
               throws InvalidPositionException

Returns the right child of v.

Specified by:

right in interface BinaryTree

Throws:

InvalidPositionException

parent

public Position parent(Position v)
                throws InvalidPositionException,
                       BoundaryViolationException

Returns the parent of v.

Specified by:

parent in interface Tree

Throws:

InvalidPositionException

BoundaryViolationException

children

public Iterator children(Position v)
                  throws InvalidPositionException

Returns an iterator of the children of v.

Specified by:

children in interface Tree

Throws:

InvalidPositionException

positions

public Iterator positions()

Returns an iterator of all nodes in the tree.

Specified by:

positions in interface Tree

replace

public Object replace(Position v,
                      Object o)
               throws InvalidPositionException

Replaces the element at v.

Specified by:

replace in interface Tree

Throws:

InvalidPositionException

add

public Position add(Object e)

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

Specified by:

add in interface CompleteBinaryTree

remove

public Object remove()
              throws EmptyTreeException

Removes and returns the element at the last node.

Specified by:

remove in interface CompleteBinaryTree

Throws:

EmptyTreeException

checkPosition

protected VectorCompleteBinaryTree.VectorNode checkPosition(Position v)
                                                     throws InvalidPositionException

Determine whether v is a valid node.

Throws:

InvalidPositionException

inorderPositions

protected int inorderPositions(Position v,
                               List pos,
                               int i)
                        throws InvalidPositionException

Fills a list according to an inorder traversal.

Throws:

InvalidPositionException

sibling

public Position sibling(Position v)
                 throws InvalidPositionException,
                        BoundaryViolationException

Returns the sibling of v.

Throws:

InvalidPositionException

BoundaryViolationException

swapElements

public void swapElements(Position v,
                         Position w)
                  throws InvalidPositionException

Swaps the elements at two nodes.

Throws:

InvalidPositionException

elements

public Iterator elements()

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

Specified by:

elements in interface Tree

toString

public String toString()

Returns a String representing this complete binary tree.