BinarySearchTree.java

public class BinarySearchTree<T extends Comparable> {
	 private class Node {
		 private T mContent;
		 private Node mLeft, mRight;
		 
		 public Node(T content, Node left, Node right) {
			 mContent = content;
			 mLeft = left;
			 mRight = right;
		 }
		 
		 public Node(T content) {
			 this(content, new Node(), new Node());
		 }
		 
		 public Node() {
			 this(null, null, null);
		 }
		 
		 public Node getLeft() {
			 return mLeft;
		 }
		 
		 public void setLeft(Node left) {
			 mLeft = left;
		 }
		 
		 public Node getRight() {
			 return mRight;
		 }
		 
		 public void setRight(Node right) {
			 mRight = right;
		 }
		 
		 public T getContent() {
			 return mContent;
		 }
		 
		 public void setContent(T content) {
			 mContent = content;
		 }
		 
		 public boolean hasLeft() {
			 return mLeft != null && !mLeft.empty();
		 }
		 
		 public boolean hasRight() {
			 return mRight != null && !mRight.empty();
		 }
		 
		 public boolean empty() {
			 return getContent() == null;
		 }
		 
		 public void printPreOrder(int level, Node start, String mark) {
			 if (start == null || start.empty()) return;
			 for (int i = 0; i < level; i++) System.out.print("-");
			 System.out.println(start.getContent() + " " + mark);
			 printPreOrder(level+1, start.getLeft(), "left");
			 printPreOrder(level+1, start.getRight(), "right");
		 }
	 }
	 
	 private Node mRoot;
	 
	 public BinarySearchTree(T content) {
		 mRoot = new Node(content, null, null);
	 }
	 
	 public Node search(T value) {
		 Node active = mRoot;
		 
		 while (!active.empty()) {
			 switch (value.compareTo(active.getContent())) {
			 case 0:
				 return active;
			 case 1:
				 active = active.getRight();
				 break;
			 case -1:
				 active = active.getLeft();
				 break;
			 }
		 }
		 
		 return new Node();
	 }
	 
	 public void insert(T value) {
		 Node active = mRoot;
		 
		 while (!active.empty()) {
			 switch (value.compareTo(active.getContent())) {
			 case 0:
				 return;
			 case 1:
				 if (active.hasRight()) {
					 active = active.getRight();
				 } else {
					 active.setRight(new Node(value));
					 return;
				 }
				 break;
			 case -1:
				 if (active.hasLeft()) {
					 active = active.getLeft();
				 } else {
					 active.setLeft(new Node(value));
					 return;
				 }
				 break;
			 }
		 }
	 }
	 
	 public Node findMax(Node root) {
		 while (!root.empty()) {
			 if (root.hasRight()) {
				 root = root.getRight();
			 } else {
				 return root;
			 }
		 }
		 return new Node();
	 }
	 
	 public void remove(T value) {
		 // suche nach knoten
		 Node drop = search(value);
		 if (drop == null) return;
		 
		 // kein kind
		 if (drop.hasLeft()) {
			 if (drop.hasRight()) {
				 T maxValue = findMax(drop.getLeft()).getContent();
				 remove(maxValue);
				 drop.setContent(maxValue);
			 } else {
				 T leftValue = drop.getLeft().getContent();
				 remove(leftValue);
				 drop.setContent(leftValue);
			 }
		 } else if (drop.hasRight()) {
			 T rightValue = drop.getRight().getContent();
			 remove(rightValue);
			 drop.setContent(rightValue);
		 } else {
			 drop.setContent(null);
		 }
	 }
	 
	 public void printInOrder() {
		 mRoot.printPreOrder(1, mRoot, "root");
	 }
}