package net.datastructures;
import java.util.Iterator;
/**
* An implementation of the BinaryTree interface by means of a linked structure.
* 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
* {@link #size() size} method returns the number of total nodes
* whereas the {@link BinarySearchTree#size() size} method in the
* {@link BinarySearchTree BinarySearchTree} class returns the number
* of internal nodes only. For this reason, the the {@link #size
* size} variable instead of the {@link #size() size} method is used
* within this class.
*
* @author Luca Vismara, Roberto Tamassia, Michael Goodrich, Eric
* Zamore
* @see BinaryTree
*/
/**
* @costaContext net/datastructures/BTNode net/datastructures/NodeList
*/
public class LinkedBinaryTree implements BinaryTree {
protected Position root; // reference to the root
protected int size; // number of nodes
/** Creates an empty binary tree. */
public LinkedBinaryTree() {
root = null; // start with an empty tree
size = 0;
}
// BinaryTree interface methods
/** Returns the number of nodes in the tree. */
public int size() {
return size;
}
/** Returns whether the tree is empty. */
public boolean isEmpty() {
return (size==0);
}
/** Returns whether a node is internal. */
public boolean isInternal(Position v) throws InvalidPositionException {
checkPosition(v); // auxiliary method
return (hasLeft(v) || hasRight(v));
}
/** Returns whether a node is external. */
public boolean isExternal(Position v) throws InvalidPositionException {
return !isInternal(v);
}
/** Returns whether a node is the root. */
public boolean isRoot(Position v) throws InvalidPositionException {
checkPosition(v);
return (v == root());
}
/** Returns whether a node has a left child. */
public boolean hasLeft(Position v) throws InvalidPositionException {
BTPosition vv = checkPosition(v);
return (vv.getLeft() != null);
}
/** Returns whether a node has a right child. */
public boolean hasRight(Position v) throws InvalidPositionException {
BTPosition vv = checkPosition(v);
return (vv.getRight() != null);
}
/** Returns the root of the tree. */
public Position root() throws EmptyTreeException {
if (root == null)
throw new EmptyTreeException("The tree has no root");
return root;
}
/** Returns the left child of a node. */
public Position left(Position v)
throws InvalidPositionException, BoundaryViolationException {
if (!hasLeft(v))
throw new BoundaryViolationException("No left child");
return ((BTPosition)v).getLeft();
}
/** Returns the right child of a node. */
public Position right(Position v)
throws InvalidPositionException, BoundaryViolationException {
if (!hasRight(v))
throw new BoundaryViolationException("No right child");
return ((BTPosition)v).getRight();
}
/** Returns the parent of a node. */
public Position parent(Position v)
throws InvalidPositionException, BoundaryViolationException {
if (isRoot(v))
throw new BoundaryViolationException("Root has no parent");
return ((BTPosition)v).getParent();
}
/** Returns an iterator of the children of a node. */
public Iterator children(Position v)
throws InvalidPositionException {
List children = new NodeList();
if (hasLeft(v))
children.insertLast(left(v));
if (hasRight(v))
children.insertLast(right(v));
return children.elements();
}
/** Returns an iterator of the tree nodes. */
public Iterator positions() {
List positions = new NodeList();
if(size != 0)
inorderPositions(root(), positions); // assign positions in inorder
return positions.elements();
}
/** Returns an iterator of the elements stored at the nodes */
public Iterator elements() {
Iterator positer = positions();
List elements = new NodeList();
for (int i = 0; i < size; i++)
elements.insertLast(((Position) positer.next()).element());
return elements.elements(); // An iterator of elements
}
/** Replaces the element at a node. */
public Object replace(Position v, Object o)
throws InvalidPositionException {
BTPosition vv = checkPosition(v);
Object temp = v.element();
vv.setElement(o);
return temp;
}
// Additional accessor method
/** Return the sibling of a node */
public Position sibling(Position v)
throws InvalidPositionException, BoundaryViolationException {
try {
Position p = parent(v);
Position lc = left(p);
if (v == lc)
return right(p);
else
return lc;
}
catch(BoundaryViolationException e) {
throw new BoundaryViolationException("Node has no sibling");
}
}
// Additional update methods
/** Inserts a left child at a given node. */
public Position insertLeft(Position v, Object e)
throws InvalidPositionException {
if (hasLeft(v))
throw new InvalidPositionException("Node already has a left child");
BTPosition vv = (BTPosition)v;
BTPosition ww = createNode(e, vv, null, null);
vv.setLeft(ww);
size++;
return ww;
}
/** Inserts a right child at a given node. */
public Position insertRight(Position v, Object e)
throws InvalidPositionException {
if (hasRight(v))
throw new InvalidPositionException("Node already has a right child");
BTPosition vv = (BTPosition)v;
BTPosition w = createNode(e, vv, null, null);
vv.setRight(w);
size++;
return w;
}
/** Removes a node with zero or one child. */
public Object remove(Position v)
throws InvalidPositionException {
if (hasLeft(v) && hasRight(v))
throw new InvalidPositionException("Cannot remove node w/ 2 children");
BTPosition vv = (BTPosition)v;
BTPosition ww; // the only child of v, if any
if (hasLeft(v))
ww = (BTPosition) left(v);
else if (hasRight(v))
ww = (BTPosition) right(v);
else
ww = null;
if (v == root()) {
if (ww != null)
ww.setParent(null);
root = ww;
}
else {
BTPosition uu = (BTPosition) parent(v);
if (hasLeft(uu) && v == left(uu))
uu.setLeft(ww);
else
uu.setRight(ww);
if(ww != null)
ww.setParent(uu);
}
size--;
return v.element();
}
/** Adds a root node to an empty tree */
public Position addRoot(Object e) throws NonEmptyTreeException {
if(!isEmpty())
throw new NonEmptyTreeException("Tree already has a root");
size = 1;
root = createNode(e,null,null,null);
return root;
}
/** Attaches two trees to be subtrees of an external node. */
public void attach(Position v, BinaryTree T1, BinaryTree T2)
throws InvalidPositionException {
if (isInternal(v))
throw new InvalidPositionException("Cannot attach from internal node");
BTPosition vv = (BTPosition)v;
if (!T1.isEmpty()) {
vv.setLeft((BTPosition) T1.root());
((BTPosition)T1.root()).setParent(vv); // T1 should be invalidated
}
if (!T2.isEmpty()) {
vv.setRight((BTPosition) T2.root());
((BTPosition)T2.root()).setParent(vv); // T2 should be invalidated
}
}
/** Swap the elements at two nodes */
public void swapElements(Position v, Position w)
throws InvalidPositionException {
BTPosition vv = checkPosition(v);
BTPosition ww = checkPosition(w);
Object temp = w.element();
ww.setElement(v.element());
vv.setElement(temp);
}
/** Expand an external node into an internal node with two external
node children */
public void expandExternal(Position v, Object l, Object r)
throws InvalidPositionException {
if (!isExternal(v))
throw new InvalidPositionException("Node is not external");
insertLeft(v, l);
insertRight(v, r);
}
/** Remove an external node v and replace its parent with v's
sibling */
public void removeAboveExternal(Position v)
throws InvalidPositionException {
if (!isExternal(v))
throw new InvalidPositionException("Node is not external");
if (isRoot(v))
remove(v);
else {
Position u = parent(v);
remove(v);
remove(u);
}
}
// Auxiliary methods
/** If v is a good binary tree node, cast to BTPosition, else throw exception */
protected BTPosition checkPosition(Position v)
throws InvalidPositionException {
if (v == null || !(v instanceof BTPosition))
throw new InvalidPositionException("The position is invalid");
return (BTPosition) v;
}
/** Creates a new binary tree node */
protected BTPosition createNode(Object element, BTPosition parent,
BTPosition left, BTPosition right) {
return new BTNode(element,parent,left,right); }
/** Creates a list storing the the nodes in the subtree of a node,
* ordered according to the inorder traversal of the subtree. */
protected void inorderPositions(Position v, List pos)
throws InvalidPositionException {
if (hasLeft(v))
inorderPositions(left(v), pos); // recurse on left child
pos.insertLast(v);
if (hasRight(v))
inorderPositions(right(v), pos); // recurse on right child
}
}