2. 删除结点
删除二叉搜索树的结点，我们必需在删除该结点后保证这个二叉树还是为二叉搜索树，因此这样的操作是比较难的。
二叉搜索树的难点(重点)就在于删除节点，我们可以设根节点为 root 待删除的节点为 cur，待删除的节点的双亲结点为 parent。因此会出以下情况：
- cur.left为null时
- cur.right为null时
- cur.left不为空并且cur.right不为空时:
(1).cur.left为null
当cur.left为null时分为3种情况：
情况1，cur 是 root 时，需要将root=cur.right。
编辑
if (cur.left == null) { if (cur == root) { root = cur.right; } }
情况2，cur不是root，cur是parent.left时，我们需要将parent.left = cur.right。
编辑
if (cur.left == null) { if (cur == parent.left) { parent.left = cur.right; } }
情况3，cur不是root，cur是parent.right，我们需要将parent.right = cur.right。
编辑
if (cur.left == null) { if (cur == parent.right) { parent.right = cur.right; } }
因此把cur.left为null的三种情况综合起来:
if (cur.left == null) { if (cur == root) { root = cur.right; }else if(cur == parent.left) { parent.left = cur.right; }else { parent.right = cur.right; } }
(2).cur.right为null
cur.right为null，也分为3种情况：
情况1，cur是root，root=cur.left
编辑
if(cur.right == null) { if(cur == root) { root = cur.left; } }
情况2，cur不是root，cur是parent.left，parent.left = cur.left
编辑
if(cur.right == null) { if(cur == parent.left) { parent.left = cur.left; } }
情况3，cur不是root，cur是parent.right，parent.right = cur.left
编辑
if(cur.right == null) { if(cur == parent.right) { parent.right = cur.left; } }
把cur.right = null的三种情况综合起来，就能写出以下代码:
if(cur.right == null) { if (cur == root) { root = cur.left; }else if(cur == parent.left) { parent.left = cur.left; }else { parent.right = cur.left; } }
(3).cur.left不为空且cur.right不为空
当删除的结点左右子树都不为空的情况下，我们就得使用“替换法”来替换被删节点，被替换的节点为被删除节点的右子树的左侧子树的最后一个左子树是最适合用来替换被删节点的，无论哪种情况都是这样，大家可以自行画图测试一番。
目前我们知道了 cur 为要删除的结点，因此替换的结点我们设为 target ，替换节点的双亲结点为 targetParent ，设置替换节点双亲结点是为了当替换节点为空时，我们能找到替换节点！
当 cur.right 的最左子树为 target 时：
程序的结束条件为：target.left != null ，直接将该树的值赋值给cur的值即 cur.val = target.val。替换节点删除操作为：targetParent.left = target.right。
编辑
cur.right 的最左侧不为 target 时：
程序的结束条件为：target.left != null ，直接将该树的值赋值给cur的值即 cur.val = target.val。替换节点删除操作为：targetParent.right = target.right。
编辑
因此，综合上方把cur.left不为空且cur.right不为空可以写成以下代码:
TreeNode target = cur.right; TreeNode targetParent = cur; while (target.left != null) {//终止条件为最左侧为空 targetParent = target; target = target.left; } cur.val = target.val;//把cur的值替换为target的值 if (target == targetParent.left) { targetParent.left = target.right;//最左侧值等于target }else { targetParent.right = target.right;//最左侧值不等于target }
把删除节点中所有代码综合起来，我们就能写出完整的删除操作。当然，我们得先找到删除的节点又使用到了 findNode 的操作，我把删除节点的操作封装到一个名为 removeNode 的方法里面，以下为完整代码:
//查找节点 public void delNode(int key) { TreeNode cur = root; TreeNode parent = null; while(cur != null) { if (cur.val == key) { removeNode(cur,parent);//调用删除节点方法 }else if(cur.val > key) { parent = cur; cur = cur.left; removeNode(cur,parent);//调用删除节点方法 }else { parent = cur; cur = cur.right; removeNode(cur,parent);//调用删除节点方法 } } } //删除节点 public void removeNode(TreeNode parent,TreeNode cur) { while (cur != null) { if (cur.left == null) { if (cur == root) { root = cur.right; }else if(cur == parent.left) { parent.left = cur.right; }else { parent.right = cur.right; } }else if(cur.right == null) { if (cur == root) { root = cur.left; }else if(cur == parent.left) { parent.left = cur.left; }else { parent.right = cur.left; } }else{ TreeNode target = cur.right; TreeNode targetParent = cur; while (target.left != null) { targetParent = target; target = target.left; } cur.val = target.val; if (target == targetParent.left) { targetParent.left = target.right; }else { targetParent.right = target.right; } } } }
