net.datastructures
Class LinkedTree<E>

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

All Implemented Interfaces:

Tree<E>

public class LinkedTree<E>
extends java.lang.Object
implements Tree<E>

A linked class for a tree where nodes have an arbitrary number of children.

Author:

Luca Vismara, Roberto Tamassia, Michael Goodrich, Eric Zamore

Constructor Summary

LinkedTree()
Creates an empty tree.

Method Summary

Position<E>	addRoot(E e) Adds a root node to an empty tree
java.lang.Iterable<Position<E>>	children(Position<E> v) Returns an iterable collection of the children of a 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.
java.util.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.
java.lang.Iterable<Position<E>>	positions() Returns an iterable collection of the tree nodes.
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

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

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 java.lang.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 java.lang.Iterable<Position<E>> positions()

Returns an iterable collection of the tree nodes.

Specified by:

positions in interface Tree<E>

iterator

public java.util.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