Package dsa.lab06.solutions

Class BinaryTree<Item>

java.lang.Object

dsa.lab06.solutions.BinaryTree<Item>

Type Parameters:

Item - the item type

All Implemented Interfaces:

Container<Item>, Iterable<Item>

public class BinaryTree<Item>
extends Object
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.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static enum	BinaryTree.IterationOrder
static class	BinaryTree.Node<Item>	A node in a binary tree.
static class	BinaryTree.NodeIterator<Item>

Constructor Summary

Constructors

Constructor	Description
BinaryTree()	Construct an empty binary tree.
BinaryTree(Item... items)	Construct a binary tree containing the given items.
BinaryTree(Iterable<Item> items)	Construct a binary tree containing the given items.
BinaryTree(Iterable<Item> items, int size)	Construct a binary tree containing the given items more efficiently than BinaryTree(Iterable).

Method Summary

Modifier and Type	Method	Description
static <Item> BinaryTree<Item>	buildInOrder(Item... items)
static <Item> BinaryTree<Item>	buildInOrder(Iterable<Item> items)
static <Item> BinaryTree<Item>	buildInOrder(Iterable<Item> items, int size)
int	height()	Get the number of levels below the root of the tree.
Iterable<Item>	inOrder()
Iterable<BinaryTree.Node<Item>>	inOrderNodes()
void	insertRoot(BinaryTree.Node<Item> root)	Insert the given node as the root.
boolean	isEmpty()	Check if it's empty.
Iterable<Item>	items()	Get an iterable that yields each item once.
Iterable<Item>	postOrder()
Iterable<BinaryTree.Node<Item>>	postOrderNodes()
Iterable<Item>	preOrder()
Iterable<BinaryTree.Node<Item>>	preOrderNodes()
void	printInOrder()
void	printPostOrder()
void	printPreOrder()
BinaryTree.Node<Item>	removeRoot()	Remove and return the root.
Iterable<Item>	reverseInOrder()
Iterable<BinaryTree.Node<Item>>	reverseInOrderNodes()
Iterable<Item>	reversePostOrder()
Iterable<BinaryTree.Node<Item>>	reversePostOrderNodes()
Iterable<Item>	reversePreOrder()
Iterable<BinaryTree.Node<Item>>	reversePreOrderNodes()
BinaryTree.Node<Item>	root()	Get the root node.
int	size()	Get the number of contained items.
String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface dsa.lab02.base.Container

contains, iterator

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Details

BinaryTree

public BinaryTree()

Construct an empty binary tree.

BinaryTree

public BinaryTree(Iterable<Item> items)

Construct a binary tree containing the given items.

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).

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.

Parameters:

items - the items

Method Details

buildInOrder

public static <Item> BinaryTree<Item> buildInOrder(Iterable<Item> items)

buildInOrder

public static <Item> BinaryTree<Item> buildInOrder(Iterable<Item> items,
 int size)

buildInOrder

@SafeVarargs
public static <Item> BinaryTree<Item> buildInOrder(Item... 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()

toString

public String toString()

Overrides:

toString in class Object

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