二叉查找树BST——Java实现

参考：二叉树查找之Java实现

树的基本概念

    1、树是一种数据结构，它是由n（n≥1）个有限结点组成一个具有层次关系的集合。

    2、树Tree是n(n>=0)个结点的有限集。在任意一颗非空树中：

    （1）有且仅有一个特定的被称为根root的结点；

    （2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1,T2,...,Tm,其中每一个集合本身又是一棵树，并且称为根的子树SubTree.

1、结点拥有的子树数称为结点的度Degree。度为0的结点称为叶子Leaf或终端结点；度不为0的结点称为非终端结点或分支结点。

2、树的度是树内各结点度的最大值。

3、结点的子树的根称为该结点的孩子Child，相应地，该结点称为孩子的双亲结点Parent。

4、结点的层次Level是从根结点开始计算，根为第一层，根的孩子为第二层，依次类推。

    树中结点的最大层次称为树的深度Depth或高度。

5、如果将树中结点的各子树看成从左至右是有次序的(即不能互换)，则该树称为有序树，否则称为无序树。

二叉树的基本概念

1、二叉树Binary Tree的特点是每个结点至多具有两棵子树(即在二叉树中不存在度大于2 的结点)，并且子树之间有左右之分。

它有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。

2、二叉树Binary Tree性质：

1、在二叉树的第i层至多有2^(i-1)个结点(i≥1)；

2、深度为k的二叉树至多有2^k-1个结点(k≥1)；

3、对任意一棵二叉树，如果其终端结点数为n0,度为2 的结点数为n2，则，n0=n2+1

4、具有n个结点的完全二叉树的深度不大于log₂ n的最大整数加1

5、包含n个结点的二叉树的高度至少为log₂ (n+1)

6、如果对一棵有n个结点的完全二叉树的结点按层序编号(从第一层到最后一层，每层从左到右)，则对任一结点(1≤i≤n)，有

        a:如果i=1,则结点i是二叉树的根，无双亲；

            如果i>1,则其双亲是结点x（其中结点x是 不大于i/2的最大整数）

        b:如果2i>n,则结点i无左孩子(结点i为叶子结点)；否则其左孩子是结点2i

        c:如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1

3、满二叉树、完全二叉树和二叉查找树

    3.1满二叉树

定义：高度为h，并且由2^{h} –1个结点的二叉树，被称为满二叉树。

    3.2完全二叉树

定义：一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树。

特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

    3.3二叉查找树

定义：二叉查找树(Binary Search Tree)，又被称为二叉搜索树。设x为二叉查找树中的一个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y] <= key[x]；如果y是x的右子树的一个结点，则key[y] >= key[x]。

二叉查找树(BinarySearch Tree，也叫二叉搜索树，或二叉排序树BinarySort Tree)或者是一棵空树，或者是具有下列性质的二叉树：

1、若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2、若任意结点的右子树不空，则右子树上所有节点的值均大于它的根结点的值；

3、任意结点的左右子树也分别为二叉查找树；

4、没有键值相等的结点。

在实际应用中，二叉查找树的使用比较多。

二叉查找树的Java实现

1、二叉查找树结点的定义

BSTree是二叉树，它保护了二叉树的根结点mRoot；mRoot是BSTNode类型，而BSTNode是二叉查找树的结点，它是BSTree的内部类。二叉查找树的节点BSTNode包含二叉查找树的几个基本信息：

(01) key       -- 它是关键字，是用来对二叉查找树的节点进行排序的。
(02) left       -- 它指向当前节点的左孩子。
(03) right    -- 它指向当前节点的右孩子。
(04) parent -- 它指向当前节点的父结点。

package binarySearchTree;

public class BSTree<T extends Comparable<T>> {
	
	private BSTNode<T> mRoot;		//根结点
	public class BSTNode<T extends Comparable<T>>{	//内部类
		T key;				//关键字
		BSTNode<T> left;	//左孩子
		BSTNode<T> right;	//右孩子
		BSTNode<T> parent;	//父结点	
		public BSTNode(T key, BSTNode<T> left, BSTNode<T> right, BSTNode<T> parent) {
			super();
			this.key = key;
			this.left = left;
			this.right = right;
			this.parent = parent;
		}		
	}
}

2、遍历

    2.1前序遍历

    若二叉树非空，则执行以下操作：

    （01）访问根节点

    （02）先序遍历左子树

    （03）先序遍历右子树

        /**
	 * 前序遍历二叉树
	 */
	public void preOrder(){
		preOrder(mRoot);
	}
	private void preOrder(BSTNode<T> tree){
		if (tree!=null) {
			System.out.println(tree.key+" ");
			preOrder(tree.left);
			preOrder(tree.right);
		}
	}

    2.2中序遍历

   若二叉树非空，则执行以下操作：

    （01）中序遍历左子

    （02）树访问根节点

    （03）中序遍历右子树

        /**
	 * 中序遍历二叉树
	 */
	public void inOrder(){
		inOrder(mRoot);
	}
	private void inOrder(BSTNode<T> tree) {
		// TODO Auto-generated method stub
		if (tree!=null) {
			inOrder(tree.left);
			System.out.println(tree.key+" ");
			inOrder(tree.right);
		}
	}

    2.3后序遍历

   若二叉树非空，则执行以下操作：

    （01）后序遍历左子树

    （02）后序遍历右子树

    （03）访问根节点

        /**
	 * 后序遍历二叉树
	 */
	public void postOrder(){
		postOrder(mRoot);
	}
	private void postOrder(BSTNode<T> tree) {
		// TODO Auto-generated method stub
		if (tree!=null) {
			postOrder(tree.left);
			postOrder(tree.right);
			System.out.println(tree.key+" ");
		}
	}

3、查找

递归版本的代码

        /**
	 * 查找
	 * 递归实现 查找二叉树tree中键值为key的结点
	 */
	public BSTNode<T> search(T key){
		return search(mRoot,key);
	}	
	private BSTNode<T> search(BSTNode<T> tree, T key) {
		// TODO Auto-generated method stub
		if (tree==null) {
			return tree;
		}
		int cmp=key.compareTo(tree.key);
		if (cmp<0) {
			return search(tree.left, key);
		}else if (cmp>0) {
			return search(tree.right, key);
		}else {
			return tree;
		}
	}

非递归版本的代码

        /**
	 * 查找
	 * 非递归实现 查找二叉树tree中键值为key的结点
	 */
	public BSTNode<T> iterSearch(T key){
		return iterSearch(mRoot,key);
	}
	
	private BSTNode<T> iterSearch(BSTNode<T> tree, T key) {
		// TODO Auto-generated method stub
		while(tree!=null){
			int cmp=key.compareTo(tree.key);
			if (cmp<0) {
				tree=tree.left;
			}else if (cmp>0) {
				tree=tree.right;
			}else {
				return tree;
			}
		}
		return tree;
	}

4、最大值和最小值

查找最大值的代码

        /**
	 * 查找最大结点：返回tree为根结点的二叉树的最大结点
	 */
	public T max(){
		BSTNode<T> p=max(mRoot);
		if (p!=null) {
			return p.key;
		}
		return null;
	}		
	private BSTNode<T> max(BSTNode<T> tree) {
		// TODO Auto-generated method stub
		if (tree==null) {
			return null;
		}
		while(tree.right!=null){
			tree=tree.right;
		}
		return tree;
	}

查找最小值的代码

        /**
	 * 查找最小结点：返回tree为根结点的二叉树的最小结点
	 */
	public T min(){
		BSTNode<T> p=min(mRoot);
		if (p!=null) {
			return p.key;
		}
		return null;
	}		
	private BSTNode<T> min(BSTNode<T> tree) {
		// TODO Auto-generated method stub
		if (tree==null) {
			return null;
		}
		while(tree.left!=null){
			tree=tree.left;
		}
		return tree;
	}

5、前驱和后继

结点的前驱：是该结点的左子树中的最大结点。

结点的后继：是该结点的右子树中的最小结点。

查找前驱结点的代码

        /**
	 * 找结点x的前驱结点：即，查找“二叉树中数据值小于该结点”的“最大结点”
	 */
	public BSTNode<T> predecessor(BSTNode<T> x){
		//如果x存在左孩子，则“x的前驱结点”为“以其左孩子为根的子树的最大结点”
		if (x.left!=null) {
			return max(x.left);
		}
		/**
		 * 如果x没有左孩子，则x有以下两种可能
		 * 1、x是“一个右孩子”，则“x的前驱结点”为“它的父结点”
		 * 2、x是“一个左孩子”，则查找“x的最低的父结点，并且该父结点要具有右孩子”，
		 * 					找到的这个“最低的父结点”就是“x的前驱结点”
		 */
		BSTNode<T> y=x.parent;
		while((y!=null)&&(x==y.left)){
			x=y;
			y=y.parent;
		}
		return y;
	}

查找后继结点的代码

        /**
	 * 找结点x的后继结点：即，查找“二叉树中数据值大于该结点”的“最小结点”
	 */
	public BSTNode<T> successor(BSTNode<T> x){
		//如果x存在右孩子，则“x的后继结点”为“以其右孩子为根的子树的最小结点”
		if (x.right!=null) {
			return min(x.right);
		}
		/**
		 * 如果x没有右孩子，则x有以下两种可能
		 * 1、x是“一个左孩子”，则“x的后继结点”为“它的父结点”
		 * 2、x是“一个右孩子”，则查找“x的最低的父结点，并且该父结点要具有左孩子”，
		 * 					找到的这个“最低的父结点”就是“x的后继结点”
		 */
		BSTNode<T> y=x.parent;
		while((y!=null)&&(x==y.right)){
			x=y;
			y=y.parent;
		}
		return y;
	}

6、插入

    先找到待插入的叶子结点，再在叶子结点上判断与key的关系，以判断key值应该插入到什么位置

插入结点的代码

        /**
	 * 新建结点key，并将其插入到二叉树中
	 * @param bst 二叉树
	 * @param key 插入结点的键值
	 * @param z 插入的结点
	 */
	public void insert(T key){
		BSTNode<T> z=new BSTNode<T>(key, null, null, null);
		//如果新建结点失败，则返回
		if (z!=null) {
			insert(this,z);
		}
	}		
	private void insert(BSTree<T> bst, BSTNode<T> z) {
		// TODO Auto-generated method stub
		int cmp;
		BSTNode<T> y=null;
		BSTNode<T> x=bst.mRoot;//x指向该树的根结点
		
		/*
		 * 查找z的插入位置
		 * 比较根结点x与新节点z之间的关系 
		 * 		这时，y结点指向根结点x,若z小于根结点，则x指向x的左子树；否则指向右子树
		 * 			直到左/右子树为空  【y结点是x结点的父结点】
		 * 此时，z.parent指向y
		 * if y=null
		 *		新节点z就是父结点；
		 * else    
		 * 		比较z和y的大小，
		 * 		if z<y
		 * 			z插入到y的左孩子的位置
		 * 		else
		 * 			z插入到y的右孩子的位置	
		 */
		while(x!=null){	
			y=x;
			cmp=z.key.compareTo(x.key);
			if (cmp<0) {
				x=x.left;
			}else {
				x=x.right;
			}
		}
		z.parent=y;
		if (y==null) {
			bst.mRoot=z;
		}else {
			cmp=z.key.compareTo(y.key);
			if (cmp<0) {
				y.left=z;
			}else {
				y.right=z;
			}
		}		
	}

7、删除

参考--删除结点讲解

删除结点的代码

    

        /**
	 * 删除结点z，并返回被删除的结点
	 * @param tree 二叉树的根结点
	 * @param z 删除的结点
	 */
	public void remove(T key){
		BSTNode<T> z,node;
		if ((z=search(mRoot, key))!=null) {
			if ((node=remove(this,z))!=null) {
				node=null;
			}
		}
	}	
	/**
	 * 删除结点z，并返回被删除的结点
	 * @param bst 二叉树
	 * @param z 删除的结点
	 */	
	private BSTNode<T> remove(BSTree<T> bst, BSTNode<T> z) {
		// TODO Auto-generated method stub
		BSTNode<T> x=null;//子结点child
		BSTNode<T> y=null;//真正删除的结点
		
		//只有一个结点或没有结点时
		if ((z.left==null) ||(z.right==null)) {
			y=z;//z就是要删除的结点
		}else{
			y=successor(z);//当有两个子结点时，删除后继结点
		}
		
		//获取子结点，不管左右
		if (y.left!=null) {
			x=y.left;
		}else{
			x=y.right;
		}
		
		//如果存在子结点，就关联被删除结点的父结点
		if (x!=null) {
			x.parent=y.parent;
		}
		
		//如果父结点是空，说明要删的是根结点
		if (y.parent==null) {
			bst.mRoot=x;//设置根为child(此时根只有一个结点或者没有结点)
		}else if (y==y.parent.left.left) {//要删的是左结点
			y.parent.left=x;//左结点关联子结点
		}else {//要删除的是右结点
			y.parent.right=x;//右结点关联子结点
		}
		
		//如果要删除的结点和一开始传入的不一样，就是后继情况
		if (y!=z) {
			z.key=y.key;//后继的值传给本来要删除的结点
		}
		return y;//返回被删除的结点
	}

总结删除结点的思路        delete方法

1、如果该结点同时存在左右子结点

        获取后继结点；

        转移后继结点值到当前结点node；

        把要删除的当前结点设置为后继结点successor。

2、经过步骤1的处理，下面两种情况，只能是一个结点或者没有结点。

    不管有没有结点，都获取子结点child

    if child!=null,就说明有一个结点的情况，此时将父结点与子结点关联上

    if 当前结点没有父结点(后继情况到这一定有父结点)，说明要删除的就是根结点,

        根结点设置为child

    else if 当前结点是父结点的左结点

        则将父结点的左结点设置为child

    else 当前结点是父结点的右结点

        则将父结点的右结点设置为child

3、返回被删除的结点node

    public void delete(T key){
		//获取要删除的结点
		BSTNode<T> node=search(mRoot, key);
		//如果存在就删除
		if (node!=null) {
			delete(node);
		}
	}
	private BSTNode<T> delete(BSTNode<T> node) {
		//第3种情况，如果同时存在左右子结点
		if (node.left!=null && node.right!=null) {
			//获取后继结点
			BSTNode<T> successor=successor(node);
			//转移后继结点值到当前结点
			node.key=successor.key;
			//把要删除的当前结点设置为后继结点
			node=successor;
		}
		/**
		 * 经过前一步处理，下面只有两种情况，只能是一个结点或者没有结点
		 * 不管是否有子结点，都获取子结点
		 */
		BSTNode<T> child;
		if (node.left!=null) {
			child=node.left;
		}else{
			child=node.right;
		}
		/**
		 * 如果child!=null,就说明有一个结点的情况
		 * 将父结点与子结点关联上
		 */
		if (child!=null) {
			child.parent=node.parent;
		}
		/**
		 * 如果当前结点没有父结点(后继情况到这儿时一定有父结点)
		 * 说明要删除的就是根结点
		 */
		if (node.parent==null) {
			/**
			 * 根结点设置为子结点
			 * 按照前面的逻辑，根只有一个或者没有结点，所以直接赋child
			 */
			mRoot=child;
		}else if (node==node.parent.left) {
			/**
			 * 存在父结点，并且当前结点是左结点
			 * 将父结点的左结点设置为child
			 */
			node.parent.left=child;
		}else {
			/**
			 * 存在父结点，并且当前结点是右结点
			 * 将父结点的右结点设置为child
			 */
			node.parent.right=child;
		}
		//返回被删除的结点
		return node;				
	}

8、打印

打印二叉查找树的代码

        /**
	 * 打印二叉查找树
	 * key:  结点的值
	 * i  :  0,表示该结点是根结点
	 * 	-1,表示该结点是它的父结点的左孩子
	 * 	 1,表示该结点是它的父结点的右孩子
	 */
	public void print(){
		if (mRoot!=null) {
			print(mRoot,mRoot.key,0);
		}
	}
	private void print(BSTNode<T> tree, T key, int i) {
		// TODO Auto-generated method stub
		if (tree!=null) {
			if (i==0) {//根结点
				System.out.printf("%2d is root\n",tree.key);
			}else {
				System.out.printf("%2d is %2d's %6s child\n",tree.key,key,
						i==1?"right":"left");
			}
			print(tree.left, tree.key, -1);
			print(tree.right, tree.key, 1);
		}
	}

9、销毁

销毁二叉查找树的代码

        /**
	 * 销毁二叉树
	 */
	public void clear(){
		destory(mRoot);
		mRoot=null;
	}
	private void destory(BSTNode<T> tree) {
		// TODO Auto-generated method stub
		if (tree==null) {
			return ;
		}
		if (tree.left!=null) {
			destory(tree.left);
		}
		if (tree.right!=null) {
			destory(tree.right);
		}
		tree=null;
	}

实现二叉查找树的完整代码

package binarySearchTree;

public class BSTree<T extends Comparable<T>> {
	
	private BSTNode<T> mRoot;		//根结点
	public class BSTNode<T extends Comparable<T>>{	//内部类
		T key;				//关键字
		BSTNode<T> left;	//左孩子
		BSTNode<T> right;	//右孩子
		BSTNode<T> parent;	//父结点	
		//通过构造方法初始化结点
		public BSTNode(T key, BSTNode<T> left, BSTNode<T> right, BSTNode<T> parent) {
			super();
			this.key = key;
			this.left = left;
			this.right = right;
			this.parent = parent;
		}		
		public T getKey(){
			return key;
		}
		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return "key:"+key;
		}
	}
	
	public BSTree() {
		mRoot=null;
	}
	
	/**
	 * 新建结点key，并将其插入到二叉树中
	 * @param bst 二叉树
	 * @param key 插入结点的键值
	 * @param z 插入的结点
	 */
	public void insert(T key){
		BSTNode<T> z=new BSTNode<T>(key, null, null, null);
		//如果新建结点失败，则返回
		if (z!=null) {
			insert(this,z);
		}
	}		
	private void insert(BSTree<T> bst, BSTNode<T> z) {
		// TODO Auto-generated method stub
		int cmp;
		BSTNode<T> y=null;
		BSTNode<T> x=bst.mRoot;//x指向该树的根结点
		
		/*
		 * 查找z的插入位置
		 * 比较根结点x与新节点z之间的关系 
		 * 		这时，y结点指向根结点x,若z小于根结点，则x指向x的左子树；否则指向右子树
		 * 			直到左/右子树为空  【y结点是x结点的父结点】
		 * 此时，z.parent指向y
		 * if y=null
		 *		新节点z就是父结点；
		 * else    
		 * 		比较z和y的大小，
		 * 		if z<y
		 * 			z插入到y的左孩子的位置
		 * 		else
		 * 			z插入到y的右孩子的位置	
		 */
		while(x!=null){	
			y=x;
			cmp=z.key.compareTo(x.key);
			if (cmp<0) {
				x=x.left;
			}else {
				x=x.right;
			}
		}
		z.parent=y;
		if (y==null) {
			bst.mRoot=z;
		}else {
			cmp=z.key.compareTo(y.key);
			if (cmp<0) {
				y.left=z;
			}else {
				y.right=z;
			}
		}		
	}
	
	/**
	 * 前序遍历二叉树
	 */
	public void preOrder(){
		preOrder(mRoot);
	}
	private void preOrder(BSTNode<T> tree){
		if (tree!=null) {
			System.out.println(tree.key+" ");
			preOrder(tree.left);
			preOrder(tree.right);
		}
	}
	
	/**
	 * 中序遍历二叉树
	 */
	public void inOrder(){
		inOrder(mRoot);
	}
	private void inOrder(BSTNode<T> tree) {
		// TODO Auto-generated method stub
		if (tree!=null) {
			inOrder(tree.left);
			System.out.println(tree.key+" ");
			inOrder(tree.right);
		}
	}
	
	/**
	 * 后序遍历二叉树
	 */
	public void postOrder(){
		postOrder(mRoot);
	}
	private void postOrder(BSTNode<T> tree) {
		// TODO Auto-generated method stub
		if (tree!=null) {
			postOrder(tree.left);
			postOrder(tree.right);
			System.out.println(tree.key+" ");
		}
	}
	
	/**
	 * 查找
	 * 递归实现 查找二叉树tree中键值为key的结点
	 */
	public BSTNode<T> search(T key){
		return search(mRoot,key);
	}	
	private BSTNode<T> search(BSTNode<T> tree, T key) {
		// TODO Auto-generated method stub
		if (tree==null) {
			return tree;
		}
		int cmp=key.compareTo(tree.key);
		if (cmp<0) {
			return search(tree.left, key);
		}else if (cmp>0) {
			return search(tree.right, key);
		}else {
			return tree;
		}
	}

	/**
	 * 查找
	 * 非递归实现 查找二叉树tree中键值为key的结点
	 */
	public BSTNode<T> iterSearch(T key){
		return iterSearch(mRoot,key);
	}
	
	private BSTNode<T> iterSearch(BSTNode<T> tree, T key) {
		// TODO Auto-generated method stub
		while(tree!=null){
			int cmp=key.compareTo(tree.key);
			if (cmp<0) {
				tree=tree.left;
			}else if (cmp>0) {
				tree=tree.right;
			}else {
				return tree;
			}
		}
		return tree;
	}

	/**
	 * 查找最小结点：返回tree为根结点的二叉树的最小结点
	 */
	public T min(){
		BSTNode<T> p=min(mRoot);
		if (p!=null) {
			return p.key;
		}
		return null;
	}		
	private BSTNode<T> min(BSTNode<T> tree) {
		// TODO Auto-generated method stub
		if (tree==null) {
			return null;
		}
		while(tree.left!=null){
			tree=tree.left;
		}
		return tree;
	}

	/**
	 * 查找最大结点：返回tree为根结点的二叉树的最大结点
	 */
	public T max(){
		BSTNode<T> p=max(mRoot);
		if (p!=null) {
			return p.key;
		}
		return null;
	}		
	private BSTNode<T> max(BSTNode<T> tree) {
		// TODO Auto-generated method stub
		if (tree==null) {
			return null;
		}
		while(tree.right!=null){
			tree=tree.right;
		}
		return tree;
	}

	/**
	 * 找结点x的前驱结点：即，查找“二叉树中数据值小于该结点”的“最大结点”
	 */
	public BSTNode<T> predecessor(BSTNode<T> x){
		//如果x存在左孩子，则“x的前驱结点”为“以其左孩子为根的子树的最大结点”
		if (x.left!=null) {
			return max(x.left);
		}
		/**
		 * 如果x没有左孩子，则x有以下两种可能
		 * 1、x是“一个右孩子”，则“x的前驱结点”为“它的父结点”
		 * 2、x是“一个左孩子”，则查找“x的最低的父结点，并且该父结点要具有右孩子”，
		 * 					找到的这个“最低的父结点”就是“x的前驱结点”
		 */
		BSTNode<T> y=x.parent;
		while((y!=null)&&(x==y.left)){
			x=y;
			y=y.parent;
		}
		return y;
	}
	
	/**
	 * 找结点x的后继结点：即，查找“二叉树中数据值大于该结点”的“最小结点”
	 */
	public BSTNode<T> successor(BSTNode<T> x){
		//如果x存在右孩子，则“x的后继结点”为“以其右孩子为根的子树的最小结点”
		if (x.right!=null) {
			return min(x.right);
		}
		/**
		 * 如果x没有右孩子，则x有以下两种可能
		 * 1、x是“一个左孩子”，则“x的后继结点”为“它的父结点”
		 * 2、x是“一个右孩子”，则查找“x的最低的父结点，并且该父结点要具有左孩子”，
		 * 					找到的这个“最低的父结点”就是“x的后继结点”
		 */
		BSTNode<T> y=x.parent;
		while((y!=null)&&(x==y.right)){
			x=y;
			y=y.parent;
		}
		return y;
	}
	
	/**
	 * 删除结点z，并返回被删除的结点
	 * @param tree 二叉树的根结点
	 * @param z 删除的结点
	 */
	public void remove(T key){
		BSTNode<T> z,node;
		if ((z=search(mRoot, key))!=null) {
			if ((node=remove(this,z))!=null) {
				node=null;
			}
		}
	}	
	/**
	 * 删除结点z，并返回被删除的结点
	 * @param bst 二叉树
	 * @param z 删除的结点
	 */	
	private BSTNode<T> remove(BSTree<T> bst, BSTNode<T> z) {
		// TODO Auto-generated method stub
		BSTNode<T> x=null;//真正删除结点的子树；左右子树合体的抽象
		BSTNode<T> y=null;//真正删除的结点
		
		//获取真正删除的结点
		if ((z.left==null) ||(z.right==null)) {
			y=z;
		}else{
			y=successor(z);
		}
		
		//真正删除结点的子树；左右子树合体的抽象
		if (y.left!=null) {
			x=y.left;
		}else{
			x=y.right;
		}
		
		//删除  真正删除结点
		if (x!=null) {
			x.parent=y.parent;
		}
		
		//删除之后把子树这段了，准备焊接
		if (y.parent==null) {
			bst.mRoot=x;
		}else if (y==y.parent.left.left) {
			y.parent.left=x;
		}else {
			y.parent.right=x;
		}
		
		//对删除转移 做值替换
		if (y!=z) {
			z.key=y.key;
		}
		return y;
	}
	
	public void delete(T key){
		//获取要删除的结点
		BSTNode<T> node=search(mRoot, key);
		//如果存在就删除
		if (node!=null) {
			delete(node);
		}
	}
	private BSTNode<T> delete(BSTNode<T> node) {
		//第3种情况，如果同时存在左右子结点
		if (node.left!=null && node.right!=null) {
			//获取后继结点
			BSTNode<T> successor=successor(node);
			//转移后继结点值到当前结点
			node.key=successor.key;
			//把要删除的当前结点设置为后继结点
			node=successor;
		}
		/**
		 * 经过前一步处理，下面只有两种情况，只能是一个结点或者没有结点
		 * 不管是否有子结点，都获取子结点
		 */
		BSTNode<T> child;
		if (node.left!=null) {
			child=node.left;
		}else{
			child=node.right;
		}
		/**
		 * 如果child!=null,就说明有一个结点的情况
		 * 将父结点与子结点关联上
		 */
		if (child!=null) {
			child.parent=node.parent;
		}
		/**
		 * 如果当前结点没有父结点(后继情况到这儿时一定有父结点)
		 * 说明要删除的就是根结点
		 */
		if (node.parent==null) {
			/**
			 * 根结点设置为子结点
			 * 按照前面的逻辑，根只有一个或者没有结点，所以直接赋child
			 */
			mRoot=child;
		}else if (node==node.parent.left) {
			/**
			 * 存在父结点，并且当前结点是左结点
			 * 将父结点的左结点设置为child
			 */
			node.parent.left=child;
		}else {
			/**
			 * 存在父结点，并且当前结点是右结点
			 * 将父结点的右结点设置为child
			 */
			node.parent.right=child;
		}
		//返回被删除的结点
		return node;				
	}

	
	/**
	 * 打印二叉查找树
	 * key:  结点的值
	 * i  :  0,表示该结点是根结点
	 * 		 -1,表示该结点是它的父结点的左孩子
	 * 		  1,表示该结点是它的父结点的右孩子
	 */
	public void print(){
		if (mRoot!=null) {
			print(mRoot,mRoot.key,0);
		}
	}
	private void print(BSTNode<T> tree, T key, int i) {
		// TODO Auto-generated method stub
		if (tree!=null) {
			if (i==0) {//根结点
				System.out.printf("%2d is root\n",tree.key);
			}else {
				System.out.printf("%2d is %2d's %6s child\n",tree.key,key,
						i==1?"right":"left");
			}
			print(tree.left, tree.key, -1);
			print(tree.right, tree.key, 1);
		}
	}
	
	/**
	 * 销毁二叉树
	 */
	public void clear(){
		destory(mRoot);
		mRoot=null;
	}
	private void destory(BSTNode<T> tree) {
		// TODO Auto-generated method stub
		if (tree==null) {
			return ;
		}
		if (tree.left!=null) {
			destory(tree.left);
		}
		if (tree.right!=null) {
			destory(tree.right);
		}
		tree=null;
	}
	
}

二叉查找树的测试程序

package binarySearchTree;

public class BSTreeTest {

	private static final int arr[]={1,5,4,3,2,6};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BSTree<Integer> tree=new BSTree<>();
		
		System.out.println("==依次添加：");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+" ");
			tree.insert(arr[i]);
		}
		
		System.out.println("==前序遍历：");
		tree.preOrder();
		System.out.println("==中序遍历：");
		tree.inOrder();
		System.out.println("==后序遍历：");
		tree.postOrder();
		
		System.out.println("++++遍历树++++");
		tree.print();
		
		System.out.println("==最小值："+tree.min());
		System.out.println("==最大值："+tree.max());
		
		//System.out.println("==删除根结点："+arr[3]);
		//tree.remove(arr[3]);
		
		System.out.println("==中序遍历：");
		tree.inOrder();
		
		//销毁二叉树
		tree.clear();
	}

}