Java实现二叉查找树

川长思鸟来 2023-07-21 11:12 8阅读 0赞

前序：[开头：数据结构和算法][Link 1]的二叉排序树部分已经介绍二叉排序树了

**实现了以下方法：**

1.  makeEmpty方法
2.  isEmpty方法
3.  contains方法
4.  getMin方法
5.  getMax方法
6.  insert方法
7.  remove方法
8.  printTree方法（遍历树）

说明：T extends Comparable<? super T>的含义  
extends/super分别是泛型的上下界（含）。  
对T的约束是Comparable的子类，对Comparable中泛型的约束是，至少是T的父类。

**实现代码：**

/**
     * @Description: 二叉排序树
     */
    public class BinarySearchTree<T extends Comparable<? super T>>{
    	
    	/**
    	 * @Description: 静态内部类：表示树结点
    	 */
    	private static class BinaryNode<T>{
    		T element;
    		BinaryNode<T> left;
    		BinaryNode<T> right;
    		
    		BinaryNode(T theElement){
    			this.element=theElement;
    		}
    		BinaryNode(T theElement,BinaryNode<T> lt,BinaryNode<T> rt){
    			this.element=theElement;
    			this.left=lt;
    			this.right=rt;
    		}
    	}
    	private BinaryNode<T> root;
    	
    	public BinarySearchTree(){
    		this.root=null;
    	}
    	
    	/**
    	 * @Description:[功能描述]1.二叉排序树置空
    	 */
    	public void makeEmpty() {
    		root=null;
    	}
    	
    	/**
    	 * @Description:[功能描述]2.查看二叉排序树是否为空
    	 */
    	public boolean isEmpty() {
    		return root==null;
    	}
     
    	/**
    	 * @Description:[功能描述]3.判断二叉排序树中是否存在项x的结点
    	 * @param x
    	 * @return 如果存在，放回true;否则返回false
    	 */
    	public boolean contains(T x) {
    		return contains(x,root);
    	}
    	
    	/**
    	 * @Description:[功能描述]4.返回树中包含最大元
    	 * @return
    	 */
    	public T findMin() {
    		return findMin(root).element;
    	}
     
    	/**
    	 * @Description:[功能描述]5.返回树中包含最小元
    	 * @return
    	 */
    	public T findMax() {
    		return findMax(root).element;
    	}
     
    	/**
    	 * @Description:[功能描述]6.插入操作
    	 * @param x
    	 */
    	public void insert(T x) {
    		root=insert(x,root);
    	}
     
    	/**
    	 * @Description:[功能描述]7.删除操作，正如许多数据结构一样，最困难的是remove(删除)
    	 * @param x
    	 */
    	public void remove(T x) {
    		root=remove(x,root);
    	}
    	
    	//8.遍历树
    	public void printTree() {
    		if(isEmpty()) {
    			System.out.println("Emptye tree");
    		}else {
    			printTree(root);
    		}
    	}
     
    	//先序遍历二叉树
    	private void printTree(BinaryNode<T> t) {
    		System.out.println(t.element);
    		if(t.left!=null) {
    			printTree(t.left);
    		}
    		if(t.right!=null) {
    			printTree(t.right);
    		}
    	}
    
    	private boolean contains(T x, BinaryNode<T> t) {
    		if(t==null) {
    			return false;
    		}
    		int compareResult=x.compareTo(t.element);
    		
    		if(compareResult < 0) {
    			return contains(x,t.left);
    		}else if(compareResult > 0) {
    			return contains(x,t.right);
    		}else {
    			return true;
    		}
    	}
    	
    	private BinaryNode<T> findMin(BinaryNode<T> t) {
    		if(t==null) {
    			return null;
    		}else if(t.left==null) {
    			return t;
    		}
    		return findMin(t.left);
    	}
    	
    	private BinaryNode<T> findMax(BinaryNode<T> t) {
    		if(t!=null) {
    			while(t.right!=null) {
    				t=t.right;
    			}
    		}
    		return t;
    	}
    	
    	private BinaryNode<T> insert(T x, BinaryNode<T> t) {
    		if(t==null) {
    			return new BinaryNode<T>(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 {
    			;//do nothing
    		}
    		return t;
    		
    	}
    	
    	private BinaryNode<T> remove(T x, BinaryNode<T> t) {
    		if(t==null) {
    			return t;
    		}
    		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) {
    			t.element=findMin(t.right).element;
    			t.right=remove(t.element,t.right);
    		}else {
    			t=(t.left !=null)?t.left:t.right;
    		}
    		return t;
    		
    	}
    }

**测试：**

public class Test {
        	public static void main(String[] args) throws Throwable{
        		BinarySearchTree<Integer> bst=new BinarySearchTree<>();
        		bst.insert(4);
        		bst.insert(2);
        		bst.insert(6);
        		bst.insert(1);
        		bst.insert(5);
        		//先序遍历
        		bst.printTree();
       
        	}    
    }

![20200404095616527.png][]

[Link 1]: https://blog.csdn.net/yiguang_820/article/details/84287481
[20200404095616527.png]: /images/20230528/ea015a0488d94841a3070df42d605001.png