net.datastructures
Class LinkedTree<E>

java.lang.Object
  net.datastructures.LinkedTree<E>

All Implemented Interfaces:

Tree<E>

public class LinkedTree<E>
extends Object
implements Tree<E>

A linked class for a tree where nodes have an arbitrary number of children. //end#fragment Tree

Author:

Luca Vismara, Roberto Tamassia, Michael Goodrich, Eric Zamore //begin#fragment Tree

Field Summary

protected TreePosition<E>	root
protected int	size

Constructor Summary

LinkedTree()
Creates an empty tree.

Method Summary

Position<E>	addRoot(E e) Adds a root node to an empty tree
protected TreePosition<E>	checkPosition(Position<E> v) If v is a good tree node, cast to TreePosition, else throw exception
Iterable<Position<E>>	children(Position<E> v) Returns an iterable collection of the children of a node.
protected TreePosition<E>	createNode(E element, TreePosition<E> parent, PositionList<Position<E>> children) Creates a new tree node
boolean	isEmpty() Returns whether the tree is empty.
boolean	isExternal(Position<E> v) Returns whether a node is external.
boolean	isInternal(Position<E> v) Returns whether a node is internal.
boolean	isRoot(Position<E> v) Returns whether a node is the root.
Iterator<E>	iterator() Returns an iterator of the elements stored at the nodes
Position<E>	parent(Position<E> v) Returns the parent of a node.
Iterable<Position<E>>	positions() Returns an iterable collection of the tree nodes.
protected void	preorderPositions(Position<E> v, PositionList<Position<E>> pos) Creates a list storing the the nodes in the subtree of a node, ordered according to the preorder traversal of the subtree.
E	replace(Position<E> v, E o) Replaces the element at a node.
Position<E>	root() Returns the root of the tree.
int	size() Returns the number of nodes in the tree.
void	swapElements(Position<E> v, Position<E> 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 TreePosition<E> root

size

protected int size

Constructor Detail

LinkedTree

public LinkedTree()

Creates an empty tree.

Method Detail

size

public int size()

Returns the number of nodes in the tree.

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

Specified by:

isInternal in interface Tree<E>

Throws:

InvalidPositionException

isExternal

public boolean isExternal(Position<E> v)
                   throws InvalidPositionException

Returns whether a node is external.

Specified by:

isExternal in interface Tree<E>

Throws:

InvalidPositionException

isRoot

public boolean isRoot(Position<E> v)
               throws InvalidPositionException

Returns whether a node is the root.

Specified by:

isRoot in interface Tree<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

parent

public Position<E> parent(Position<E> v)
                   throws InvalidPositionException,
                          BoundaryViolationException

Returns the parent of a node.

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

Specified by:

children in interface Tree<E>

Throws:

InvalidPositionException

positions

public Iterable<Position<E>> positions()

Returns an iterable collection of the tree nodes.

Specified by:

positions in interface Tree<E>

iterator

public Iterator<E> iterator()

Returns an iterator of the elements stored at the nodes

Specified by:

iterator in interface Tree<E>

replace

public E replace(Position<E> v,
                 E o)
          throws InvalidPositionException

Replaces the element at a node.

Specified by:

replace in interface Tree<E>

Throws:

InvalidPositionException

addRoot

public Position<E> addRoot(E e)
                    throws NonEmptyTreeException

Adds a root node to an empty tree

Throws:

NonEmptyTreeException

swapElements

public void swapElements(Position<E> v,
                         Position<E> w)
                  throws InvalidPositionException

Swap the elements at two nodes

Throws:

InvalidPositionException

checkPosition

protected TreePosition<E> checkPosition(Position<E> v)
                                 throws InvalidPositionException

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

Throws:

InvalidPositionException

createNode

protected TreePosition<E> createNode(E element,
                                     TreePosition<E> parent,
                                     PositionList<Position<E>> children)

Creates a new tree node

preorderPositions

protected void preorderPositions(Position<E> v,
                                 PositionList<Position<E>> pos)
                          throws InvalidPositionException

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

Throws:

InvalidPositionException