Package dsa.lab06.exercises

Class BinaryTree<Item>

java.lang.Object
dsa.lib.DSAObject
dsa.lab06.exercises.BinaryTree<Item>
Type Parameters:
Item - the item type
All Implemented Interfaces:
Container<Item>, dsa.lib.DSAInterface, Iterable<Item>
public class BinaryTree<Item> extends dsa.lib.DSAObject implements Container<Item>
A binary tree.

This implementation is designed for binary trees that are built bottom-up. It will work in other cases, just less efficiently.

  • Constructor Details

    • BinaryTree

      public BinaryTree()
      Construct an empty binary tree.

    • BinaryTree

      public BinaryTree(Iterable<Item> items)
      Construct a binary tree containing the given items.

      The binary tree will be complete, and a pre-order traversal of it will yield the same items in the same order as supplied.

      For example, given the items [a, b, c, d, e, f], the tree will be [[[d] b [e]] a [[f] c []]].

      Parameters:
      items - the items

    • BinaryTree

      public BinaryTree(Iterable<Item> items, int size) throws IllegalArgumentException
      Construct a binary tree containing the given items more efficiently than BinaryTree(Iterable).

      The binary tree will be complete, and a pre-order traversal of it will yield the same items in the same order as supplied.

      For example, given the items [a, b, c, d, e, f], the tree will be [[[d] b [e]] a [[f] c []]].

      Parameters:
      items - the items
      size - the number of items
      Throws:
      IllegalArgumentException - if size != n (where n is items's size)

    • BinaryTree

      @SafeVarargs public BinaryTree(Item... items)
      Construct a binary tree containing the given items.

      The binary tree will be complete, and a pre-order traversal of it will yield the same items in the same order as supplied.

      For example, given the items [a, b, c, d, e, f], the tree will be [[[d] b [e]] a [[f] c []]].

      Parameters:
      items - the items

  • Method Details

    • buildInOrder

      public static <Item> BinaryTree<Item> buildInOrder(Iterable<Item> items)
      Construct a binary tree containing the given items.

      The binary tree will be complete, and an in-order traversal of it will yield the same items in the same order as supplied.

      For example, given the items [a, b, c, d, e, f], the tree will be [[[a] b [c]] d [[e] f []]].

      Parameters:
      items - the items

    • buildInOrder

      public static <Item> BinaryTree<Item> buildInOrder(Iterable<Item> items, int size) throws IllegalArgumentException
      Construct a binary tree containing the given items more efficiently than buildInOrder(Iterable).

      The binary tree will be complete, and an in-order traversal of it will yield the same items in the same order as supplied.

      For example, given the items [a, b, c, d, e, f], the tree will be [[[a] b [c]] d [[e] f []]].

      Parameters:
      items - the items
      size - the number of items
      Throws:
      IllegalArgumentException - if size != n (where n is items's size)

    • buildInOrder

      @SafeVarargs public static <Item> BinaryTree<Item> buildInOrder(Item... items)
      Construct a binary tree containing the given items.

      The binary tree will be complete, and an in-order traversal of it will yield the same items in the same order as supplied.

      For example, given the items [a, b, c, d, e, f], the tree will be [[[a] b [c]] d [[e] f []]].

      Parameters:
      items - the items

    • root

      public BinaryTree.Node<Item> root()
      Get the root node.

      If there is none (i.e. it is empty), returns null.

      Returns:
      the root node

    • insertRoot

      public void insertRoot(BinaryTree.Node<Item> root) throws IllegalStateException, IllegalArgumentException
      Insert the given node as the root.
      Parameters:
      root - the new root
      Throws:
      IllegalStateException - if there's already a root, or
      IllegalArgumentException - if the one given already has a parent or is in a different tree

    • removeRoot

      public BinaryTree.Node<Item> removeRoot() throws NoSuchElementException
      Remove and return the root.
      Returns:
      the old root
      Throws:
      NoSuchElementException - if there is no root

    • height

      public int height()
      Get the number of levels below the root of the tree.

      If the tree is empty, returns -1, otherwise returns a non-negative integer.

      Returns:
      the height

    • size

      public int size()
      Description copied from interface: Container
      Get the number of contained items.
      Specified by:
      size in interface Container<Item>
      Returns:
      the size

    • isEmpty

      public boolean isEmpty()
      Description copied from interface: Container
      Check if it's empty.
      Specified by:
      isEmpty in interface Container<Item>
      Returns:
      whether there are no items

    • printPreOrder

      public void printPreOrder()

    • printInOrder

      public void printInOrder()

    • printPostOrder

      public void printPostOrder()

    • preOrderNodes

      public Iterable<BinaryTree.Node<Item>> preOrderNodes()

    • inOrderNodes

      public Iterable<BinaryTree.Node<Item>> inOrderNodes()

    • postOrderNodes

      public Iterable<BinaryTree.Node<Item>> postOrderNodes()

    • reversePreOrderNodes

      public Iterable<BinaryTree.Node<Item>> reversePreOrderNodes()

    • reverseInOrderNodes

      public Iterable<BinaryTree.Node<Item>> reverseInOrderNodes()

    • reversePostOrderNodes

      public Iterable<BinaryTree.Node<Item>> reversePostOrderNodes()

    • preOrder

      public Iterable<Item> preOrder()

    • inOrder

      public Iterable<Item> inOrder()

    • postOrder

      public Iterable<Item> postOrder()

    • reversePreOrder

      public Iterable<Item> reversePreOrder()

    • reverseInOrder

      public Iterable<Item> reverseInOrder()

    • reversePostOrder

      public Iterable<Item> reversePostOrder()

    • items

      public Iterable<Item> items()
      Description copied from interface: Container
      Get an iterable that yields each item once.
      Specified by:
      items in interface Container<Item>
      Returns:
      an iterable over the items

    • toCompactString

      public String toCompactString()

    • toString

      public String toString(String indent)
      Specified by:
      toString in interface Container<Item>
      Specified by:
      toString in interface dsa.lib.DSAInterface