定义
二叉搜索树(Binary Search Tree,BST),也称为二叉排序树或二叉查找树。
相较于普通的二叉树，非空的二叉搜索树有如下性质：
- 非空左子树的所有键值小于其根结点的键值；
- 非空右子树的所有键值大于其根结点的键值；
- 左右子树均为二叉搜索树；
- 树中没有键值相等的结点。
可以看到，二叉搜索树的性质很鲜明，这也使得二叉树也有了实际意义。
二叉搜索树的常用操作
对于二叉搜索树，除了常规的4种遍历之外，还有如下一些关键的操作值得我们去关注。
二叉树的存储结构实现
对于二叉树，我们还是习惯的选择采用链式存储结构实现。
二叉树结点定义
二叉搜索树最大的特点，就是他的元素是可以比较大小的。这一点是需要注意的地方。
/**
* Created by engineer on 2017/10/26.
* <p>
* 二叉搜索树树结点定义
*/
public class TreeNode<T extends Comparable<T>> {
// 数据域
private T data;
// 左子树
public TreeNode<T> leftChild;
// 右子树
public TreeNode<T> rightChild;
public TreeNode(T data) {
this(null, data, null);
}
public TreeNode(TreeNode leftChild, T data, TreeNode rightChild) {
this.leftChild = leftChild;
this.data = data;
this.rightChild = rightChild;
}
public T getData() {
return data;
}
public TreeNode<T> getLeftChild() {
return leftChild;
}
public TreeNode<T> getRightChild() {
return rightChild;
}
public void setData(T data) {
this.data = data;
}
}
二叉搜索树插入
有了根节点，我们就可以根据二叉树的性质，从根节点出发，构建出一颗二叉树。
/**
* 树中插入元素
*
* @param value
*/
void insert(T value) {
if (value == null) {
return;
}
root = insert(root, value);
}
private TreeNode<T> insert(TreeNode<T> node, T value) {
if (node == null) {
// 树为空,则创建根节点
return new TreeNode<>(value);
} else {
if (compare(node, value) < 0) { // 插入值比根节点小，在左子树继续创建二叉搜索树
node.leftChild = insert(node.getLeftChild(), value);
} else if (compare(node, value) > 0) { // 插入值比根节点大，在右子树继续创建二叉搜索树
node.rightChild = insert(node.getRightChild(), value);
}
}
return node;
}
private int compare(TreeNode<T> node, T value) {
return value.compareTo(node.getData());
}
根据二叉搜索树的特性，我们很容易使用递归实现二叉树的插入操作；总的来说，就是每次插入一个结点，从根节点出发作比较，小的就往左子树插，大的就往右子树插。这和二叉搜索树的定义时完全一致的。
我们可以简单测试一下，这个insert方法的正确性。
测试二叉搜索树插入操作
public class BinarySearchTreeTest {
private static Integer[] arrays = new Integer[]{10, 8, 3, 12, 9, 4, 5, 7, 1,11, 17};
public static void main(String[] args) {
BinarySearchTree<Integer> mSearchTree = new BinarySearchTree<>();
for (Integer data : arrays) {
mSearchTree.insert(data);
}
// 打印二叉树的三种遍历顺序
mSearchTree.printTree();
}
}
关于树的遍历已在上文中详细分析，此处不再做深入探讨
这里定义了一个随机数组，这个将这个数组的按序插入到树中，并按照树的三种遍历结构打印树。按照这个数组我们将构建出如下所示的一颗二叉搜索树：
看一下程序输出的遍历结果。
前序遍历：10 8 3 1 4 5 7 9 12 11 17
中序遍历：1 3 4 5 7 8 9 10 11 12 17
后序遍历：1 7 5 4 3 9 8 11 17 12 10
可以看到，遍历结果和我们画出来二叉树是一致的，因此可以验证插入方法是正确的。
查找
通过插入操作，我们已经实现了一颗二叉搜索树，下面就来看看如何从树中查找元素。
- 查找最大值与最小值
根据二叉搜索树的特点，我们知道在一颗二叉搜索树上，最小的值一定在最最左边的结点上，而最大值一定在最最右边的结点上。因此，查找二叉树最值就变得非常容易了。
/**
* 查找最大值
*
* @return
*/
public T findMax() {
if (isEmpty()) return null;
return findMax(root);
}
/**
* 从特定结点开始寻找最大值
*
* @param node
* @return
*/
private T findMax(TreeNode<T> node) {
TreeNode<T> temp = node;
while (temp.getRightChild() != null) {
temp = temp.getRightChild();
}
return temp.getData();
}
/**
* 查找最小值
*
* @return
*/
public T findMin() {
if (isEmpty()) return null;
return findMin(root);
}
/**
* 从特定结点开始寻找最小值
*
* @param node
* @return
*/
private T findMin(TreeNode<T> node) {
TreeNode<T> temp = node;
while (temp.getLeftChild() != null) {
temp = temp.getLeftChild();
}
return temp.getData();
}
可以看到，算法实现非常简单，就是不断后移结点找到没有子树的结点，就是最边界位置的结点了。
- 查找特定值
在二叉搜索树中，怎样快速找到一个值为特定元素的结点呢？想想我们是怎样实现结点插入的？这个问题就很简单了。
递归实现，查找特定结点
**
/**
* find 特定值 递归实现
*
* @param value
* @return
*/
public TreeNode<T> find(T value) {
if (isEmpty()) {
return null;
} else {
return find(root, value);
}
}
private TreeNode<T> find(TreeNode<T> node, T value) {
if (node == null) {
// 当查找一个不在树中元素时，抛出异常
throw new RuntimeException("the value must not in the tree");
}
if (compare(node, value) < 0) {
// 小于根节点时，从去左子树找
return find(node.getLeftChild(), value);
} else if (compare(node, value) > 0) {
// 大于根节点时，从右子树找
return find(node.getRightChild(), value);
} else {
// 刚好等于，找到了
return node;
// 剩下还有一种情况，就是不等于，也就是所查找的元素不在树中
}
}
查找的实现思路，总体上和插入是一致的；无非就是做不同的操作；这里需要注意的是，为了程序的健壮性，我们还得考虑如果查找的元素不在树中这种情况。
迭代实现，查找特定值
有了前面查找最大值、最小值的经验，我们也可以考虑使用迭代算法实现查找指定元素的算法。
/**
* 查找特定值-非递归实现
*
* @param value
* @return 结点
*/
public TreeNode<T> findIter(T value) {
TreeNode<T> current = root;
while (current != null) {
if (compare(current, value) < 0) {
current = current.getLeftChild();
} else if (compare(current, value) > 0) {
current = current.getRightChild();
} else {
return current;
}
}
// current为null,说明所查找的元素不在tree里
return null;
}
这里同样测试一下，查找方法的正确性：
System.out.printf("\nfind value %d in mSearchTree \n", 12);
TreeNode mTreeNode = mSearchTree.find(12);
TreeNode mTreeNode_1 = mSearchTree.findIter(12);
System.out.println("递归实现结点 = :" + mTreeNode + ", value=" + mTreeNode.getData());
System.out.println("非递归实现结点= :" + mTreeNode_1 + ", value=" + mTreeNode_1.getData());
System.out.println("\nfind the max value in mSearchTree = " + mSearchTree.findMax());
System.out.println("find the min value in mSearchTree = " + mSearchTree.findMin());
输出：
find value 12 in mSearchTree
递归实现结点 = :com.avaj.datastruct.tree.bst.TreeNode@4b67cf4d, value=12
非递归实现结点= :com.avaj.datastruct.tree.bst.TreeNode@4b67cf4d, value=12
find the max value in mSearchTree = 17
find the min value in mSearchTree = 1
我们分别用递归和迭代两种方式去查找 12，可以看到两次找到是同一个对象，这个对象的值为12；找到的最大值和最小值也是正确的；因此查找功能的实现是正确的。
删除结点
从二叉搜索树中，删除一个结点可以算是最复杂的操作了，主要是因为所要删除的结点，所处的位置被删除后，依然需要保持整棵树依然为二叉树，因此需要就不同的情况就像分析。
就拿我们上面创建的这颗二叉树来说，如果要删除的结点是1,7,11,17 这样的叶子结点，就很容易了；让其父结点指向为null即可；而如果是4,5 这样包含一颗子树的结点，换个角度来说，这其实就是单向链表，从单向链表中间位置删除一个结点也比较容易；最麻烦的就是如果要删除的结点是10,8,3,12 这类结点包含左右子树，我们就需要从左子树中找一个最大值，或者是右子树中的最小值来替代这个值。总结一下删除结点的操作：
- 叶子结点：直接删除，其父结点指向null
- 包含一个孩子的结点 ：父结点指向要删除结点的自结点（相当于链表中间删除一个元素）；
- 包含左右子树的结点：右子树最小值或左子树最大值替换此结点
结合以上分析，得出从二叉搜索树中删除结点的实现。
/**
* 从树中删除值为value 的特定结点
*
* @param value
*/
public void delete(T value) {
if (value == null || isEmpty()) {
return;
}
root = delete(root, value);
}
private TreeNode<T> delete(TreeNode<T> node, T value) {
// 结点为空，要出删除的元素不在树中
if (node == null) {
return node;
}
if (compare(node, value) < 0) { // 去左子树删除
node.leftChild = delete(node.getLeftChild(), value);
} else if (compare(node, value) > 0) { // 去右子树删除
node.rightChild = delete(node.getRightChild(), value);
} else { // 要删除的就是当前结点
if (node.getLeftChild() != null && node.getRightChild() != null) {// 被删除的结点，包含左右子树
T temp = findMin(node.getRightChild()); // 得到右子树的最小值
node.setData(temp); //右子树最小值替换当前结点
node.rightChild = delete(node.getRightChild(), temp); // 从右子树删除这个最小值的结点
} else {// 被删除的结点，包含一个子树或没有子树
if (node.getLeftChild() != null) {
node = node.getLeftChild();
} else {
node = node.getRightChild();
}
}
}
return node;
}
这里选择使用右子树的最小值替换，是因为删除这个最小值的结点会比较容易，因为他一定是不会是一个包含左右子树的结点。
同样，这里测试一下删除结点的功能：
// 删除只带一个子树的结点
mSearchTree.delete(4);
mSearchTree.printTree();
System.out.println();
// 删除带左右子树的根节点
mSearchTree.delete(10);
mSearchTree.printTree();
输出：
前序遍历：10 8 3 1 5 7 9 12 11 17
中序遍历：1 3 5 7 8 9 10 11 12 17
后序遍历：1 7 5 3 9 8 11 17 12 10
前序遍历：11 8 3 1 5 7 9 12 17
中序遍历：1 3 5 7 8 9 11 12 17
后序遍历：1 7 5 3 9 8 17 12 11
通过和我们一开始画出来的树相比较，发现是对应的。
二叉搜索树的高度
最后，再来看看如何计算一颗二叉搜素树的度。
public int getTreeHeight() {
if (isEmpty()) {
return 0;
}
return getTreeHeight(root);
}
private int getTreeHeight(TreeNode<T> node) {
if (node == null) {
return 0;
}
int leftHeight = getTreeHeight(node.getLeftChild());
int rightHeight = getTreeHeight(node.getRightChild());
int max = leftHeight > rightHeight ? leftHeight : rightHeight;
// 得到左右子树中较大的返回.
return max + 1;
}
顺便来算一算，到最后我们创建的树，经过插入删除操作高度变成了多少。
System.out.println("\n\nTree's height =" + mSearchTree.getTreeHeight());
输出：
Tree's height =5
可以看到，由于结点4被删除，树由原来的6层变成了5层，结果是正确的！
好了，二叉搜索树的分析就是这些了！文中所有源码地址.
