二叉排序树是基于二分查找步骤生成的二叉树。
设二叉排序树的高度为h，共有n个结点
有如下性质：
1.前h-1层结点全部占满（即为满二叉树）
2.最后一层结点可以通过平移使得整个树转化成完全二叉树

思路：
首先求前h-1层的对比次数
之后求最后一层的对比次数

公式为：

下面给出证明过程：

前言

前面介绍学习的大多是线性表相关的内容，把指针搞懂后其实也没有什么难度。规则相对是简单的。

再数据结构中树、图才是数据结构标志性产物，(线性表大多都现成api可以使用),因为树的难度相比线性表大一些并且树的拓展性很强，你所知道的树、二叉树、二叉排序树，AVL树，线索二叉树、红黑树、B数、线段树等等高级数据结构。然而二叉排序树是所有的基础，所以彻底搞懂二叉排序树也是非常重要的。

树

参考王道数据结构

二叉树也是树的一种，而二叉排序树又是二叉树的一种。

• 树是递归的，将树的任何一个节点以及节点下的节点都能组合成一个新的树。并且很多操作基于递归完成。
• 根节点： 最上面的那个节点(root)，根节点没有前驱节点，只有子节点（0个或多个都可以）
• 层数： 一般认为根节点是第1层(有的也说第0层)。而树的高度就是层数最高(上图层数开始为1)节点的层数
• 节点关系: 父节点：就是链接该节点的上一层节点,孩子节点:和父节点对应，上下关系。而祖先节点是父节点的父节点(或者祖先）节点。兄弟节点：拥有同一个父节点的节点们！
• 度： 节点的度就是节点拥有孩子节点的个数(是孩子不是子孙).而树的度(最大)节点的度。同时，如果度大于0就成为分支节点,度等于0就成为叶子节点（没有子孙）。

相关性质：

• 树的节点数=所有节点度数+1.
• 度为m的树第i层最多有m^i-1个节点。(i>=1)
• 高度而h的m叉树最多（m^h-1）/(m-1)个节点(等比数列求和)
• n个节点的m叉树最小高度[log_m(n(m-1)+1)]

二叉树

二叉树是一树的一种，但应用比较多，所以需要深入学习。二叉树的每个节点最多只有两个节点。

二叉树与度为2的树的区别：

• 一：度为2的的树必须有三个节点以上，二叉树可以为空。
• 二：二叉树的度不一定为2：比如说斜树。
• 三：二叉树有左右节点区分，而度为2的树没有左右节点的区分。

几种特殊二叉树：

• 满二叉树。高度为n的满二叉树有2ⁿ-1个节点
  
• 完全二叉树：上面一层全部满，最下一层从左到右顺序排列
  
• 二叉排序树：树按照一定规则插入排序(本文详解)。
• 平衡二叉树：树上任意节点左子树和右子树深度差距不超过1.

二叉树性质：
相比树，二叉树的性质就是树的性质更加具体化。

• 非空二叉树叶子节点数=度为2的节点树+1.本来一个节点如果度为1.那么一直延续就一个叶子，但如果出现一个度为2除了延续原来的一个节点，会多出一个节点需要维系。所以到最后会多出一个叶子。
• 非空第i层最多有2^i-1个节点。
• 高为h的树最多有2^h-1个节点(等比求和)。
• 完全二叉树若从左往右，从上到下编号如图：
  

二叉排序(搜索)树

概念

前面铺垫那么多，咱们言归正传，详细实现一个二叉排序树。首先要了解二叉排序树的规则：

• 从任意节点开始，节点左侧节点值总比节点右侧值要小。
  例如。一个二叉排序树依次插入15，6，23，7，4，71，5，50会形成下图顺序
  

构造

首先二叉排序树是由若干节点构成。

• 对于node需要这些属性：left，right，和value。其中left和right是左右指针，而value是储存的数据，这里用int 类型。

node类构造为：

class node {//结点
	public int value;
	public node left;
	public node right;
	public node()
	{
	}
	public node(int value)
	{
		this.value=value;
		this.left=null;
		this.right=null;
	}
	public node(int value,node l,node r)
	{
		this.value=value;
		this.left=l;
		this.right=r;
	}			
}

既然节点构造好了，那么就需要节点等其他信息构造成树。有了链表构造经验，很容易得知一棵树最主要的还是root根节点。
所以树的构造为：

public class BinarySortTree {
	node root;//根
	public BinarySortTree()
	{root=null;}
	public void makeEmpty()//变空
	{root=null;}
	public boolean isEmpty()//查看是否为空
	{return root==null;}
	//各种方法
}

主要方法

• 既然已经构造号一棵树，那么就需要实现主要的方法。因为二叉排序树中每个节点都能看作一棵树。所以我们创建方法的是时候加上节点参数(也就是函数对每一个节点都能有效)

findmax(),findmin()

findmin()找到最小节点：

• 因为所有节点的最小都是往左插入，所以只需要找到最左侧的返回即可。

findmax()找到最大节点：

• 因为所有节点大的都是往右面插入，所以只需要找到最右侧的返回即可。
  代码使用递归函数

public node findmin(node t)//查找最小返回值是node，调用查看结果时需要.value
{
	if(t==null) {return null;}
	else if(t.left==null) {return t;}
	else return(findmin(t.left));	
}
public node findmax(node t)//查找最大
{
	if(t==null) {return null;}
	else if(t.right==null) {return t;}
	else return(findmax(t.right));	
}

isContains(int x)

这里的意思是查找二叉查找树中是否存在x。

• 假设我们我们插入x，那么如果存在x我们一定会在查找插入路径的过程中遇到x。因为你可以如果已经存在的点，再它的前方会走一次和它相同的步骤。也就是说前面固定，我来1w次x，那么x都会到达这个位置。那么我们直接进行查找比较即可！

public boolean isContains(int x)//是否存在
{
	node current=root;
	if(root==null) {return false;}
	while(current.value!=x&&current!=null) 
	{
		if(x<current.value) {current=current.left;}
		if(x>current.value) {current=current.right;}
		if(current==null) {return false;}//在里面判断如果超直接返回
	}
	//如果在这个位置判断是否为空会导致current.value不存在报错
	 if(current.value==x) {return true;}		
	return false;		
}

insert(int x)

插入的思想和前面isContains类似。找到自己的位置(空位置)插入。但是又不太一样。你可能会疑问为什么不直接找到最后一个空，然后将current赋值过去current=new node(x)。这样的化current就相当于指向一个new node(x)节点。和树就脱离关系，所以要提前判定是否为空，若为空将它的left或者right赋值即可。

public node insert(int x)// 插入 t是root的引用
{
	node current = root;
	if (root == null) {
		root = new node(x);
		return root;
	}
	while (current != null) {
		if (x < current.value) {
			if (current.left == null) {
				return current.left = new node(x);}
			else current = current.left;}
	    else if (x > current.value) {
			if (current.right == null) {
				return current.right = new node(x);}
			else current = current.right;
		}
	}
	return current;//其中用不到
}

• 比如说上面结构插入51
  

delete(int x)

删除操作算是一个相对较难理解的操作了。
删除节点规则：

• 先找到这个点。这个点用这个点的子树可以补上的点填充该点，然后在以这个点为头删除替代的子节点（调用递归）然后在添加到最后情况（只有一个分支，等等）。
• 首先要找到移除的位置，然后移除的那个点分类讨论，如果有两个儿子，就选右边儿子的最左侧那个点替代，然后再子树删除替代的那个点。如果是一个节点，判断是左空还是右空，将这个点指向不空的那个。不空的那个就替代了这个节点。入股左右都是空，那么他自己变空null就删除了。

删除的节点没有子孙:

• 这种情况不需要考虑，直接删除即可。(途中红色点)。另节点=null即可。
  

左节点为空、右节点为空：

• 此种情况也很容易，直接将删除点的子节点放到被删除位置即可。
  

左右节点均不空

• 这种情况相对是复杂的。因为这涉及到一个策略问题。
  
• 如果拿19或者71节点填补。虽然可以保证部分侧大于小于该节点，但是会引起合并的混乱.比如你若用71替代23节点。那么你需要考虑三个节点(19,50,75)之间如何处理，还要考虑他们是否满，是否有子女。这是个极其复杂的过程。
• 首先，我们要分析我们要的这个点的属性：能够继承被删除点的所有属性。如果取左侧节点(例如17)那么首先能满足所有右侧节点都比他大（右侧比左侧大）。那么就要再这边选一个最大的点让左半枝都比它小。我们分析左支最大的点一定是子树最右侧！
• 如果这个节点是最底层我们很好考虑，可以直接替换值，然后将最底层的点删除即可。但是如果这个节点有左枝。我们该怎么办？
• 这个分析起来也不难，用递归的思想啊。我们删除这个节点，用可以满足的节点替换了。会产生什么样的后果？
  
• 多出个用过的19节点，转化一下，在左子树中删除19的点！那么这个问题又转化为删除节点的问题，查找左子树中有没有能够替代19这个点的。

所以整个删除算法流程为：

代码为

public node remove(int x, node t)// 删除节点
	{
		if (t == null) {
			return null;
		}
		if (x < t.value) {
			t.left = remove(x, t.left);
		} else if (x > t.value) {
			t.right = remove(x, t.right);
		} else if (t.left != null && t.right != null)// 左右节点均不空
		{
			t.value = findmin(t.right).value;// 找到右侧最小值替代
			t.right = remove(t.value, t.right);
		} else // 左右单空或者左右都空
		{
			if (t.left == null && t.right == null) {
				t = null;
			} else if (t.right != null) {
				t = t.right;
			} else if (t.left != null) {
				t = t.left;
			}
			return t;
		}
		return t;
	}

完整代码

二叉排序树完整代码为：

package 二叉树;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

public class BinarySortTree {
	class node {// 结点
		public int value;
		public node left;
		public node right;

		public node() {
		}

		public node(int value) {
			this.value = value;
			this.left = null;
			this.right = null;
		}

		public node(int value, node l, node r) {
			this.value = value;
			this.left = l;
			this.right = r;
		}
	}

	node root;// 根

	public BinarySortTree() {
		root = null;
	}

	public void makeEmpty()// 变空
	{
		root = null;
	}

	public boolean isEmpty()// 查看是否为空
	{
		return root == null;
	}

	public node findmin(node t)// 查找最小返回值是node，调用查看结果时需要.value
	{
		if (t == null) {
			return null;
		} else if (t.left == null) {
			return t;
		} else
			return (findmin(t.left));
	}

	public node findmax(node t)// 查找最大
	{
		if (t == null) {
			return null;
		} else if (t.right == null) {
			return t;
		} else
			return (findmax(t.right));
	}

	public boolean isContains(int x)// 是否存在
	{
		node current = root;
		if (root == null) {
			return false;
		}
		while (current.value != x && current != null) {
			if (x < current.value) {
				current = current.left;
			}
			if (x > current.value) {
				current = current.right;
			}
			if (current == null) {
				return false;
			} // 在里面判断如果超直接返回
		}
		// 如果在这个位置判断是否为空会导致current.value不存在报错
		if (current.value == x) {
			return true;
		}
		return false;
	}

	public node insert(int x)// 插入 t是root的引用
	{
		node current = root;
		if (root == null) {
			root = new node(x);
			return root;
		}
		while (current != null) {
			if (x < current.value) {
				if (current.left == null) {
					return current.left = new node(x);}
				else current = current.left;}
		    else if (x > current.value) {
				if (current.right == null) {
					return current.right = new node(x);}
				else current = current.right;
			}
		}
		return current;//其中用不到
	}

	public node remove(int x, node t)// 删除节点
	{
		if (t == null) {
			return null;
		}
		if (x < t.value) {
			t.left = remove(x, t.left);
		} else if (x > t.value) {
			t.right = remove(x, t.right);
		} else if (t.left != null && t.right != null)// 左右节点均不空
		{
			t.value = findmin(t.right).value;// 找到右侧最小值替代
			t.right = remove(t.value, t.right);
		} else // 左右单空或者左右都空
		{
			if (t.left == null && t.right == null) {
				t = null;
			} else if (t.right != null) {
				t = t.right;
			} else if (t.left != null) {
				t = t.left;
			}
			return t;
		}
		return t;
	}
}

结语

• 这里我们优先学习了树，二叉树，以及二叉搜素树的基本构造。对于二叉搜素树插入查找比较容易理解但是实现的时候要注意函数对参数的引用等等。需要认真考虑。
• 而偏有难度的是二叉树的删除，利用一个递归的思想，要找到特殊情况和普通情况，递归一定程度也是问题的转化(转成自己相同问题，作用域减小)需要思考。
• 下面还会介绍二叉搜素树的三序遍历(递归和非递归).和层序遍历。需要的朋友请持续关注。另外，笔者数据结构专栏欢迎查房。！
• 如果对后端、爬虫、数据结构算法等感性趣欢迎关注我的个人公众号交流：bigsai。回复爬虫，数据结构等有精美资料一份。
  

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。本文详细介绍了二叉排序树的原理，并且提供了Java代码的完全实现。

1 二叉排序树的概述

本文没有介绍一些基础知识。对于常见查找算法，比如顺序查找、二分查找、插入查找、斐波那契查找还不清楚的，可以看这篇文章：常见查找算法详解以及Java代码的实现。对于树和二叉树的概念还不清楚的，建议看这个专栏：树。

假设查找的数据集是普通的顺序存储，那么插入操作就是将记录放在表的末端，给表记录数加一即可，删除操作可以是删除后，后面的记录向前移，也可以是要删除的元素与最后一个元素互换，表记录数减一，反正整个数据集也没有什么顺序，这样的效率也不错。应该说，插入和删除对于顺序存储结构来说，效率是可以接受的，但这样的表由于无序造成查找的效率很低。

如果查找的数据集是有序线性表，并且是顺序存储的，查找可以用折半、插值、斐波那契等查找算法来实现，可惜，因为有序，在插入和删除操作上，为了维持顺序，需要移动大量元素，就需要耗费大量的时间。

有没有一种即可以使得插入和删除效率不错，又可以比较高效率地实现查找的算法呢？这就是二叉排序树。

二叉排序树（Binary Sort Tree），又称为二叉查找树/二叉搜索树（binary search tree）。它是具有下列性质的二叉树：

1. 若它的左子树不空，则左子树上所有节点的值均小于它的根结构的值；
2. 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 它的左、右子树也分别为二叉排序树；
4. 二叉排序树也可以是一个空树。

构造一棵二叉排序树的目的，其主要目的并不是为了排序，而是为了提高查找和插入删除关键字的速度，用以提升数据结构的综合能力。不管怎么说，在一个有序数据集上的查找，速度总是要快于无序的数据集的，而二叉排序树这种非线性的结构，也有利于插入和删除的实现。

2 二叉排序树的构建

2.1 类架构

首先，最简单的节点对象还是需要一个数据域和两个引用域。

另外还需要一个比较器的引用，因为需要对元素进行排序，自然需要比较元素的大小，如果外部传递了比较器，那么就使用用户指定的比较器进行比较，否则，数据类型E必须是Comparable接口的子类，否则因为不能比较而报错。

另外，还需要提供中序遍历的方法，该遍历方法对于二叉排序树的结果将会顺序展示。

public class BinarySearchTree<E> {
    /**
     * 外部保存根节点的引用
     */
    private BinaryTreeNode<E> root;

    /**
     * 自定义比较器
     */
    private Comparator<? super E> cmp;


    /**
     * 树节点的数量
     */
    private int size;

    /**
     * 内部节点对象
     *
     * @param <E> 数据类型
     */
    public static class BinaryTreeNode<E> {

        //数据域
        E data;
        //左子节点
        BinaryTreeNode<E> left;
        //右子节点
        BinaryTreeNode<E> right;

        public BinaryTreeNode(E data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return data.toString();
        }

    }

    /**
     * 指定比较器
     *
     * @param cmp 比较器
     */
    public BinarySearchTree(Comparator<? super E> cmp) {
        this.cmp = cmp;
    }

    /**
     * 空构造器
     */
    public BinarySearchTree() {
    }

    /**
     * 是否是空树
     *
     * @return true 是 ;false 否
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 返回节点数
     *
     * @return 节点数
     */
    public int size() {
        return size;
    }


    /**
     * 对元素进行比较大小的方法,如果传递了自定义比较器,则使用自定义比较器,否则则需要数据类型实现Comparable接口
     *
     * @param e1 被比较的第一个对象
     * @param e2 被比较的第二个对象
     * @return 0 相等 ;小于0 e1 < e2 ;大于0 e1 > e2
     */
    private int compare(E e1, E e2) {
        if (cmp != null) {
            return cmp.compare(e1, e2);
        } else {
            return ((Comparable<E>) e1).compareTo(e2);
        }
    }


    /**
     * 保存遍历出来的节点数据
     */
    List<BinaryTreeNode<E>> str = new ArrayList<>();

    /**
     * 中序遍历,提供给外部使用的api
     *
     * @return 遍历的数据
     */
    public String toInorderTraversalString() {

        //如果是空树,直接返回空
        if (isEmpty()) {
            return null;
        }
        //从根节点开始递归
        inorderTraversal(root);
        //获取遍历结果
        String s = str.toString();
        str.clear();
        return s;
    }

    /**
     * 中序遍历 内部使用的递归遍历方法,借用了栈的结构
     *
     * @param root 节点,从根节点开始
     */
    private void inorderTraversal(BinaryTreeNode<E> root) {

        BinaryTreeNode<E> left = getLeft(root);
        if (left != null) {
            //如果左子节点不为null,则继续递归遍历该左子节点
            inorderTraversal(left);
        }
        //添加数据节点
        str.add(root);
        //获取节点的右子节点
        BinaryTreeNode<E> right = getRight(root);
        if (right != null) {
            //如果右子节点不为null,则继续递归遍历该右子节点
            inorderTraversal(right);
        }
    }

    /**
     * 获取左子节点
     *
     * @param parent 父节点引用
     * @return 左子节点或者null--表示没有左子节点
     */
    public BinaryTreeNode<E> getLeft(BinaryTreeNode<E> parent) {
        return parent == null ? null : parent.left;
    }

    /**
     * 获取右子节点
     *
     * @param parent 父节点引用
     * @return 右子节点或者null--表示没有右子节点
     */
    public BinaryTreeNode<E> getRight(BinaryTreeNode<E> parent) {
        return parent == null ? null : parent.right;
    }

    /**
     * 获取根节点
     *
     * @return 根节点 ;或者null--表示空树
     */
    public BinaryTreeNode<E> getRoot() {
        return root;
    }

}

2.2 查找的方法

查找的方法很简单：

1. 若根节点的关键字值等于查找的关键字，成功，返回true；
2. 否则，若小于根节点的关键字值，递归查左子树；
3. 若大于根节点的关键字值，递归查右子树；
4. 最终查找到叶子节点还是没有数据，那么查找失败，则返回false。

/**
 * 查找,开放给外部使用的api
 */
public boolean contains(E e) {
    return contains(e, root);
}

/**
 * 查找,内部调用的方法,从根节点开始查找
 *
 * @param e    要查找的元素
 * @param root 节点
 * @return false 不存在 true 存在
 */
private boolean contains(E e, BinaryTreeNode<E> root) {
    /*null校验*/
    if (root == null) {
        return false;
    }
    /*调用比较的方法*/
    int i = compare(e, root.data);
    /*如果大于0，则说明e>root.date 继续查询右子树*/
    if (i > 0) {
        return contains(e, root.right);
        /*如果小于0，则说明e<root.date 继续查询左子树*/
    } else if (i < 0) {
        return contains(e, root.left);
    } else {
        /*如果等于0，则说明e=root.date 即查询成功*/
        return true;
    }
}

2.3 插入的方法

有了二叉排序树的查找函数，那么所谓的二叉排序树的插入，其实也就是将关键字放到树中的合适位置而已，插入操作就好像在调用查找的操作，如果找到了那么什么都不做，返回false，如果没找到，则将要插入的元素插入到遍历的路径的最后一点上：

1. 若二叉树为空。则单独生成根节点，返回true。
2. 执行查找算法，找出被插节点的父亲节点。
3. 判断被插节点是其父亲节点的左、右儿子。将被插节点作为叶子节点插入，返回true。如果原节点存在那么什么都不做，返回false。注意：新插入的节点总是叶子节点。

/**
 * 插入,开放给外部使用的api
 *
 * @param e 要插入的元素
 */
public void insert(E e) {
    //返回root,但此时新的节点可能已经被插入进去了
    root = insert(e, root);
}

/**
 * 插入,开放给外部使用的api
 *
 * @param es 要插入的元素的数组,注意,数组元素的顺序存储的位置将会影响二叉排序树的生成
 */
public void insert(E[] es) {
    //返回root,但此时新的节点可能已经被插入进去了
    for (E e : es) {
        root = insert(e, root);
    }

}

/**
 * 插入,内部调用的方法,先从根节点开始递归查找要插入的位置,然后插入
 *
 * @param e    要插入的数据
 * @param root 节点
 * @return 原节点或者新插入的节点
 */
private BinaryTreeNode<E> insert(E e, BinaryTreeNode<E> root) {
    /*没有查找到,那么直接构建新的节点返回,将会在上一层方法中被赋值给其父节点的某个引用,这个插入的位置肯定是该遍历路径上的最后一点
     * 即插入的元素节点肯定是属于叶子节点*/
    if (root == null) {
        size++;
        return new BinaryTreeNode<>(e);
    }
    /*调用比较的方法*/
    int i = compare(e, root.data);
    /*如果大于0，则说明e>root.date 继续查询右子树*/
    if (i > 0) {
        //重新赋值
        root.right = insert(e, root.right);
        /*如果小于0，则说明e<root.date 继续查询左子树*/
    } else if (i < 0) {
        //重新赋值
        root.left = insert(e, root.left);
    } else {
        /*如果等于0，则说明e=root.date 即存在节点 什么都不做*/
    }
    //没查询到最底层,则返回该节点
    return root;
}

2.3.1 测试

现在我们想要构建如下一颗排序二叉树：

首先要插入根节点47，然后是第二层的节点16、73，然后是第三层的节点1、24、59、88，然后是第四层的节点20、35、62、77。每一层内部节点的顺序可以不一致，但是每一层之间的大顺序一定要保持一致，否则虽然中序遍历输出的时候能够正常输出，但是树的结构不能保证。

public class BinarySearchTreeTest {
    BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();

    @Test
    public void insert() {
        //首先要插入根节点47，然后是第二层的节点16,73，然后是第三层的节点1,24,59,88，然后是第四层的节点20,35,62,77。
        // 每一层内部节点的顺序可以不一致，但是每一层之间的打顺序一定要保持一致，否则虽然中序遍历输出的时候能够正常输出,但是树的结构不能保证。
        Integer[] es = new Integer[]{47, 16, 73, 1, 24, 59, 88, 20, 35, 62, 77};
        binarySearchTree.insert(es);
        //中序遍历输出
        System.out.println(binarySearchTree.toInorderTraversalString());

        //查找某个数据是否存在
        System.out.println(binarySearchTree.contains(1));
        System.out.println(binarySearchTree.contains(2));
    }
}

在System.out处打上断点，Debug，可以看到树结构和我们预想的一致，如果改变层间的大顺序，那么使用Debug会发现树结构不如预期。

2.4 查找最大值和最小值

很简单，最左边的节点一定是最小的，最右边的节点一定是最大的。因此查找最小的节点只需要向左递归查找，查找最大的节点只需要向右递归查找。

/**
 * 查找最小的节点
 *
 * @param root 根节点
 * @return 最小的节点
 */
private BinaryTreeNode<E> findMin(BinaryTreeNode<E> root) {
    if (root == null) {
        return null;
        /*如果该节点没有左右子节点，那么该节点就是最小的节点，返回*/
    } else if (root.left == null) {
        return root;
    }
    /*如果该节点存在左子节点，那么继续向左递归查找*/
    return findMin(root.left);
}

/**
 * 查找最大的节点
 *
 * @param root 根节点
 * @return 最大的节点
 */
private BinaryTreeNode<E> findMax(BinaryTreeNode<E> root) {
    if (root == null) {
        return null;
        /*如果该节点没有右子节点，那么该节点就是最大的节点，返回*/
    } else if (root.right == null) {
        return root;
    }
    /*如果该节点存在右子节点，那么继续向右递归查找*/
    return findMax(root.right);
}

2.5 删除的方法

对于二叉排序树的删除，就不是那么容易，我们不能因为删除了节点，而让这棵树变得不满足二叉排序树的特性，所以删除需要考虑多种情况。一共有三种情况需要考虑：

如果查找到的将要被删除的节点没有子节点，那么很简单，直接删除父节点对于该节点的引用即可，如下图的红色节点：

例如，删除20之后：

如果查找到的将要被删除的节点具有一个子节点，那么也很简单，直接绕过该节点将原本父节点对于该节点的引用指向该节点的子节点即可，如下图的红色节点：

例如，删除59之后：

如果查找到的将要被删除的节点具有两个子节点，那么就比较麻烦了，如下图的红色节点：

比如我们需要删除73，那么我们就必须要找出一个已存在的能够替代73的节点，然后删除该节点。实际上该73节点的左子树的最大节点62和右子树的最小节点77都能够替代73节点，即它们正好是二叉排序树中比它小或比它大的最接近73的两个数。

一般我们选择一种方式即可，我们这次使用右子树的最小节点替代要删除的节点，使用77替代73之后的结构如下：

完整的代码如下：

    /**
     * 删除,开放给外部使用的api
     *
     * @param e 要删除的元素
     */
    public void delete(E e) {
        //返回root,但此时可能有一个节点已经被删除了
        root = delete(e, root);
    }

    /**
     * 删除,内部调用的方法,删除分为三种情况: 1、该节点没有子节点 2、该字节仅有一个子节点 3、该节点具有两个子节点
     *
     * @param e    要删除的数据
     * @param root 根节点
     * @return 该节点
     */
    private BinaryTreeNode<E> delete(E e, BinaryTreeNode<E> root) {
        /*没有查找到,那么什么都不做*/
        if (root == null) {
            return null;
        }
        /*调用比较的方法*/
        int i = compare(e, root.data);
        /*如果大于0，则说明e>root.date 继续查询右子树*/
        if (i > 0) {
            //从新赋值
            root.right = delete(e, root.right);
            /*如果小于0，则说明e<root.date 继续查询左子树*/
        } else if (i < 0) {
            //从新赋值
            root.left = delete(e, root.left);
        } else {
            /*如果等于0，则说明e=root.date 即查询成功 开始执行删除*/
            /*如果两个子节点都不为null*/
            if (root.left != null && root.right != null) {
                /*方法1、递归查找最小的节点，然后递归删除  该方法不推荐使用*/
                //root.data = findMin(root.right).data;
                //root.right = delete(root.data, root.right);
                /*方法2、递归查找并删除最小的节点 推荐*/
                root.data = findAndDeleteMin(root.right, root);
                size--;
            } else {
                /*如果一个子节点不为null，则返回该子节点；或者两个子节点都为null，则返回null
                 * 此时该root节点已经被"绕过了"*/
                root = (root.left != null) ? root.left : root.right;
                size--;
            }
        }
        //没查询到最底层,则返回该节点
        return root;
    }

    /**
     * 查找最小的节点并删除
     * 最小的节点肯定不存在两个子节点,有可能没有子节点,有可能存在右子节点
     *
     * @param root   节点
     * @param parent 节点的父节点
     * @return 被删除的最小的节点
     */
    private E findAndDeleteMin(BinaryTreeNode<E> root, BinaryTreeNode<E> parent) {
        //如果节点为null，返回
        if (root == null) {
            return null;
            /*如果节点的左子节点为null,那么该节点就是最小的节点*/
            /*1、该最小节点肯定没有左子节点，因为左子节点比父节点小，但是可能有右子节点*/
            /*2、此时该节点可能作为某个节点的左子节点，也可能作为原父节点的右子节点（即右子树是一颗右斜树），这里需要分开讨论*/
        } else if (root.left == null) {
            //如果该节点是父节点的右子节点,说明还没进行递归或者第一次递归就找到了最小节点.
            //那么此时,应该让该节点的父节点的右子节点指向该节点的右子节点,并返回该节点的数据，该节点由于没有了强引用，会被GC删除
            if (root == parent.right) {
                parent.right = root.right;
            } else {
                //如果该节点不是父节点的右子节点，说明进行了多次递归。
                //那么此时,应该让该节点的父节点的左子节点指向该节点的右子节点,并返回该节点的数据，该节点由于没有了强引用，会被GC删除
                parent.left = root.right;
            }
            //返回最小节点的数据
            return root.data;
        }
        //递归调用,注意此时是往左查找
        return findAndDeleteMin(root.left, root);
    }

2.5.1 测试

public class BinarySearchTreeTest {
    BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();

    @Test
    public void test() {
        //首先要插入根节点47，然后是第二层的节点16,73，然后是第三层的节点1,24,59,88，然后是第四层的节点20,35,62,77。
        // 每一层内部节点的顺序可以不一致，但是每一层之间的打顺序一定要保持一致，否则虽然中序遍历输出的时候能够正常输出,但是树的结构不能保证。
        Integer[] es = new Integer[]{47, 16, 73, 1, 24, 59, 88, 20, 35, 62, 77};
        binarySearchTree.insert(es);
        //中序遍历输出
        System.out.println(binarySearchTree.toInorderTraversalString());

        //查找是否存在
        System.out.println(binarySearchTree.contains(1));
        System.out.println(binarySearchTree.contains(2));

        //移除
        binarySearchTree.delete(73);
        //中序遍历输出
        System.out.println(binarySearchTree.toInorderTraversalString());
    }
}

3 二叉排序树的总结

总之，二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可。

插入删除的时间性能比较好。而对于二叉排序树的查找，走的就是从根节点到要查找的节点的路径，其比较次数等于给定值的节点在二叉排序树的层数。极端情况，最少为1次，即根节点就是要找的节点，最多也不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于，二叉排序树的形状是不确定的。

例如{47, 16, 73, 1, 24, 59, 88}这样的数组，我们可以构建下图左的二叉排序树。但如果数组元素的次序是从小到大有序，如{1, 16, 24, 47, 59, 73, 88}，则二叉排序树就成了极端的右斜树，注意它依然是一棵二叉排序树，如下图右。此时，同样是查找节点88，左图只需要3次比较，而右图就需要7次比较才可以得到结果，二者差异很大。

也就是说，我们希望二叉排序树是比较平衡的，即其深度与完全二叉树相同，均为|log2n+1|(|x|表示不大于x的最大整数)，那么查找的时间复杂也就为O(logn)，近似于折半查找，事实上，上图的左图也不够平衡，明显的左重右轻。而极端情况下的右图,则完全退化成为链表，查找的时间复杂度为O(n)，这等同于顺序查找。

因此，如果我们希望对一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树，防止极端情况的发生。这样我们就引申出另一个问题，如何让二叉排序树平衡的问题。关于这个问题，在后续的平衡二叉树（AVL树)的部分将会详细解释！

相关参考：

1. 《算法》
2. 《算法图解》
3. 《大话数据结构》

如果有什么不懂或者需要交流，可以留言。另外希望点赞、收藏、关注，我将不间断更新各种Java学习博客！