Create a gist now

Instantly share code, notes, and snippets.

@Alex-Cosma /AbstractNode Secret
Created Jun 10, 2015

Embed
What would you like to do?
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;
}
}
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);
}
}
}
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);
}
}
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);
}
}
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
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment