oink

package info3;/** *  * Info 3 Blatt 3, Aufgabe 2 *  * @author fieberfn, hatjeki * * <p> * Class that implements a binary search tree. Elements smaller than the one * looked at come to the left. If you insert an element already contained it * will come to the right. Implemented functions are contains and insert. * Contains and insert are implemented with variable parameter lists. * </p> */public class BinarySearchTree<T extends Comparable<T>> {		private BinaryTree<T> anchor;	BinarySearchTree() {	}		public boolean isEmpty () {		return anchor == null;	}		public void insert (T Item) {		if (anchor == null) {			anchor = new BinaryTree<T> (Item);		} else {			insert(Item, anchor);		}	}		public boolean contains (T param) {		return contains (param, anchor);	}		public boolean delete (T param) {		return myDelete (param);	}		public boolean putInorder () {		return putInorder(anchor);	}	public void insert (T... params) {		for (T element : params) {			insert (element);		}	}		//	public boolean delTree () {//		//anchor = null;//		delTree(anchor);//		return true;//	}	/*	public java.util.LinkedList contains (T... params) {		java.util.LinkedList<T> contained = new java.util.LinkedList<T>(); 		for (T param : params) {			if (contains (param)) {				contained.add(param);			}		}		return contained;	}*/		public boolean[] contains (T... params) {		boolean contained[] = new boolean[params.length];		for (int i = 0; i < params.length; i++) {			if (contains (params[i])) {				contained[i] = true;			}		}		return contained;	}		public boolean[] delete (T... params) {		boolean deleted[] = new boolean[params.length];		for (int i = 0; i < params.length; i++) {			if (delete (params[i])) {				deleted[i] = true;			}		}		return deleted;	}			private void insert (T Item, BinaryTree<T> tree) {		if (Item.compareTo(tree.Item) < 0) {			if (tree.left == null) {				tree.left = new BinaryTree<T>(Item);			} else {				insert (Item, tree.left);			}		} else {			if (tree.right == null) {				tree.right = new BinaryTree<T>(Item);			} else {				insert (Item, tree.right);			}		}	}		private boolean contains (T param, BinaryTree<T> tree) {		if (tree != null) {			if (tree.Item.equals(param)) {				return true;			} else if (param.compareTo(tree.Item) < 0) {				return contains (param, tree.left);			} else {				return contains (param, tree.right);			}		}		return false;	}	private boolean putInorder (BinaryTree<T> tree) {		if (anchor != null) {			if (tree != null) { 				putInorder(tree.left);				System.out.print(tree.Item+" ");				putInorder(tree.right);			}			return true;		} else {			return false;		}	}	private boolean myDelete (T elem) {		BinaryTree<T> cursor = anchor;		BinaryTree<T> parentNode = null;		BinaryTree<T> successor = null;		BinaryTree<T> tmpParent = null;		boolean left  = false;				// durchsuche Baum		while ((cursor != null) && (!cursor.Item.equals (elem))){			if (elem.compareTo(cursor.Item) > 0) {				parentNode = cursor;				cursor = cursor.right;				left = false;			} else {				parentNode = cursor;				cursor = cursor.left;				left = true;			}		}				// falls Element nicht im Baum, gebe false zurueck		if (cursor == null) {			return false;		} else {			// falls Knoten keine Kinder hat, loesche diesen			if ((cursor.left == null) & (cursor.right == null)) {				if (parentNode != null) {					if (left) {						parentNode.left = null;					} else {						parentNode.right = null;					}					cursor = null;				} else {					anchor = null;				}			} else {								// falls nur ein rechter Kindknoten				if (cursor.left == null) {					// falls Knoten Wurzel ist					if (parentNode == null) {						// setze rechtes Kind als Wurzel						anchor = cursor.right;						} else {						// ansonsten ueberspringe zu loeschenden Knoten 						if (left) {							parentNode.left = cursor.right;						} else {							parentNode.right = cursor.right;						}					}					cursor = null;				} else {					// falls nur ein linker Kindknoten					if (cursor.right == null) {						// falls Knoten Wurzel ist						if (parentNode == null) {							// setze linkes Kind als Wurzel							anchor = cursor.left;							} else {							// ansonsten ueberspringe zu loeschenden Knoten 							if (left) {								parentNode.left = cursor.left;							} else {								parentNode.right = cursor.left;							}						}						cursor = null;					} else {						// falls Knoten zwei Kinder hat, suche Inordernachfolger						successor = cursor.right;						tmpParent = null;						while (successor.left != null) {							tmpParent = successor;							successor = successor.left;						}												if (tmpParent != null) tmpParent.left = null;												// setze Inordernachfolger an Stelle des zu loeschenden Knotens						if (parentNode == null) {							anchor = successor;						} else {							if (left) {								parentNode.left = successor;							} else {								parentNode.right = successor;							}						}						// haenge linken Teilbaum des zu loeschenden Knotens links						// an Inordernachfolger						successor.left = cursor.left;												// haenge rechten Teilbaum des zu loeschenden Knotens rechts						// an den Inordernachfolgerbaum					    if (successor != cursor.right) {					    	tmpParent = successor;					    	while (tmpParent.right != null) tmpParent = tmpParent.right;					    	tmpParent.right = cursor.right;					    }					    cursor = null;					}				}							}					}				return true;	}		/**	 * @param args	 */	public static void main(String[] args) {				BinarySearchTree<Integer> Baum = new BinarySearchTree<Integer>();				Baum.insert (5);		Baum.insert (2);		Baum.insert (3);		Baum.insert (1);		Baum.insert (7);		Baum.insert (6);		Baum.insert (10);		Baum.insert (8);		Baum.insert (9);		Baum.putInorder ();				System.out.println();				Baum.myDelete (5);		Baum.putInorder ();	}}