193 lines
6.8 KiB
Java
193 lines
6.8 KiB
Java
package net.datastructures;
|
|
import java.util.ArrayList;
|
|
import java.util.Iterator;
|
|
/**
|
|
* 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 <code>n</code> has rank <i>i</i>,
|
|
* then the left child of <code>n</code> will have rank 2*<i>i</i>,
|
|
* and the right child of <code>n</code> will have rank 2*<i>i</i> +
|
|
* 1. Traversing the contents of the vector in order of increasing
|
|
* rank yields a level-order traversal
|
|
*
|
|
* @author Michael Goodrich, Eric Zamore
|
|
* @see BinaryTree
|
|
* @see CompleteBinaryTree
|
|
*/
|
|
|
|
//begin#fragment VectorHeap
|
|
public class ArrayListCompleteBinaryTree<E>
|
|
implements CompleteBinaryTree<E> {
|
|
protected ArrayList<BTPos<E>> T; // indexed list of tree positions
|
|
/** Nested class for a index list-based complete binary tree node. */
|
|
protected static class BTPos<E> implements Position<E> {
|
|
E element; // element stored at this position
|
|
int index; // index of this position in the array list
|
|
public BTPos(E elt, int i) {
|
|
element = elt;
|
|
index = i;
|
|
}
|
|
public E element() { return element; }
|
|
public int index() { return index; }
|
|
public E setElement(E elt) {
|
|
E temp = element;
|
|
element = elt;
|
|
return temp;
|
|
}
|
|
//end#fragment VectorHeap
|
|
public String toString() {
|
|
return("[" + element + "," + index + "]");
|
|
}
|
|
//begin#fragment VectorHeap
|
|
}
|
|
/** default constructor */
|
|
public ArrayListCompleteBinaryTree() {
|
|
T = new ArrayList<BTPos<E>>();
|
|
T.add(0, null); // the location at rank 0 is deliberately empty
|
|
}
|
|
/** Returns the number of (internal and external) nodes. */
|
|
public int size() { return T.size() - 1; }
|
|
/** Returns whether the tree is empty. */
|
|
public boolean isEmpty() { return (size() == 0); }
|
|
//end#fragment VectorHeap
|
|
//begin#fragment VectorHeap2
|
|
/** Returns whether v is an internal node. */
|
|
public boolean isInternal(Position<E> v) throws InvalidPositionException {
|
|
return hasLeft(v); // if v has a right child it will have a left child
|
|
}
|
|
/** Returns whether v is an external node. */
|
|
public boolean isExternal(Position<E> v) throws InvalidPositionException {
|
|
return !isInternal(v);
|
|
}
|
|
/** Returns whether v is the root node. */
|
|
public boolean isRoot(Position<E> v) throws InvalidPositionException {
|
|
BTPos<E> vv = checkPosition(v);
|
|
return vv.index() == 1;
|
|
}
|
|
/** Returns whether v has a left child. */
|
|
public boolean hasLeft(Position<E> v) throws InvalidPositionException {
|
|
BTPos<E> vv = checkPosition(v);
|
|
return 2*vv.index() <= size();
|
|
}
|
|
/** Returns whether v has a right child. */
|
|
public boolean hasRight(Position<E> v) throws InvalidPositionException {
|
|
BTPos<E> vv = checkPosition(v);
|
|
return 2*vv.index() + 1 <= size();
|
|
}
|
|
/** Returns the root of the tree. */
|
|
public Position<E> root() throws EmptyTreeException {
|
|
if (isEmpty()) throw new EmptyTreeException("Tree is empty");
|
|
return T.get(1);
|
|
}
|
|
/** Returns the left child of v. */
|
|
public Position<E> left(Position<E> v)
|
|
throws InvalidPositionException, BoundaryViolationException {
|
|
if (!hasLeft(v)) throw new BoundaryViolationException("No left child");
|
|
BTPos<E> vv = checkPosition(v);
|
|
return T.get(2*vv.index());
|
|
}
|
|
/** Returns the right child of v. */
|
|
public Position<E> right(Position<E> v)
|
|
throws InvalidPositionException {
|
|
if (!hasRight(v)) throw new BoundaryViolationException("No right child");
|
|
BTPos<E> vv = checkPosition(v);
|
|
return T.get(2*vv.index() + 1);
|
|
}
|
|
//end#fragment VectorHeap2
|
|
//begin#fragment VectorHeap3
|
|
/** Returns the parent of v. */
|
|
public Position<E> parent(Position<E> v)
|
|
throws InvalidPositionException, BoundaryViolationException {
|
|
if (isRoot(v)) throw new BoundaryViolationException("No parent");
|
|
BTPos<E> vv = checkPosition(v);
|
|
return T.get(vv.index()/2);
|
|
}
|
|
//end#fragment VectorHeap3
|
|
/** Returns an iterable collection of the children of v. */
|
|
public Iterable<Position<E>> children(Position<E> v) throws InvalidPositionException {
|
|
PositionList<Position<E>> children = new NodePositionList<Position<E>>();
|
|
if (hasLeft(v))
|
|
children.addLast(left(v));
|
|
if (hasRight(v))
|
|
children.addLast(right(v));
|
|
return children;
|
|
}
|
|
/** Returns an iterable collection of all the nodes in the tree. */
|
|
public Iterable<Position<E>> positions() {
|
|
ArrayList<Position<E>> P = new ArrayList<Position<E>>();
|
|
Iterator<BTPos<E>> iter = T.iterator();
|
|
iter.next(); // skip the first position
|
|
while (iter.hasNext())
|
|
P.add(iter.next());
|
|
return P;
|
|
}
|
|
//begin#fragment VectorHeap3
|
|
/** Replaces the element at v. */
|
|
public E replace(Position<E> v, E o) throws InvalidPositionException {
|
|
BTPos<E> vv = checkPosition(v);
|
|
return vv.setElement(o);
|
|
}
|
|
/** Adds an element just after the last node (in a level numbering). */
|
|
public Position<E> add(E e) {
|
|
int i = size() + 1;
|
|
BTPos<E> p = new BTPos<E>(e,i);
|
|
T.add(i, p);
|
|
return p;
|
|
}
|
|
/** Removes and returns the element at the last node. */
|
|
public E remove() throws EmptyTreeException {
|
|
if(isEmpty()) throw new EmptyTreeException("Tree is empty");
|
|
return T.remove(size()).element();
|
|
}
|
|
/** Determines whether the given position is a valid node. */
|
|
protected BTPos<E> checkPosition(Position<E> v)
|
|
throws InvalidPositionException
|
|
{
|
|
if (v == null || !(v instanceof BTPos))
|
|
throw new InvalidPositionException("Position is invalid");
|
|
return (BTPos<E>) v;
|
|
}
|
|
//end#fragment VectorHeap3
|
|
// Additional Methods
|
|
/** Returns the sibling of v. */
|
|
public Position<E> sibling(Position<E> v)
|
|
throws InvalidPositionException, BoundaryViolationException {
|
|
try {
|
|
Position<E> p = parent(v);
|
|
Position<E> lc = left(p);
|
|
if (v == lc)
|
|
return right(p);
|
|
else
|
|
return lc;
|
|
}
|
|
catch(BoundaryViolationException e) {
|
|
throw new BoundaryViolationException("Node has no sibling");
|
|
}
|
|
}
|
|
/** Swaps the elements at two nodes. */
|
|
public void swapElements(Position<E> v, Position<E> w)
|
|
throws InvalidPositionException {
|
|
BTPos<E> vv = checkPosition(v);
|
|
BTPos<E> ww = checkPosition(w);
|
|
E temp = vv.element();
|
|
vv.setElement(ww.element());
|
|
ww.setElement(temp);
|
|
}
|
|
//begin#fragment VectorHeap3
|
|
/** Returns an iterator of the elements stored at all nodes in the tree. */
|
|
public Iterator<E> iterator() {
|
|
ArrayList<E> list = new ArrayList<E>();
|
|
Iterator<BTPos<E>> iter = T.iterator();
|
|
iter.next(); // skip the first element
|
|
while (iter.hasNext())
|
|
list.add(iter.next().element());
|
|
return list.iterator();
|
|
}
|
|
//end#fragment VectorHeap3
|
|
/** Returns a String representing this complete binary tree. */
|
|
public String toString() { return T.toString(); }
|
|
//begin#fragment VectorHeap3
|
|
}
|
|
//end#fragment VectorHeap3
|