For EECS2030

BinarySortedTree.java

package quiz4;

import java.util.Random;
import java.util.Scanner;

/**
 * BinarySortedTree for EECS2030
 * 
 * @author chen256
 *
 */
public class BinarySortedTree <T extends Comparable<? super T>>{

	/**
	 * Test Cases
	 * @param args
	 */
	public static void main(String[] args) {
		BinarySortedTree<Integer> bst = new BinarySortedTree<Integer>();
		/*
		Random rn = new Random();
		for (int i = 0; i < 10; i++){
			bst.addNode(new Integer(rn.nextInt(100)));
		}
		*/
		bst.addNode(new Integer(50));
		bst.addNode(new Integer(27));
		bst.addNode(new Integer(73));
		bst.addNode(new Integer(8));
		bst.addNode(new Integer(44));
		bst.addNode(new Integer(83));
		bst.addNode(new Integer(73));
		bst.addNode(new Integer(93));

		
		System.out.print("Inorder=>");
		System.out.println(bst.toString());
		System.out.print("Preorder=>");
		System.out.println(bst.toStringPreorder());
		System.out.print("Postorder=>");
		System.out.println(bst.toStringPostorder());
		
		System.out.print("Max:");
		System.out.println(bst.largestValue());
		
		Scanner in = new Scanner(System.in);

		boolean exit = false;
		String cmd;
		while (!exit)
		{
			System.out.print("\n> ");
			cmd = in.next();
			if (cmd.equals("exit"))
			{
				exit = true;
			}else{
				Integer remove = Integer.parseInt(cmd);
				bst.removeNode(remove);
				System.out.print("Inorder=>");
				System.out.println(bst.toString());
			}
		}
	}
	
	///////////////////////////////////////
	private Node<T> root;
	
	public BinarySortedTree(){
		this.root = null;
	}
	
	/**
	 * Add a new Node
	 * @param data
	 */
	public void addNode(T data){
		this.root = addNode(root, data);
	}
	
	private Node<T> addNode(Node<T> n, T data){
		if (n == null){
			return new Node<T>(data, null, null);
		}else{
			if(n.data.compareTo(data) > 0){
				n.left = addNode(n.left, data);
			}else{
				n.right = addNode(n.right, data);
			}
			return n;
		}
	}
	
	private Node<T> addNode(Node<T> n, Node<T> o){
		if (n == null){
			return o;
		}else{
			if(n.data.compareTo(o.data) > 0){
				n.left = addNode(n.left, o);
			}else{
				n.right = addNode(n.right, o);
			}
			return n;
		}
	}
	
	/**
	 * Remove a Node
	 * @param data
	 */
	public void removeNode(T data){
		this.root = removeNode(root, data);
	}
	
	private Node<T> removeNode(Node<T> n, T data){
		if (n == null){
			return null;
		}else{
			int compare = n.data.compareTo(data);
			if (compare == 0){
				if (n.left == null && n.right == null){
					return null;
				}else if (n.left != null && n.right != null){
					n.data = this.largestValue(n.left);
					n.left = this.removeNode(n.left, n.data);
					return n;
				}else{
					if (n.left != null){
						return n.left;
					}else{
						return n.right;
					}
				}
			}else if (compare > 0){
				n.left = removeNode(n.left, data);
			}else{
				n.right = removeNode(n.right, data);
			}
			return n;
		}
	}
	
	/**
	 * Find the largest value
	 * @return
	 */
	public T largestValue(){
		return largestValue(this.root);
	}
	
	private T largestValue(Node<T> root){
		if (root == null){
			return null;
		}else if(root.right != null){
			return largestValue(root.right);
		}else{
			return root.data;
		}	
	}
	
	
	/**
	 * Convert to String
	 */
	public String toString(){
		return this.toStringInorder(this.root);
	}

	public String toStringInorder(){
		return this.toStringInorder(this.root);
	}
	
	private String toStringInorder(Node<T> n){
		StringBuilder sb = new StringBuilder();
		if (n != null){
			if(n.left != null){
				sb.append(toStringInorder(n.left));
				sb.append(",");
			}
			sb.append(n.data.toString());
			if(n.right != null){
				sb.append(",");
				sb.append(toStringInorder(n.right));
			}
		}
		return sb.toString();
	}

	public String toStringPreorder(){
		return this.toStringPreorder(this.root);
	}
	
	private String toStringPreorder(Node<T> n){
		StringBuilder sb = new StringBuilder();
		if (n != null){
			sb.append(n.data.toString());
			if(n.left != null){
				sb.append(",");
				sb.append(toStringPreorder(n.left));
			}
			if(n.right != null){
				sb.append(",");
				sb.append(toStringPreorder(n.right));
			}
		}
		return sb.toString();
	}
	

	public String toStringPostorder(){
		return this.toStringPostorder(this.root);
	}
	
	private String toStringPostorder(Node<T> n){
		StringBuilder sb = new StringBuilder();
		if (n != null){
			if(n.left != null){
				sb.append(toStringPostorder(n.left));
				sb.append(",");
			}
			if(n.right != null){
				sb.append(toStringPostorder(n.right));
				sb.append(",");
			}
			sb.append(n.data.toString());
		}
		return sb.toString();
	}
	
	/**
	 * Node Structure
	 * @author chen256
	 *
	 * @param <T>
	 */
	public static class Node<T>{
		public T data;
		public Node<T> left;
		public Node<T> right;
		
		public Node(T data, Node<T> left, Node<T> right){
			this.data = data;
			this.left = left;
			this.right = right;
		}
	}

}