binarysearchtree.java

Binary Search:算法基础

//******************PUBLIC OPERATIONS*********************
//void insert( k )       			--> Insert k
//void delete( k )       			--> Delete k
//void printTree( node )			--> Print all the nodes
//Comparable find( k )				--> Return node that matches k
//boolean search( k )				--> Return true if find k; else false
//Comparable findMin( node )		--> Return smallest node
//boolean isEmpty( node )			--> Return true if empty; else false


package binaryTree;

public class BinarySearchTree {

	private class BinarySearchTreeNode {

		Comparable key;
		BinarySearchTreeNode left_child;
		BinarySearchTreeNode right_child;

		BinarySearchTreeNode(Comparable key) {
		this(key, null, null);
		}

		BinarySearchTreeNode(Comparable key, BinarySearchTreeNode left_child, BinarySearchTreeNode right_child) {
			this.key = key;
			this.left_child = left_child;
			this.right_child = right_child;
		}
	}
	
	private BinarySearchTreeNode root;
	private int size;
	
	public BinarySearchTree() {
		root = null;
		size = 0;
	}
	
	public Comparable find(Comparable k) {
		return find(k,root).key;
	}
	
	private BinarySearchTreeNode find(Comparable k, BinarySearchTreeNode aNode) {
		if (aNode == null)//k not found
			return null;
		else if (k.compareTo(aNode.key) < 0)//if smaller goto left
			return find(k, aNode.left_child);
		else if(k.compareTo(aNode.key) > 0)//if bigger goto right
			return find(k, aNode.right_child);
		else//k found
			return aNode;
	}
	public boolean search(Comparable k){
		return search(k,root);
	}
	private boolean search(Comparable k, BinarySearchTreeNode aNode) {
		
		if( aNode == null ) //k not found
			return false;
		else if(aNode.key == k)//k found
			return true;	
		else if(k.compareTo(aNode.key)<0)  //if smaller goto left
			return search(k, aNode.left_child); 
		else //if bigger goto right
			return search(k, aNode.right_child); 
	}

	public void insert(Comparable k) {
		insert(k, root);
		++size;
	}

	private BinarySearchTreeNode insert(Comparable k, BinarySearchTreeNode aNode) {
		if (aNode == null){
			aNode = new BinarySearchTreeNode(k, null, null);//go to the external node and insert the new node
		}
		else if (k.compareTo(aNode.key) < 0)//if smaller goto left
			aNode.left_child = insert(k, aNode.left_child);
		else if (k.compareTo(aNode.key) > 0)//if bigger goto right
			aNode.right_child = insert(k, aNode.right_child);
		return aNode;
	}
	
	//delete use a recursion to delete a node in a fantastic way.	
	public void delete(Comparable k) {
		delete(k, root);
		--size;
	}
	
	private BinarySearchTreeNode delete(Comparable k, BinarySearchTreeNode aNode) {
		if (aNode == null)
			return aNode; 
		if (k.compareTo(aNode.key) < 0)
			aNode.left_child = delete(k, aNode.left_child);
		else if (k.compareTo(aNode.key) > 0)
			aNode.right_child = delete(k, aNode.right_child);
		else if (aNode.left_child != null && aNode.right_child != null) 
		{
			aNode.key = findMin(aNode.right_child).key;
			aNode.right_child = delete(aNode.key, aNode.right_child);
		}
		else
			aNode = (aNode.left_child != null) ? aNode.left_child : aNode.right_child;
		return aNode;
	}
	//findMax to find the minimum key in the subtree of the a node.		
	public BinarySearchTreeNode findMin(BinarySearchTreeNode aNode) {
		if (aNode == null)
			return null;
		else if (aNode.left_child == null)
			return aNode;
		return findMin(aNode.left_child);
	}
	
	//InorderTraversal to print the whole tree.	
	public void printTree() {
		if(size == 0)
			System.out.println("The tree is empty");
		else {
			String output = (size == 0) ? "node" : "nodes";
			System.out.println("Tree has "+ size + output);	
			inorderTraversal(root);
		}
	}

	private void inorderTraversal(BinarySearchTreeNode aNode) {
		if(aNode != null) 
		{
			inorderTraversal(aNode.left_child);
			System.out.println(aNode.key);
			inorderTraversal(aNode.right_child);
		}
	}
	
	public boolean isEmpty() {
		if(size == 0)
			return true;
		else return false;
	}
	
}