AbstractNode

package Ch0.Utilities;

public abstract class AbstractNode<E extends Element, U extends AbstractNode<E, U>> {
	private U parent;
	private U left;
	private U right;
	private E data;

	public AbstractNode(U parent, E data) {
		this.parent = parent;
		this.data = data;
	}

	public U getParent() {
		return parent;
	}

	public void setParent(U parent) {
		this.parent = parent;
	}

	public U getLeft() {
		return left;
	}

	public void setLeft(U left) {
		this.left = left;
	}

	public U getRight() {
		return right;
	}

	public void setRight(U right) {
		this.right = right;
	}

	public E getData() {
		return data;
	}

	public void setData(E data) {
		this.data = data;
	}

}

BinarySearchTree

public class BinarySearchTree<Element> extends Tree<Element, Node<Element>> {

	@Override
	public Node<Element> searchIterative(Node<Element> n, int key) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Node<Element> getMinimum(Node<Element> n) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Node<Element> getMaximum(Node<Element> n) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Node<Element> getMinimumIterative(Node<Element> n) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Node<Element> getMaximumIterative(Node<Element> n) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Node<Element> getPredecessor(Node<Element> n) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Node<Element> getSuccessor(Node<Element> n) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Node<Element> insert(Element e, Node<Element> cRoot) {
		// TODO Auto-generated method stub
		return null;
	}
	
		@Override
	public void delete(Element e) {
		Node<Element> z = search(root, e.getIntegerData());
		if (z == null) {
			return;
		}
		if (z.getLeft() == null) {
			transplant(z, z.getRight());
		} else if (z.getRight() == null) {
			transplant(z, z.getLeft());
		} else {
			Node<Element> y = getMinimum(z.getRight());
			if (y.getParent() != z) {
				transplant(y, y.getRight());
				y.setRight(z.getRight());
				y.getRight().setParent(y);
			}
			transplant(z, y);
			y.setLeft(z.getLeft());
			y.getLeft().setParent(y);
		}
	}
}

Element

package Ch0.Utilities;

public class Element implements Cloneable {
	private String stringData;
	private int integerData;

	public Element(String stringData) {
		super();
		this.stringData = stringData;
	}

	public Element(int integerData) {
		super();
		this.integerData = integerData;
	}

	public Element(Element element) {
		this.stringData = element.stringData;
	}

	public String getStringData() {
		return stringData;
	}

	public int getIntegerData() {
		return integerData;
	}

	public void setIntegerData(int integerData) {
		this.integerData = integerData;
	}

	public void setStringData(String stringData) {
		this.stringData = stringData;
	}

	public static Element DELETED_ELEMENT() {
		return new Element("DELETED");
	}

	public Element clone() {
		return new Element(this);
	}

}

Node

package Ch12.BinarySearchTrees;

import Ch0.Utilities.AbstractNode;
import Ch0.Utilities.Element;

public class Node<E extends Element> extends AbstractNode<E, Node<E>> {

	public Node(Node<E> parent, E data) {
		super(parent, data);
	}

}

Tree

package Ch12.BinarySearchTrees;

import Ch0.Utilities.AbstractNode;
import Ch0.Utilities.Element;

public abstract class Tree<E extends Element, T extends AbstractNode<E, T>> {

	protected T root;

	public T getRoot() {
		return this.root;
	}

	public abstract T search(T n, int key);

	public abstract T searchIterative(T n, int key);

	public abstract T getMinimum(T n);

	public abstract T getMaximum(T n);

	public abstract T getMinimumIterative(T n);

	public abstract T getMaximumIterative(T n);

	public abstract T getPredecessor(T n);

	public abstract T getSuccessor(T n);

	public abstract T insert(E e, T cRoot);

	public abstract void insertIterative(E n);

	public abstract void delete(E e);

	public void preorderWalk(T n) {
		if (n != null) {
			System.out.print(n.getData().getIntegerData() + " ");
			preorderWalk((T) n.getLeft());
			preorderWalk((T) n.getRight());
		}
	}

	public void inorderWalk(T n) {
		if (n != null) {
			inorderWalk((T) n.getLeft());
			System.out.print(n.getData().getIntegerData() + " ");
			inorderWalk((T) n.getRight());
		}
	}

	public void postorderWalk(T n) {
		if (n != null) {
			postorderWalk((T) n.getLeft());
			postorderWalk((T) n.getRight());
			System.out.print(n.getData().getIntegerData() + " ");
		}
	}

	public void transplant(T u, T v) {
		if (u.getParent() == null)
			root = v;
		else if (u == u.getParent().getLeft()) {
			u.getParent().setLeft(v);
		} else {
			u.getParent().setRight(v);
		}
		if (v != null) {
			v.setParent(u.getParent());
		}
	}

	public void prettyPrint(T root, int recLevel) {
		if (root == null) {
			recLevel--; // reached leaf, must decrement recurence level
			return;
		}
		recLevel++; // otherwise increment it
		prettyPrint((T) root.getRight(), recLevel); // keep going right in the
													// tree
		int j = 0;

		// print spaces for the appropriate recurence level
		for (j = 0; j < recLevel - 1; j++) {
			System.out.print("     ");
		}
		// then print value
		System.out.print(root.getData().getIntegerData());

		// print a new line
		System.out.println();

		prettyPrint((T) root.getLeft(), recLevel); // keep going left in the
													// tree
	}

}