BinaryTreeNode.java

public abstract class BinaryTreeNode {

	// wartosc w wezle
	protected int dane;
	// prawe i lewe poddrzewo
	protected BinaryTreeNode lewy, prawy;

	public BinaryTreeNode(int dane) {
		this.dane = dane;
	}

	/*
	 * Wypisuje drzewo np. dla drzewa 8 3 5 2 1 4 0 wypisac: 2 3 1 8 4 5 0
	 * wypisz lewe wypisz odstep, wypisz dane, endl wypisz prawe
	 */
	public abstract void print(int poziom);

	// rekurencyjne przeszukuje drzewo BST, zwraca true, jesli znajdzie element
	// o podanej wartosci
	// Metoda ma wypisywać ile wezlow drzewa zostalo odwiedzonych
	public abstract boolean searchBSTRec(int szukany);

	// rekurencyjnie dodaje element do drzewa BST
	public abstract void addBSTRec(int nowy);

	// zwraca pare: wezel zawierajacy poszukiwany element oraz jego poprzednika
	// jesli szukanego elementu nie ma w drzewie, to pierwszym elementem pary
	// jest null
	// jesli pierwszy element pary jest korzeniem (nie ma poprzednika), to
	// drugim elementem pary jest null
	public abstract Pair<BinaryTreeNode, BinaryTreeNode> searchBST(int szukany);

	// korzystajac z searchBST dodaje element do drzewa BST
	public abstract void insertBST(int nowy);

}

GenericBTS.java

public class GenericBTS<T extends Comparable<T>>  implements Comparable<T> {
	protected T dane;
	protected GenericBTS<T> lewy, prawy;


	public GenericBTS(T dane) {
		this.dane = dane;
	}

	public T getDane() {
		return dane;
	}

	public int compareTo(T e) {
	     return getDane().compareTo(e);
	 }

	 public int compareTo(GenericBTS<T> other)
	    {
	        return getDane().compareTo(other.getDane());
	    }

	
	public void print(int poziom) {
		if (lewy != null) {
			lewy.print(poziom + 1);
		}
		for (int i = 0; i < poziom; i++) {
			System.out.print("  ");
			
		}
		System.out.print(this.dane);
		System.out.print("\n");
		if (prawy != null) {
			prawy.print(poziom + 1);
		}
	}

	public boolean searchBSTRec(T szukany) {
		int count = 0;
		GenericBTS<T> x = this;
		GenericBTS<T> y = null;
		while (x != null && x.dane != szukany) {
			y = x;
			if(szukany.compareTo(x.getDane())==1){
				x = x.lewy;
			}else{
				x = x.prawy;
			}
			count++;
		}
		System.out.print("Odwiedzono:" + count);
		return true;
	}

	public Pair<GenericBTS<T>, GenericBTS<T>> searchBST(T szukany) {
		GenericBTS<T> x = this;
		GenericBTS<T> y = null;
		while (x != null && x.dane != szukany) {
			y = x;
			if(szukany.compareTo(x.dane) == -1){
				x = x.lewy;
			}else{
				x = x.prawy;
			}
		}
		return new Pair<GenericBTS<T>, GenericBTS<T>>(x, y);
	}

	public void addBSTRec(T nowy) {
		if (this.dane == nowy) {
			return;
		} else if (nowy.compareTo(this.dane) == -1) {
			if (this.lewy == null) {
				this.lewy = new GenericBTS<T>(nowy);
			} else {
				this.lewy.insertBST(nowy);
			}
		} else {
			if (this.prawy == null) {
				this.prawy = new GenericBTS<T>(nowy);
			} else {
				this.prawy.insertBST(nowy);
			}
		}
	}

	public static void main(String[] args) {
		// .8
		// 3 5
		// 2 1 4 0
		GenericBTS<Integer> a = new GenericBTS<Integer>(8);
		a.insertBST(20);
		a.insertBST(5);
		a.insertBST(30);
		a.insertBST(15);
		a.insertBST(17);
		a.insertBST(25);
		a.insertBST(35);
		a.addBSTRec(40);
		a.print(1);
		assert (a.searchBST(150).first == null);
		assert (a.searchBST(8).second == null);
		assert (a.searchBST(15).second == a.searchBST(20).first);
		assert (a.searchBST(15).first.dane == 15);
		System.out.print("\n-------------\n");
		a.remove(20);
		System.out.print("\n-------------\n");
		a.print(1);
		a.remove(5);
		System.out.print("\n-------------\n");
		a.print(1);
		a.remove(30);
		System.out.print("\n-------------\n");
		a.print(1);
		a.remove(15);
		System.out.print("\n-------------\n");
		a.print(1);
		a.remove(17);
		System.out.print("\n-------------\n");
		a.print(1);
		a.remove(25);
		System.out.print("\n-------------\n");
		a.print(1);
		a.remove(35);
		System.out.print("\n-------------\n");
		a.print(1);
		a.remove(40);
		System.out.print("\n-------------\n");
		a.print(1);
		System.out.print("\n-------------\n");
		a.print(1);
	}

	public void insertBST(T nowy) {
		Pair<GenericBTS<T>, GenericBTS<T>> pair = this.searchBST(nowy);
		if (pair.first != null) {
			return;
		} else if (nowy.compareTo(pair.second.dane) == -1) {
			pair.second.lewy = new GenericBTS<T>(nowy);
		} else {
			pair.second.prawy = new GenericBTS<T>(nowy);
		}
	};

	private static boolean random() {
		return Math.random() < 0.5;
	}

	private boolean replace(GenericBTS<T> child, GenericBTS<T> niu) {
		if (this.lewy == child) { // usuwamy od rodzica z lewej
			this.lewy = niu;
			return true;
		} else if (this.prawy == child) { // usuwamy od rodzica z prawej rodzica
			this.prawy= niu;
			return true;
		}
		return false;
	}

	public void remove(T usuwany) {
		this.remove(usuwany, null);
	}

	private static boolean random() {
		return Math.random() < 0.5;
	}

	public void remove(T usuwany, GenericBTS<T> parent){
		if(usuwany.compareTo(this.dane) == -1){
	        this.lewy.remove(usuwany, this);
		}else if(usuwany.compareTo(this.dane) == 1){
	        this.prawy.remove(usuwany, this);
		}else{ // delete the key here
	        if(this.lewy !=null && this.prawy !=null){ // if both children are present
	        	if(GenericBTS.random()){
	        		GenericBTS<T> successor = this.prawy;
	        		GenericBTS<T> rodzic = this;
		    		while (successor.lewy != null) {
		    			rodzic = successor;
		    			successor = successor.lewy;
		    			
		    		}
		    		this.dane = successor.dane;
		            rodzic.lewy = null;
	        	}else{
	        		GenericBTS<T> successor = this.lewy;
	        		GenericBTS<T> rodzic = this;
		    		while (successor.prawy != null) {
		    			rodzic = successor;
		    			successor = successor.prawy;
		    			
		    		}
		    		this.dane = successor.dane;
		            rodzic.prawy = null;
	        	}
			}else if(this.lewy !=null){   // if the node has only a *left* child
	            if(parent != null){
	            	parent.replace(this, this.lewy);
	            }
			}else if(this.prawy !=null){  // if the node has only a *right* child
	            if(parent != null){
	            	parent.replace(this, this.prawy);
	            }
			} else { // this node has no children
				if (parent.lewy == this) { // usuwamy od rodzica z lewej
					parent.lewy = null;
				} else if (parent.prawy == this) { // usuwamy od rodzica z prawej rodzica
					parent.prawy= null;
				}
			}
		};
	}


	public boolean isBST() {
		if (this.lewy != null && this.compareTo(this.lewy) == -1) {
			return false;
		}
		if (this.prawy != null && this.compareTo(this.prawy) == 1) {
			return false;
		}
		if (this.lewy != null && !this.lewy.isBST()) {
			return false;
		}
		if (this.prawy != null && !this.prawy.isBST()) {
			return false;
		}
		return true;
	}

}

ImplementBTS.java

public class ImplementBTS extends BinaryTreeNode {

	public ImplementBTS(int dane) {
		super(dane);
	}

	@Override
	public void print(int poziom) {
		if (lewy != null) {
			lewy.print(poziom + 1);
		}
		for (int i = 0; i < poziom; i++) {
			if (this.dane > 10) {
				System.out.print("  ");
			} else {
				System.out.print(" ");
			}
		}
		System.out.print(this.dane);
		System.out.print("\n");
		if (prawy != null) {
			prawy.print(poziom + 1);
		}
	}

	@Override
	public boolean searchBSTRec(int szukany) {
		int count = 0;
		BinaryTreeNode x = this;
		BinaryTreeNode y = null;
		while (x != null && x.dane != szukany) {
			y = x;
			x = szukany < x.dane ? x.lewy : x.prawy;
			count++;
		}
		System.out.print("Odwiedzono:" + count);
		return true;
	}

	@Override
	public Pair<BinaryTreeNode, BinaryTreeNode> searchBST(int szukany) {
		BinaryTreeNode x = this;
		BinaryTreeNode y = null;
		while (x != null && x.dane != szukany) {
			y = x;
			x = szukany < x.dane ? x.lewy : x.prawy;
		}
		return new Pair<BinaryTreeNode, BinaryTreeNode>(x, y);
	}

	@Override
	public void addBSTRec(int nowy) {
		if (this.dane == nowy) {
			return;
		} else if (nowy < this.dane) {
			if (this.lewy == null) {
				this.lewy = new ImplementBTS(nowy);
			} else {
				this.lewy.insertBST(nowy);
			}
		} else {
			if (this.prawy == null) {
				this.prawy = new ImplementBTS(nowy);
			} else {
				this.prawy.insertBST(nowy);
			}
		}
	}

	public static void main(String[] args) {
		// .8
		// 3 5
		// 2 1 4 0
		ImplementBTS a = new ImplementBTS(8);
		a.insertBST(20);
		a.insertBST(5);
		a.insertBST(30);
		a.insertBST(15);
		a.insertBST(17);
		a.insertBST(25);
		a.insertBST(35);
		a.insertBST(40);
		a.print(1);
		assert (a.searchBST(150).first == null);
		assert (a.searchBST(8).second == null);
		assert (a.searchBST(15).second == a.searchBST(20).first);
		assert (a.searchBST(15).first.dane == 15);
		System.out.print("\n-------------\n");
		System.out.print(a.isBST());
		System.out.print("\n-------------\n");
		a.remove(20);
		System.out.print("\n-------------\n");
		System.out.print(a.isBST());
		System.out.print("\n-------------\n");
		a.print(1);
		
		System.out.print("End");
	}

	@Override
	public void insertBST(int nowy) {
		Pair<BinaryTreeNode, BinaryTreeNode> pair = this.searchBST(nowy);
		if (pair.first != null) {
			return;
		} else if (nowy < pair.second.dane) {
			pair.second.lewy = new ImplementBTS(nowy);
		} else {
			pair.second.prawy = new ImplementBTS(nowy);
		}
	};

	private static boolean random() {
		return Math.random() < 0.5;
	}

	private boolean replace(BinaryTreeNode child, BinaryTreeNode niu) {
		if (this.lewy == child) { // usuwamy od rodzica z lewej
			this.lewy = niu;
			return true;
		} else if (this.prawy == child) { // usuwamy od rodzica z prawej rodzica
			this.prawy= niu;
			return true;
		}
		return false;
	}

	public void remove(int usuwany) {
		this.remove(usuwany, null);
	}

	public void remove(int usuwany, BinaryTreeNode parent){
		if(usuwany < this.dane){
	        ((ImplementBTS) this.lewy).remove(usuwany, this);
		}else if(usuwany > this.dane){
	        ((ImplementBTS) this.prawy).remove(usuwany, this);
		}else{ // delete the key here
	        if(this.lewy !=null && this.prawy !=null){ // if both children are present
	        	if(ImplementBTS.random()){
		        	BinaryTreeNode successor = this.prawy;
		    		while (successor.lewy != null) {
		    			successor = successor.lewy;
		    		}
		    		this.dane = successor.dane;
		            ((ImplementBTS) successor).remove(successor.dane, this);
	        	}else{
		        	BinaryTreeNode successor = this.lewy;
		    		while (successor.prawy != null) {
		    			successor = successor.prawy;
		    		}
		    		this.dane = successor.dane;
		            ((ImplementBTS) successor).remove(successor.dane, this);	
	        	}
			}else if(this.lewy !=null){   // if the node has only a *left* child
	            if(parent != null){
	            	((ImplementBTS)parent).replace(this, this.lewy);
	            }
			}else if(this.prawy !=null){  // if the node has only a *right* child
	            if(parent != null){
	            	((ImplementBTS) parent).replace(this, this.prawy);
	            }
			} else { // this node has no children
				if (parent.lewy == this) { // usuwamy od rodzica z lewej
					parent.lewy = null;
				} else if (parent.prawy == this) { // usuwamy od rodzica z prawej rodzica
					parent.prawy= null;
				}
			}
		};
	}

	/*
	public void remove2(int usuwany) {
		Pair<BinaryTreeNode, BinaryTreeNode> pair = this.searchBST(usuwany);
		if (pair.first == null) {
			return;
			// Rys. 1 (liść)
		} else if (pair.first.lewy == null && pair.first.prawy == null) {
			assert (((ImplementBTS) pair.first).replace(pair.second, null) == true);
			// Rys. 2 (węzeł z jednym dzieckiem)
		} else if (pair.first.lewy == null) {
			assert (((ImplementBTS) pair.second).replace(pair.first,
					pair.first.prawy) == true);
		} else if (pair.first.prawy == null) {
			assert (((ImplementBTS) pair.second).replace(pair.first,
					pair.first.lewy) == true);
			// Rys. 3 (węzeł ma dwóch synów)
		} else {
			boolean rand = this.random();
			// (a) idziemy raz w prawo i do końca w lewo - Rys. 3 – wstawiamy 6
			// (b) idziemy raz w lewo i do końca w prawo – wstawiamy 3
			BinaryTreeNode tmp;
			BinaryTreeNode tmp_prev = pair.second;
			boolean x = false;
			if (rand && x) { // prawy & maks w lewo
				// Szukamy wezla do przestawienia
				tmp = pair.second.prawy;
				while (tmp.lewy != null) {
					tmp_prev = tmp;
					tmp = tmp.lewy;
				}
				// Przestawiamy wezel
				if (pair.second.lewy == pair.first) { // usuwamy od rodzica z
														// lewej
					pair.second.lewy.dane = tmp.dane;
				} else if (pair.second.prawy == pair.first) { // usuwamy od
																// rodzica z
																// prawej
																// rodzica
					pair.second.prawy.dane = tmp.dane;
				} else {
					assert (false);
				}
				// tmp_prev.lewy = tmp.lewy;
			} else { // lewy & maks w prawo
				// Szukamy wezla do przestawienia
				tmp = pair.second.lewy;
				while (tmp.prawy != null) {
					tmp_prev = tmp;
					tmp = tmp.prawy;
				}
				System.out.print(tmp.dane + ":" + tmp_prev.dane);
				// Przestawiamy wezel
				if (pair.second.lewy == pair.first) { // usuwamy od rodzica z
														// lewej
					pair.second.lewy.dane = tmp.dane;
				} else if (pair.second.prawy == pair.first) { // usuwamy od
																// rodzica z
																// prawej
																// rodzica
					pair.second.prawy.dane = tmp.dane;
				} else {
					assert (false);
				}

				// tmp_prev.prawy = tmp.prawy;
			}

		}
	};
	*/
	private boolean isBST() {
		if (this.lewy != null && this.dane < this.lewy.dane) {
			return false;
		}
		if (this.prawy != null && this.dane > this.prawy.dane) {
			return false;
		}
		if (this.lewy != null && !((ImplementBTS) this.lewy).isBST()) {
			return false;
		}
		if (this.prawy != null && !((ImplementBTS) this.prawy).isBST()) {
			return false;
		}
		return true;
	}

}

Pair.java

public class Pair<T1, T2> {
        public T1 first;
        public T2 second;

         public Pair(T1 a, T2 b) {
               first = a;
               second = b;
        }
}