Package com.zybooks.dsaj.tree

Class LinkedBinaryTree<E>

java.lang.Object

com.zybooks.dsaj.tree.AbstractTree<E>

com.zybooks.dsaj.tree.AbstractBinaryTree<E>

com.zybooks.dsaj.tree.LinkedBinaryTree<E>

Type Parameters:

E - type of element to be stored at each position of the tree

All Implemented Interfaces:

BinaryTree<E>, Tree<E>, Iterable<E>

Direct Known Subclasses:

TreeMap.BalanceableBinaryTree

public class LinkedBinaryTree<E>
extends AbstractBinaryTree<E>

Concrete implementation of a binary tree using a node-based, linked structure.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	LinkedBinaryTree.Node<E>	Nested static class for a binary tree node.

Field Summary

Fields

Modifier and Type	Field	Description
protected LinkedBinaryTree.Node<E>	root	The root of the binary tree

Constructor Summary

Constructors

Constructor	Description
LinkedBinaryTree()	Construts an empty binary tree.

Method Summary

Modifier and Type	Method	Description
Position<E>	addLeft(Position<E> p, E e)	Creates a new left child of Position p storing element e and returns its Position.
Position<E>	addRight(Position<E> p, E e)	Creates a new right child of Position p storing element e and returns its Position.
Position<E>	addRoot(E e)	Places element e at the root of an empty tree and returns its new Position.
void	attach(Position<E> p, LinkedBinaryTree<E> t1, LinkedBinaryTree<E> t2)	Attaches trees t1 and t2, respectively, as the left and right subtree of the leaf Position p.
protected LinkedBinaryTree.Node<E>	createNode(E e, LinkedBinaryTree.Node<E> parent, LinkedBinaryTree.Node<E> left, LinkedBinaryTree.Node<E> right)	Factory function to create a new node storing element e.
Position<E>	left(Position<E> p)	Returns the Position of p's left child (or null if no child exists).
Position<E>	parent(Position<E> p)	Returns the Position of p's parent (or null if p is root).
E	remove(Position<E> p)	Removes the node at Position p and replaces it with its child, if any.
Position<E>	right(Position<E> p)	Returns the Position of p's right child (or null if no child exists).
Position<E>	root()	Returns the root Position of the tree (or null if tree is empty).
E	set(Position<E> p, E e)	Replaces the element at Position p with element e and returns the replaced element.
int	size()	Returns the number of nodes in the tree.
protected LinkedBinaryTree.Node<E>	validate(Position<E> p)	Verifies that a Position belongs to the appropriate class, and is not one that has been previously removed.

Methods inherited from class com.zybooks.dsaj.tree.AbstractBinaryTree

children, inorder, numChildren, positions, sibling

Methods inherited from class com.zybooks.dsaj.tree.AbstractTree

breadthfirst, depth, height, isEmpty, isExternal, isInternal, isRoot, iterator, postorder, preorder

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Methods inherited from interface com.zybooks.dsaj.tree.Tree

isEmpty, isExternal, isInternal, isRoot, iterator

Field Details

root

protected LinkedBinaryTree.Node<E> root

The root of the binary tree

Constructor Details

LinkedBinaryTree

public LinkedBinaryTree()

Construts an empty binary tree.

Method Details

createNode

protected LinkedBinaryTree.Node<E> createNode(E e,
 LinkedBinaryTree.Node<E> parent,
 LinkedBinaryTree.Node<E> left,
 LinkedBinaryTree.Node<E> right)

Factory function to create a new node storing element e.

validate

protected LinkedBinaryTree.Node<E> validate(Position<E> p)
                                     throws IllegalArgumentException

Verifies that a Position belongs to the appropriate class, and is not one that has been previously removed. Note that our current implementation does not actually verify that the position belongs to this particular list instance.

Parameters:

p - a Position (that should belong to this tree)

Returns:

the underlying Node instance for the position

Throws:

IllegalArgumentException - if an invalid position is detected

size

public int size()

Returns the number of nodes in the tree.

Specified by:

size in interface Tree<E>

Overrides:

size in class AbstractTree<E>

Returns:

number of nodes in the tree

root

public Position<E> root()

Returns the root Position of the tree (or null if tree is empty).

Returns:

root Position of the tree (or null if tree is empty)

parent

public Position<E> parent(Position<E> p)
                   throws IllegalArgumentException

Returns the Position of p's parent (or null if p is root).

Parameters:

p - A valid Position within the tree

Returns:

Position of p's parent (or null if p is root)

Throws:

IllegalArgumentException - if p is not a valid Position for this tree.

left

public Position<E> left(Position<E> p)
                 throws IllegalArgumentException

Returns the Position of p's left child (or null if no child exists).

Parameters:

p - A valid Position within the tree

Returns:

the Position of the left child (or null if no child exists)

Throws:

IllegalArgumentException - if p is not a valid Position for this tree

right

public Position<E> right(Position<E> p)
                  throws IllegalArgumentException

Returns the Position of p's right child (or null if no child exists).

Parameters:

p - A valid Position within the tree

Returns:

the Position of the right child (or null if no child exists)

Throws:

IllegalArgumentException - if p is not a valid Position for this tree

addRoot

public Position<E> addRoot(E e)
                    throws IllegalStateException

Places element e at the root of an empty tree and returns its new Position.

Parameters:

e - the new element

Returns:

the Position of the new element

Throws:

IllegalStateException - if the tree is not empty

addLeft

public Position<E> addLeft(Position<E> p,
 E e)
                    throws IllegalArgumentException

Creates a new left child of Position p storing element e and returns its Position.

Parameters:

p - the Position to the left of which the new element is inserted

e - the new element

Returns:

the Position of the new element

Throws:

IllegalArgumentException - if p is not a valid Position for this tree

IllegalArgumentException - if p already has a left child

addRight

public Position<E> addRight(Position<E> p,
 E e)
                     throws IllegalArgumentException

Creates a new right child of Position p storing element e and returns its Position.

Parameters:

p - the Position to the right of which the new element is inserted

e - the new element

Returns:

the Position of the new element

Throws:

IllegalArgumentException - if p is not a valid Position for this tree.

IllegalArgumentException - if p already has a right child

set

public E set(Position<E> p,
 E e)
      throws IllegalArgumentException

Replaces the element at Position p with element e and returns the replaced element.

Parameters:

p - the relevant Position

e - the new element

Returns:

the replaced element

Throws:

IllegalArgumentException - if p is not a valid Position for this tree.

attach

public void attach(Position<E> p,
 LinkedBinaryTree<E> t1,
 LinkedBinaryTree<E> t2)
            throws IllegalArgumentException

Attaches trees t1 and t2, respectively, as the left and right subtree of the leaf Position p. As a side effect, t1 and t2 are set to empty trees.

Parameters:

p - a leaf of the tree

t1 - an independent tree whose structure becomes the left child of p

t2 - an independent tree whose structure becomes the right child of p

Throws:

IllegalArgumentException - if p is not a valid Position for this tree

IllegalArgumentException - if p is not a leaf

remove

public E remove(Position<E> p)
         throws IllegalArgumentException

Removes the node at Position p and replaces it with its child, if any.

Parameters:

p - the relevant Position

Returns:

element that was removed

Throws:

IllegalArgumentException - if p is not a valid Position for this tree.

IllegalArgumentException - if p has two children.