binarytree.java

Binary Search:算法基础

//******************PUBLIC OPERATIONS*********************
//void insert( k )       			--> Insert k
//void delete( k )       			--> Delete k
//BinaryTreeNode find( k )			--> Return node that matches k
//boolean search( k )				--> Return true if find k; else false
//boolean isEmpty( node )			--> Return true if empty; else false

package binaryTree;

public class BinaryTree {
	
	private class BinaryTreeNode {

		Object key;
		BinaryTreeNode left_child;
		BinaryTreeNode right_child;

		BinaryTreeNode(Object aNode) {
			this(aNode, null, null);
		}

		BinaryTreeNode(Object key, BinaryTreeNode left_child, BinaryTreeNode right_child) {
			this.key = key;
			this.left_child = left_child;
			this.right_child = right_child;
		}
	}

	private BinaryTreeNode root;
	private final Object DELETED = null;
	private int size;
	
	public BinaryTree() {
		root = null;
	}

	public void insert(Comparable k) {
		insert(k, root);
		++size;
	}
	
	private BinaryTreeNode insert(Comparable k, BinaryTreeNode aNode) {
		if (isInsertable(aNode))
			aNode = new BinaryTreeNode(k, null, null);
		else if (aNode.left_child == null)
			aNode.left_child = insert(k, aNode.left_child);
		else if (aNode.right_child == null)
			aNode.right_child = insert(k, aNode.right_child);
		return aNode;
	}
	
	private boolean isInsertable(BinaryTreeNode aNode) {
		if (aNode == null || aNode.key.equals(DELETED)){
			return true;
		}
		else return false;
	}
	
	public boolean search(Comparable k, BinaryTreeNode aNode) {
		if (aNode == null)//k not found
			return false;
		if (k.equals(aNode.key)) return true;
		else {
			return (search(k, aNode.left_child)||search(k, aNode.right_child));
		}
	}
	
	private BinaryTreeNode current = null;//the recorder in the recurrence of find
	public BinaryTreeNode find(Comparable k, BinaryTreeNode aNode) {
		if (aNode == null) return null;//k not found
		else if (k.equals(aNode.key)) current = aNode;//k found
		else{
			find(k, aNode.left_child);
			find(k, aNode.right_child);
		}
		return current;
	}
	
	public void delete(Comparable k, BinaryTreeNode aNode) {
		BinaryTreeNode d = find(k,root);
		d.key = DELETED;
		--size;
	}
	
	public boolean isEmpty() {
		if(size == 0)
			return true;
		else return false;
	}
	

}