二叉查找树的简单实现

Love The Way You Lie 2022-05-17 12:24 134阅读 0赞

二叉查找树的性质是：对于树中的每个节点X，它的左子树中所有项的值小于X项的值，而它的右子树中所有的项的值大于X项的值。

对于二叉树要求所有的项都要可以排序，因此应当实现Comparable接口，在树的构建中使用迭代的方法，以及查找删除均使用迭代的方式实现。

主要实现：

*  定义了二叉树的节点，采用了嵌套类的方式(nest class)包含元素节点、左子节点、右子节点。
 *  包含contain(anyType x)方法根据其树的结构特点，采用二分递归的方式查找是否存在。
 *  查询最大值findMax()和最小值findMin()方法，一个采用递归一个采用while循环。在所有的方法递归前先处理空树的情况，防止出现NullPointException的问题。
 *  insert(AnyType x)方法,根据要插入的元素遍历树，采用包含方法的遍历思想，比较找到合适的位置将其插入，并且每次返回新的节点的位置方便下次的递归调用。
 *  删除元素。分为三种情况：

1.   如果没有节点即叶子结点直接删除；
2.  如果该节点上有只有一个子节点父节点直接调整结构直接绕过该节点将其子节点上提代替掉该节点；
3.  如果有两个子节点则需要在左子树中找到其最大的子孙节点代替该节点。

**
     * @author QuLei
     *The simple BinarySearchTree 
     * @param <AnyType>
     */
    public class BinarySearchTree<AnyType extends Comparable<? super AnyType >>{
    	
    	private static class BinaryNode<AnyType>{
    		AnyType element;
    		BinaryNode<AnyType> left;
    		BinaryNode<AnyType> right;
    		//Constructor
    		BinaryNode(AnyType theElemnt) {
    			// TODO Auto-generated constructor stub
    			this(theElemnt,null,null);  //调用当前类的构造器
    		}
    		
    		BinaryNode(AnyType theElemnt, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt) {
    			// TODO Auto-generated constructor stub
    			element =theElemnt;
    			left = lt;
    			right = rt;
    		}
    	}
    	
    	private BinaryNode<AnyType> root;
    	
    	public BinarySearchTree() {
    		root = null;
    	}
    	
    	public void makeEmpty() {
    		root = null;
    	}
    	
    	public boolean isEmpty() {
    		return root == null;
    	}
    	
    	public boolean contains(AnyType x) {
    		return contains(x,root);
    	}
    
    	public AnyType findMax() throws UnderflowException {
    		if(isEmpty()) 
    			throw new UnderflowException("the tree is Empty");
    		return findMax(root).element;
    	}
    	
    	public AnyType findMin() throws UnderflowException {
    		if(isEmpty())
    			throw new UnderflowException("the tree is Empty");
    		return findMin(root).element;
    	}
    	
    	public void insert(AnyType x) {
    		root = insert(x,root);
    	}
    	
    	public void remove(AnyType x) {
    		root = remove(x,root);
    	}
    	
    	public void printTree() {
    		if(isEmpty()) {
    			System.out.println("Empty tree");
    		}else {
    			printTree(root);
    		}
    	}
    	/**
    	 * Internal method to find an item in a subtree.
    	 * @param x is item to search for.
    	 * @param root the node that roots the subtree.
    	 * @return node containing the matched item.
    	 */
    	private boolean contains(AnyType x,BinaryNode<AnyType> root) {
    		if(root == null) {
    			return false;  //Empty tree
    		}
    		int compareResult = x.compareTo(root.element);
    		if(compareResult < 0 ) {
    			return contains(x,root.left);  //iterate to left
    		}else if(compareResult > 0) {
    			return contains(x, root.right); //iterate to right
    		}else {
    			return true; //Match
    		}
    	}
    	
    	/**
    	 * Internal method to find the largest item in a subtree.
    	 * @param t the node that roots the subtree.
    	 * @return node containing the largest item.
    	 */
    	private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t){
    		if(t != null) {
    			while(t.right != null) {
    				t = t.right;
    			}
    		}
    		return t;
    	}
    	
    	/**Internal method to find the smallest item in a subtree.
    	 * @param t the node that roots the subtree.
    	 * @return node containing the smallest item.
    	 */
    	private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t){
    		if(t == null)
    			return null;
    		else if(t.left == null) {
    			return t;
    		}
    		return findMin(t.left);
    	}
    	
    	/**Internal method to insert into a subtree.
    	 * @param x the item to insert.
    	 * @param t the node that roots the subtree.
    	 * @return the new root of the subtree.
    	 */
    	private BinaryNode<AnyType> insert(AnyType x,BinaryNode<AnyType> t){
    		if(t == null) {
    			return new BinaryNode<AnyType>(x,null,null);
    		}
    		int compareResult = x.compareTo(t.element);
    		if(compareResult < 0) {
    			t.left = insert(x,t.left);
    		}else if(compareResult > 0) {
    			t.right = insert(x,t.right);
    		}else {
    			//Duplicate; do noting
    		}
    		return t;
    	}
    	
    	/**Internal method to remove from a subtree.
    	 * @param x the item to remove.
    	 * @param t the node that roots the subtree.
    	 * @return the new root of the subtree.
    	 */
    	private BinaryNode<AnyType> remove(AnyType x,BinaryNode<AnyType> t){
    		if(t == null) {
    			return t; //Item not found ;do noting
    		}
    		int compareResult = x.compareTo(t.element);
    		if(compareResult < 0)
    			t.left = remove(x, t.left);
    		else if(compareResult > 0 )
    			t.right = remove(x,t.right);
    		else if (t.left == null || t.right == null) { // two children
    			t.element = findMin(t.right).element;
    			t.right = remove(t.element,t.right);
    		}
    		else {
    			t = (t.left != null ) ? t.left : t.right;
    		}
    		return t;
    	}
    	
    	/**Internal method to print a subtree in sorted order. 
    	 * @param t the node that roots the subtree.
    	 */
    	private void printTree(BinaryNode<AnyType> t) {
    		if(t != null) {
    			printTree(t.left);
    			System.out.println(t.element);
    			printTree(t.right);
    		}
    	}
    }