Package dsa.impl

Class AbstractBinaryTree<T>

java.lang.Object
dsa.impl.AbstractBinaryTree<T>
All Implemented Interfaces:
IBinaryTree<T>, ITree<T>

public abstract class AbstractBinaryTree<T> extends Object implements IBinaryTree<T>
  • Field Details

  • Constructor Details

    • AbstractBinaryTree

      public AbstractBinaryTree()
  • Method Details

    • root

      public IPosition<T> root()
      Description copied from interface: ITree
      Get the root position of the tree.
      Specified by:
      root in interface ITree<T>
      Returns:
      The position object at the tree root.
    • parent

      public IPosition<T> parent(IPosition<T> p)
      Description copied from interface: ITree
      Get the parent of position p (or null if the position has no parent (i.e. is the root).
      Specified by:
      parent in interface ITree<T>
      Parameters:
      p -
      Returns:
      The IPosition representing the parent of p, or null if p is the root.
    • children

      public Iterator<IPosition<T>> children(IPosition<T> p)
      Description copied from interface: ITree
      Get an Iterator to iterate over the child positions of p.
      Specified by:
      children in interface ITree<T>
      Parameters:
      p -
      Returns:
    • isInternal

      public boolean isInternal(IPosition<T> p)
      Description copied from interface: ITree
      Test whether position p is internal (i.e. has children).
      Specified by:
      isInternal in interface ITree<T>
      Parameters:
      p -
      Returns:
    • isExternal

      public boolean isExternal(IPosition<T> p)
      Description copied from interface: ITree
      Test whether position p is external (i.e. has no children).
      Specified by:
      isExternal in interface ITree<T>
      Parameters:
      p -
      Returns:
    • isRoot

      public boolean isRoot(IPosition<T> p)
      Description copied from interface: ITree
      Test whether position p is the root of the tree.
      Specified by:
      isRoot in interface ITree<T>
      Parameters:
      p -
      Returns:
      true if p is the root, false otherwise.
    • size

      public int size()
      Description copied from interface: ITree
      Get the size of the tree (i.e. the number of positions it contains).
      Specified by:
      size in interface ITree<T>
      Returns:
    • isEmpty

      public boolean isEmpty()
      Description copied from interface: ITree
      Test whether the tree is empty.
      Specified by:
      isEmpty in interface ITree<T>
      Returns:
      true if the size()==0, @{code false} otherwise.
    • iterator

      public Iterator<T> iterator()
      Description copied from interface: ITree
      Get an Iterator that iterates over all the elements contained in the tree's positions.
      Specified by:
      iterator in interface ITree<T>
      Returns:
    • positions

      public Iterator<IPosition<T>> positions()
      Description copied from interface: ITree
      Get an Iterator that iterates over all the positions in the tree.
      Specified by:
      positions in interface ITree<T>
      Returns:
    • replace

      public T replace(IPosition<T> p, T e)
      Description copied from interface: ITree
      Replace the element contained in a position.
      Specified by:
      replace in interface ITree<T>
      Parameters:
      p - A position in the tree.
      e - The new element to store in p.
      Returns:
      The element that was formerly contained in the position before replacement.
    • left

      public IPosition<T> left(IPosition<T> p)
      Description copied from interface: IBinaryTree
      Get the left child of position p.
      Specified by:
      left in interface IBinaryTree<T>
      Parameters:
      p -
      Returns:
    • right

      public IPosition<T> right(IPosition<T> p)
      Description copied from interface: IBinaryTree
      Get the right child of position p.
      Specified by:
      right in interface IBinaryTree<T>
      Parameters:
      p -
      Returns:
    • hasLeft

      public boolean hasLeft(IPosition<T> p)
      Description copied from interface: IBinaryTree
      Check whether position p has a left child.
      Specified by:
      hasLeft in interface IBinaryTree<T>
      Parameters:
      p -
      Returns:
      true if position p has a left child, false otherwise.
    • hasRight

      public boolean hasRight(IPosition<T> p)
      Description copied from interface: IBinaryTree
      Check whether position p has a right child.
      Specified by:
      hasRight in interface IBinaryTree<T>
      Parameters:
      p -
      Returns:
      true if position p has a right child, false otherwise.
    • toString

      public String toString()
      Overrides:
      toString in class Object
    • newPosition

      protected AbstractBinaryTree<T>.BTPosition newPosition(T element, AbstractBinaryTree<T>.BTPosition parent)