net.datastructures
Class LinkedBinaryTree

java.lang.Object
  net.datastructures.LinkedBinaryTree

All Implemented Interfaces:

BinaryTree, Tree

Direct Known Subclasses:

BinarySearchTree

public class LinkedBinaryTree

extends Object

implements BinaryTree

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 size method returns the number of total nodes whereas the size method in the BinarySearchTree class returns the number of internal nodes only. For this reason, the the size variable instead of the size method is used within this class.

Author:

Luca Vismara, Roberto Tamassia, Michael Goodrich, Eric Zamore

See Also:

BinaryTree

Field Summary

protected Position	root
protected int	size

Constructor Summary

LinkedBinaryTree()
Creates an empty binary tree.

Method Summary

Position	addRoot(Object e) Adds a root node to an empty tree
void	attach(Position v, BinaryTree T1, BinaryTree T2) Attaches two trees to be subtrees of an external node.
protected BTPosition	checkPosition(Position v) If v is a good binary tree node, cast to BTPosition, else throw exception
Iterator	children(Position v) Returns an iterator of the children of a node.
protected BTPosition	createNode(Object element, BTPosition parent, BTPosition left, BTPosition right) Creates a new binary tree node
Iterator	elements() Returns an iterator of the elements stored at the nodes
void	expandExternal(Position v, Object l, Object r) Expand an external node into an internal node with two external node children
boolean	hasLeft(Position v) Returns whether a node has a left child.
boolean	hasRight(Position v) Returns whether a node has a right child.
protected void	inorderPositions(Position v, List pos) Creates a list storing the the nodes in the subtree of a node, ordered according to the inorder traversal of the subtree.
Position	insertLeft(Position v, Object e) Inserts a left child at a given node.
Position	insertRight(Position v, Object e) Inserts a right child at a given node.
boolean	isEmpty() Returns whether the tree is empty.
boolean	isExternal(Position v) Returns whether a node is external.
boolean	isInternal(Position v) Returns whether a node is internal.
boolean	isRoot(Position v) Returns whether a node is the root.
Position	left(Position v) Returns the left child of a node.
Position	parent(Position v) Returns the parent of a node.
Iterator	positions() Returns an iterator of the tree nodes.
Object	remove(Position v) Removes a node with zero or one child.
void	removeAboveExternal(Position v) Remove an external node v and replace its parent with v's sibling
Object	replace(Position v, Object o) Replaces the element at a node.
Position	right(Position v) Returns the right child of a node.
Position	root() Returns the root of the tree.
Position	sibling(Position v) Return the sibling of a node
int	size() Returns the number of nodes in the tree.
void	swapElements(Position v, Position w) Swap the elements at two nodes

Methods inherited from class java.lang.Object

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

Field Detail

root

protected Position root

size

protected int size

Constructor Detail

LinkedBinaryTree

public LinkedBinaryTree()

Creates an empty binary tree.

Method Detail

size

public int size()

Returns the number of nodes in the tree.

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

Specified by:

isInternal in interface Tree

Throws:

InvalidPositionException

isExternal

public boolean isExternal(Position v)
                   throws InvalidPositionException

Returns whether a node is external.

Specified by:

isExternal in interface Tree

Throws:

InvalidPositionException

isRoot

public boolean isRoot(Position v)
               throws InvalidPositionException

Returns whether a node is the root.

Specified by:

isRoot in interface Tree

Throws:

InvalidPositionException

hasLeft

public boolean hasLeft(Position v)
                throws InvalidPositionException

Returns whether a node has a left child.

Specified by:

hasLeft in interface BinaryTree

Throws:

InvalidPositionException

hasRight

public boolean hasRight(Position v)
                 throws InvalidPositionException

Returns whether a node 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 a node.

Specified by:

left in interface BinaryTree

Throws:

InvalidPositionException

BoundaryViolationException

right

public Position right(Position v)
               throws InvalidPositionException,
                      BoundaryViolationException

Returns the right child of a node.

Specified by:

right in interface BinaryTree

Throws:

InvalidPositionException

BoundaryViolationException

parent

public Position parent(Position v)
                throws InvalidPositionException,
                       BoundaryViolationException

Returns the parent of a node.

Specified by:

parent in interface Tree

Throws:

InvalidPositionException

BoundaryViolationException

children

public Iterator children(Position v)
                  throws InvalidPositionException

Returns an iterator of the children of a node.

Specified by:

children in interface Tree

Throws:

InvalidPositionException

positions

public Iterator positions()

Returns an iterator of the tree nodes.

Specified by:

positions in interface Tree

elements

public Iterator elements()

Returns an iterator of the elements stored at the nodes

Specified by:

elements in interface Tree

replace

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

Replaces the element at a node.

Specified by:

replace in interface Tree

Throws:

InvalidPositionException

sibling

public Position sibling(Position v)
                 throws InvalidPositionException,
                        BoundaryViolationException

Return the sibling of a node

Throws:

InvalidPositionException

BoundaryViolationException

insertLeft

public Position insertLeft(Position v,
                           Object e)
                    throws InvalidPositionException

Inserts a left child at a given node.

Throws:

InvalidPositionException

insertRight

public Position insertRight(Position v,
                            Object e)
                     throws InvalidPositionException

Inserts a right child at a given node.

Throws:

InvalidPositionException

remove

public Object remove(Position v)
              throws InvalidPositionException

Removes a node with zero or one child.

Throws:

InvalidPositionException

addRoot

public Position addRoot(Object e)
                 throws NonEmptyTreeException

Adds a root node to an empty tree

Throws:

NonEmptyTreeException

attach

public void attach(Position v,
                   BinaryTree T1,
                   BinaryTree T2)
            throws InvalidPositionException

Attaches two trees to be subtrees of an external node.

Throws:

InvalidPositionException

swapElements

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

Swap the elements at two nodes

Throws:

InvalidPositionException

expandExternal

public void expandExternal(Position v,
                           Object l,
                           Object r)
                    throws InvalidPositionException

Expand an external node into an internal node with two external node children

Throws:

InvalidPositionException

removeAboveExternal

public void removeAboveExternal(Position v)
                         throws InvalidPositionException

Remove an external node v and replace its parent with v's sibling

Throws:

InvalidPositionException

checkPosition

protected BTPosition checkPosition(Position v)
                            throws InvalidPositionException

If v is a good binary tree node, cast to BTPosition, else throw exception

Throws:

InvalidPositionException

createNode

protected BTPosition createNode(Object element,
                                BTPosition parent,
                                BTPosition left,
                                BTPosition right)

Creates a new binary tree node

inorderPositions

protected void inorderPositions(Position v,
                                List pos)
                         throws InvalidPositionException

Creates a list storing the the nodes in the subtree of a node, ordered according to the inorder traversal of the subtree.

Throws:

InvalidPositionException