/*
*
*
* Developed for use with the book:
*
* Data Structures and Algorithms in Java, Sixth Edition
*
*
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program.
*/
package net.datastructures;

/**
* Concrete implementation of a binary tree using a node-based, linked structure.
*
* @author
* @author
* @author
*/
public class LinkedBinaryTree<E> extends AbstractBinaryTree<E> {

//---------------- nested Node class ----------------
/** Nested static class for a binary tree node. */
protected static class Node<E> implements Position<E> {
private E element;       // an element stored at this node
private Node<E> parent; // a reference to the parent node (if any)
private Node<E> left;    // a reference to the left child (if any)
private Node<E> right;    // a reference to the right child (if any)

/**
* Constructs a node with the given element and neighbors.
*
* @param e the element to be stored
* @param above    reference to a parent node
* @param leftChild reference to a left child node
* @param rightChild reference to a right child node
*/
public Node(E e, Node<E> above, Node<E> leftChild, Node<E> rightChild) {
   element = e;
   parent = above;
   left = leftChild;
   right = rightChild;
}

// accessor methods
public E getElement() { return element; }
public Node<E> getParent() { return parent; }
public Node<E> getLeft() { return left; }
public Node<E> getRight() { return right; }

// update methods
public void setElement(E e) { element = e; }
public void setParent(Node<E> parentNode) { parent = parentNode; }
public void setLeft(Node<E> leftChild) { left = leftChild; }
public void setRight(Node<E> rightChild) { right = rightChild; }
} //----------- end of nested Node class -----------

/** Factory function to create a new node storing element e. */
protected Node<E> createNode(E e, Node<E> parent,
                              Node<E> left, Node<E> right) {
return new Node<E>(e, parent, left, right);
}

// LinkedBinaryTree instance variables
/** The root of the binary tree */
protected Node<E> root = null; // root of the tree

/** The number of nodes in the binary tree */
private int size = 0;          // number of nodes in the tree

// constructor
/** Construts an empty binary tree. */
public LinkedBinaryTree() { }    // constructs an empty binary tree

// nonpublic utility
/**
* 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.
*
* @param p a Position (that should belong to this tree)
* @return the underlying Node instance for the position
* @throws IllegalArgumentException if an invalid position is detected
*/
protected Node<E> validate(Position<E> p) throws IllegalArgumentException {
if (!(p instanceof Node))
   throw new IllegalArgumentException("Not valid position type");
Node<E> node = (Node<E>) p;    // safe cast
if (node.getParent() == node) // our convention for defunct node
   throw new IllegalArgumentException("p is no longer in the tree");
return node;
}

// accessor methods (not already implemented in AbstractBinaryTree)
/**
* Returns the number of nodes in the tree.
* @return number of nodes in the tree
*/
@Override
public int size() {
return size;
}

/**
* Returns the root Position of the tree (or null if tree is empty).
* @return root Position of the tree (or null if tree is empty)
*/
@Override
public Position<E> root() {
return root;
}

/**
* Returns the Position of p's parent (or null if p is root).
*
* @param p A valid Position within the tree
* @return Position of p's parent (or null if p is root)
* @throws IllegalArgumentException if p is not a valid Position for this tree.
*/
@Override
public Position<E> parent(Position<E> p) throws IllegalArgumentException {
Node<E> node = validate(p);
return node.getParent();
}

/**
* Returns the Position of p's left child (or null if no child exists).
*
* @param p A valid Position within the tree
* @return the Position of the left child (or null if no child exists)
* @throws IllegalArgumentException if p is not a valid Position for this tree
*/
@Override
public Position<E> left(Position<E> p) throws IllegalArgumentException {
Node<E> node = validate(p);
return node.getLeft();
}

/**
* Returns the Position of p's right child (or null if no child exists).
*
* @param p A valid Position within the tree
* @return the Position of the right child (or null if no child exists)
* @throws IllegalArgumentException if p is not a valid Position for this tree
*/
@Override
public Position<E> right(Position<E> p) throws IllegalArgumentException {
Node<E> node = validate(p);
return node.getRight();
}

// update methods supported by this class
/**
* Places element e at the root of an empty tree and returns its new Position.
*
* @param e the new element
* @return the Position of the new element
* @throws IllegalStateException if the tree is not empty
*/
public Position<E> addRoot(E e) throws IllegalStateException {
if (!isEmpty()) throw new IllegalStateException("Tree is not empty");
root = createNode(e, null, null, null);
size = 1;
return root;
}

/**
* Creates a new left child of Position p storing element e and returns its Position.
*
* @param p the Position to the left of which the new element is inserted
* @param e the new element
* @return the Position of the new element
* @throws IllegalArgumentException if p is not a valid Position for this tree
* @throws IllegalArgumentException if p already has a left child
*/
public Position<E> addLeft(Position<E> p, E e)
                     throws IllegalArgumentException {
Node<E> parent = validate(p);
if (parent.getLeft() != null)
   throw new IllegalArgumentE

The original U.S. income tax of 1913 was quite simple. The tax was...