Package com.zybooks.dsaj.tree

Class AbstractTree<E>

java.lang.Object
com.zybooks.dsaj.tree.AbstractTree<E>
Type Parameters:
E - Element to be stored at each position of the tree.
All Implemented Interfaces:
Tree<E>, Iterable<E>
Direct Known Subclasses:
AbstractBinaryTree
public abstract class AbstractTree<E> extends Object implements Tree<E>
An abstract base class providing some functionality of the Tree interface. The following three methods remain abstract, and must be implemented by a concrete subclass: root, parent, children. Other methods implemented in this class may be overridden to provide a more direct and efficient implementation.

  • Constructor Details

    • AbstractTree

      public AbstractTree()

  • Method Details

    • isInternal

      public boolean isInternal(Position<E> p)
      Returns true if Position p has one or more children.
      Specified by:
      isInternal in interface Tree<E>
      Parameters:
      p - A valid Position within the tree
      Returns:
      true if p has at least one child, false otherwise
      Throws:
      IllegalArgumentException - if p is not a valid Position for this tree.

    • isExternal

      public boolean isExternal(Position<E> p)
      Returns true if Position p does not have any children.
      Specified by:
      isExternal in interface Tree<E>
      Parameters:
      p - A valid Position within the tree
      Returns:
      true if p has zero children, false otherwise
      Throws:
      IllegalArgumentException - if p is not a valid Position for this tree.

    • isRoot

      public boolean isRoot(Position<E> p)
      Returns true if Position p represents the root of the tree.
      Specified by:
      isRoot in interface Tree<E>
      Parameters:
      p - A valid Position within the tree
      Returns:
      true if p is the root of the tree, false otherwise

    • numChildren

      public int numChildren(Position<E> p)
      Returns the number of children of Position p.
      Specified by:
      numChildren in interface Tree<E>
      Parameters:
      p - A valid Position within the tree
      Returns:
      number of children of Position p
      Throws:
      IllegalArgumentException - if p is not a valid Position for this tree.

    • size

      public int size()
      Returns the number of nodes in the tree.
      Specified by:
      size in interface Tree<E>
      Returns:
      number of nodes in the tree

    • isEmpty

      public boolean isEmpty()
      Tests whether the tree is empty.
      Specified by:
      isEmpty in interface Tree<E>
      Returns:
      true if the tree is empty, false otherwise

    • depth

      public int depth(Position<E> p) throws IllegalArgumentException
      Returns the number of levels separating Position p from the root.
      Parameters:
      p - A valid Position within the tree
      Returns:
      the depth of position p
      Throws:
      IllegalArgumentException - if p is not a valid Position for this tree.

    • height

      public int height(Position<E> p) throws IllegalArgumentException
      Returns the height of the subtree rooted at Position p.
      Parameters:
      p - A valid Position within the tree
      Returns:
      the height of the subtree rooted at p
      Throws:
      IllegalArgumentException - if p is not a valid Position for this tree.

    • iterator

      public Iterator<E> iterator()
      Returns an iterator of the elements stored in the tree.
      Specified by:
      iterator in interface Iterable<E>
      Specified by:
      iterator in interface Tree<E>
      Returns:
      iterator of the tree's elements

    • positions

      public Iterable<Position<E>> positions()
      Returns an iterable collection of the positions of the tree.
      Specified by:
      positions in interface Tree<E>
      Returns:
      iterable collection of the tree's positions

    • preorder

      public Iterable<Position<E>> preorder()
      Returns an iterable collection of positions of the tree, reported in preorder.
      Returns:
      iterable collection of the tree's positions in preorder

    • postorder

      public Iterable<Position<E>> postorder()
      Returns an iterable collection of positions of the tree, reported in postorder.
      Returns:
      iterable collection of the tree's positions in postorder

    • breadthfirst

      public Iterable<Position<E>> breadthfirst()
      Returns an iterable collection of positions of the tree in breadth-first order.
      Returns:
      iterable collection of the tree's positions in breadth-first order