删除节点只有一个子节点，删除该节点后，该节点的子节点变为父节点的子节点，如果删除节点时父节点的左节点，那么父节点的左节点指向该节点的子节点，反之则右节点指向删除节点的子节点。
删除节点有两个字节点，删除了该节点后，则需要选择一个后继节点，并且还不破坏该二叉树的特性(左节点要小于右节点)，一般是从删除节点的右节点中找到一个后继节点，而这个节点是右子树的最小值。
public boolean delete(int key) { Node current = root; Node parent = root; boolean isLeftChild = true; //找到被删除的节点，并标识该节点是否为左节点 while (current.index != key) { parent = current; if (key < current.index) { isLeftChild = true; current = current.leftNode; } else { isLeftChild = false; current = current.rightNode; } if (current == null) { return false; } } //第一种情况，删除节点为子节点 if (current.leftNode == null && current.rightNode == null) { if (current == root) { root = null; } else { if (isLeftChild) { parent.leftNode = null; } else { parent.rightNode = null; } } } else if ((current.leftNode != null && current.rightNode == null) || (current.leftNode == null && current.rightNode != null)) { //第二中情况，删除节点只包含一个子节点，则将子节点移动动当前节点中 if (current.rightNode == null) {//删除的节点的左节点有值，右节点为空 if (root == current) { root = current.leftNode; } else { if (isLeftChild) { parent.leftNode = current.leftNode; } else { parent.rightNode = current.leftNode; } } } else {//删除的节点的右节点有值，左节点为空 if (root == current) { root = current.rightNode; } else { if (isLeftChild) { parent.leftNode = current.rightNode; } else { parent.rightNode = current.rightNode; } } } } else if (current.leftNode != null && current.rightNode != null) { //第三种情况，删除节点中有左右两个节点 //找到后继节点 Node processer = processer(current); if (current == root) {//删除是根节点，则 root = processer; } else { if (isLeftChild) { parent.leftNode = processer; } else { parent.rightNode = processer; } } //选中的节点的左节点与删除节点的左节点相连 processer.leftNode = current.leftNode; } return true; } //找到后继节点 private Node processer(Node delNode) { Node parent = delNode; Node success = delNode; Node current = delNode.rightNode; while (current != null) { // 后继节点父节点首先保存后继节点的状态 parent = current; success = current; // 后继节点 不断的向左更新 current = current.leftNode; } // 假如我们找到的后继节点不直接是 要删除节点的右节点 而是在其右节点那条子树上面最小的一个节点 if (success != delNode.rightNode) { //后继节点的父节点断开其与后继节点左边的引用，重新连接上后继节点的右子节点（因为后继节点是没有左子节点的，锁以要保存之前树的状态，还要把后继节点的右子节点处理一下，不管 其存在不存在） parent.leftNode = success.rightNode; // 这时候后继节点的右边已经空了 上一条语句已经将其给了自己父节点的左子节点 然后让后继节点的右边 连接要删除节点的右子树 success.rightNode = delNode.rightNode; } return success; }