二叉搜索树详解
二叉搜索树（Binary Search Tree）也叫二叉查找树，他是具有下列性质的一种二叉树。
若左子树不空，则左子树上所有节点的值都小于根节点的值；
若右子树不空，则右子树上所有节点的值都大于根节点的值；
任意节点的子树也都是二叉搜索树；
二叉搜索树有一个重要特性就是他的中序遍历结果一定是有序的。如上图，二叉搜索树的中序遍历结果是 [1,3,4,6,8,9] 。
二叉搜索树的查找：
二叉搜索树的查找可以通过递归的方式，也可以通过 while 循环的方式，原理都一样，如下图所示，步骤如下：
如果当前节点为空，则搜索失败。
否则，如果当前节点的值等于要查找的值，则直接返回。
否则，如果要查找的值比当前节点小，就往当前节点的左子树找。如果要查找的值比当前节点值大，就往当前节点的右子树找。
来看下代码：
private TreeNode searchBST(TreeNode root, int val) {
if (root == null) { // 查找不成功。
return null;
} else if (val == root.val) { // 查找成功。
return root;
} else if (val < root.val) // 左子树找。
return searchBST(root.left, val);
else // 右子树找
return searchBST(root.right, val);
}
二叉搜索树的插入：
二叉搜索树插入的时候首先要找到他需要插入的位置，然后在插入，如下图所示，步骤如下：
如果当前节点为空，直接创建一个新的节点返回。
如果要插入的值比当前节点小，就往当前节点的左子树查找插入的位置。
如果要插入的值比当前节点大，就往当前节点的右子树查找插入的位置。
代码如下：
private TreeNode insertBST(TreeNode root, int val) {
if (root == null)// 如果为空，创建一个新的节点。
return new TreeNode(val);
else if (val < root.val)// 插入左子树。
root.left = insertBST(root.left, val);
else // 插入右子树。
root.right = insertBST(root.right, val);
return root;
}
这里使用的是递归的方式，递归在递归章节中有介绍，如果看不明白，还可以使用非递归。
private TreeNode insertBST(TreeNode root, int val) {
TreeNode newNode = new TreeNode(val);// 创建要插入的节点。
if (root == null)// 如果root为空，直接返回。
return newNode;
TreeNode cur = root;// 当前节点，始终是变动的。
while (true) {
if (val < cur.val) {// 在左子树查找插入位置。
if (cur.left == null) {
cur.left = newNode;// 左子树为空，就插入到左子树中。
break;// 终止循环。
} else {
cur = cur.left;// 左子树不为空，就在左子树中查找。
}
} else {// 在右子树查找插入位置，同上。
if (cur.right == null) {
cur.right = newNode;
break;
} else {
cur = cur.right;
}
}
}
return root;
}
二叉搜索树的删除：
二叉树的删除相对来说要麻烦一些，如果删除的是叶子节点，可以直接删除。如果删除的节点只有一个子节点，让这个仅有的子节点替代他。如果删除的节点有两个子节点，就需要考虑删除当前节点后子节点该怎么存放。删除有两种实现方式，一种是直接删除需要删除的节点，一种是使用移形换位法，直接删除有个缺点就是会导致树严重不平衡，在后面我们讲 AVL 树和红黑树的时候使用的都是移形换位法。这里我们先来讲下直接删除是怎么操作的。
在讲解二叉搜索树的删除之前我们先来了解一下二叉树的前驱节点和后继节点。
前驱节点：对一棵二叉树进行中序遍历，遍历后的结果中，当前节点的前一个节点为该节点的前驱节点；
后继节点：对一棵二叉树进行中序遍历，遍历后的结果中，当前节点的后一个节点为该节点的后继节点；
如上图所示，二叉树中节点 4 的前驱节点是 3 ，后继节点是 5 。假设要删除节点 4 ，有两种方式。一种是让待删除节点的右子节点成为他前驱节点的右子节点，这样待删除的节点就只有一个子节点了，如下图所示。
还一种是让待删除节点的左子节点成为他后继节点的左子节点，如图下图所示。
这里的关键是怎么查找一个节点的前驱节点和后继节点，有的同学认为通过打印二叉树的中序遍历结果即可找到，确实可以找到，实际上不需要那么麻烦。一个节点的前驱节点是他左子树中的最大节点，这个节点就是他左子树往右一直走下去的节点。同理一个节点的后继节点就是他右子树的最小节点，这个节点就是他右子树往左一直走下去的节点。
// 查找节点treeNode的前驱节点。
static TreeNode preNode(TreeNode treeNode) {
TreeNode leftBig = treeNode.left;
while (leftBig.right != null)
leftBig = leftBig.right;
return leftBig;
}
// 查找节点treeNode的后继节点。
static TreeNode postNode(TreeNode treeNode) {
TreeNode rightSmall = treeNode.right;
while (rightSmall.left != null)
rightSmall = rightSmall.left;
return rightSmall;
}
找到前驱节点或者后继节点，就可以删除了，删除的步骤如下，假设删除的节点是 p ：
如果
p是叶子节点，则直接删除。如果
p不是叶子节点，并且p仅有一个子节点，只需要让p的父节点变成p子节点的父节点即可，也可以理解为让p的子节点替换p的位置。如果
p有两个子节点，就像上面讲的，有两种方式。一种是让p的右子节点成为他前驱节点的右子节点。还一种是让p的左子节点成为他后继节点的左子节点，两种方式可以随便选一个。
public TreeNode deleteNode(TreeNode root, int val) {
if (root == null)
return null;
if (root.val == val) {
// 这里把 root 是叶子节点和 root 只有一个子节点合并了。
if (root.left == null)
return root.right;
if (root.right == null)
return root.left;
// 这里 root 有两个子节点，找到 root 的前驱节点。
TreeNode leftBig = root.left;
while (leftBig.right != null)
leftBig = leftBig.right;
// 让root的右子节点成为他前驱节点的右子节点。
leftBig.right = root.right;
// 直接返回要删除节点的左子树。
return root.left;
} else if (val < root.val) {
// 要删除的节点在左子树上。
root.left = deleteNode(root.left, val);
return root;
} else {
// 要删除的节点在右子树上。
root.right = deleteNode(root.right, val);
return root;
}
}
删除节点一般有两种实现方式，一种就是上面讲的，但这种有个缺点，就是会严重破坏树的平衡性。还一种就是移形换位，不是把待删除的节点给删除，而是用他的前驱或者后继节点的值来替换他，然后把这个前驱或后继节点给删除，后面我们讲 AVL 树和红黑树的时候会用这种方式。