public class LinkedBinaryTree<E> extends AbstractBinaryTree<E>
| Modifier and Type | Class and Description |
|---|---|
protected static class |
LinkedBinaryTree.Node<E>
Nested static class for a binary tree node.
|
| Modifier and Type | Field and Description |
|---|---|
protected LinkedBinaryTree.Node<E> |
root
The root of the binary tree
|
| Constructor and Description |
|---|
LinkedBinaryTree()
Construts an empty binary tree.
|
| Modifier and Type | Method and 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.
|
children, inorder, numChildren, positions, siblingbreadthfirst, depth, height, isEmpty, isExternal, isInternal, isRoot, iterator, postorder, preorderclone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, waitisEmpty, isExternal, isInternal, isRoot, iteratorprotected LinkedBinaryTree.Node<E> root
protected LinkedBinaryTree.Node<E> createNode(E e, LinkedBinaryTree.Node<E> parent, LinkedBinaryTree.Node<E> left, LinkedBinaryTree.Node<E> right)
protected LinkedBinaryTree.Node<E> validate(Position<E> p) throws IllegalArgumentException
p - a Position (that should belong to this tree)IllegalArgumentException - if an invalid position is detectedpublic int size()
public Position<E> root()
public Position<E> parent(Position<E> p) throws IllegalArgumentException
p - A valid Position within the treeIllegalArgumentException - if p is not a valid Position for this tree.public Position<E> left(Position<E> p) throws IllegalArgumentException
p - A valid Position within the treeIllegalArgumentException - if p is not a valid Position for this treepublic Position<E> right(Position<E> p) throws IllegalArgumentException
p - A valid Position within the treeIllegalArgumentException - if p is not a valid Position for this treepublic Position<E> addRoot(E e) throws IllegalStateException
e - the new elementIllegalStateException - if the tree is not emptypublic Position<E> addLeft(Position<E> p, E e) throws IllegalArgumentException
p - the Position to the left of which the new element is insertede - the new elementIllegalArgumentException - if p is not a valid Position for this treeIllegalArgumentException - if p already has a left childpublic Position<E> addRight(Position<E> p, E e) throws IllegalArgumentException
p - the Position to the right of which the new element is insertede - the new elementIllegalArgumentException - if p is not a valid Position for this tree.IllegalArgumentException - if p already has a right childpublic E set(Position<E> p, E e) throws IllegalArgumentException
p - the relevant Positione - the new elementIllegalArgumentException - if p is not a valid Position for this tree.public void attach(Position<E> p, LinkedBinaryTree<E> t1, LinkedBinaryTree<E> t2) throws IllegalArgumentException
p - a leaf of the treet1 - an independent tree whose structure becomes the left child of pt2 - an independent tree whose structure becomes the right child of pIllegalArgumentException - if p is not a valid Position for this treeIllegalArgumentException - if p is not a leafpublic E remove(Position<E> p) throws IllegalArgumentException
p - the relevant PositionIllegalArgumentException - if p is not a valid Position for this tree.IllegalArgumentException - if p has two children.