删除二叉排序树的节点java实现

//在节点类中需要准备的方法 public BinarySortTreeNode searchNode(int val) { //如果当前值为指定值，直接返回 if (this.val == val) { return this; //当前值小于指定值 //向右遍历 } else if (this.val < val) { if (this.right != null) { return this.right.searchNode(val); } } else { //反之，向左遍历 if (this.left != null) { return this.left.searchNode(val); } } return null; } public BinarySortTreeNode getParent(int child) { //若目前节点的左子树或右子树的值恰好等于传进来的子节点的值 //直接返回 if ((this.left != null && this.left.val == child) || (this.right != null && this.right.val == child)) { return this; //如果当前值大于传入值 } else if (this.val > child) { if (this.left != null) { //向左遍历 return this.left.getParent(child); } } else { //反之，向右遍历 if (this.right != null) { return this.right.getParent(child); } } return null; }

//在二叉树类中需要准备的方法 void delNode(int val) { if (root == null) { return; } //首先找到需要删除的节点 BinarySortTreeNode node = searchNode(val); if (node == null) { return; } //找到其父节点 BinarySortTreeNode parent = getParent(val); //若父节点为空，则说明为根节点 //若根节点有两颗子树对应情况3 若没有子树对应情况1 //若只有一棵子树 需要特殊处理 if (parent == null) { //只有右子树 -->新的根节点即为其右子树的第一个节点 if (node.left == null && node.right != null) { root = node.right; return; //只有左子树 -->新的根节点即为其左子树的第一个节点 } else if (node.left != null && node.right == null) { root = node.left; return; } } //case1 被删除节点为叶子节点 if (node.left == null && node.right == null) { //若该节点恰好为根节点 直接将根节点置空 if (root == node) { root = null; return; } //若父节点的右节点为该节点，则将右节点置空 if (parent.right == node) { parent.right = null; return; //否则将左节点置空 } else { parent.left = null; } //case3 被删除节点有两颗子树时 } else if (node.left != null && node.right != null) { //我们可以找到该节点的右子树中最小的那个值,赋值给该节点,再删除该节点的右子树的值最小的节点。 //此时由于二叉排序树特性，此时该节点左边仍比该节点小，右边仍比该节点大。 int min = getMinNodeOfTree(node.right); node.val = min; //case2 只有一棵子树时 } else { //case2.1 该节点的左子树不为空 if (node.left != null) { //case 2.1.1 该节点为父节点的左子树 if (parent.left == node) { //将父节点左节点指向该节点的左节点 parent.left = node.left; //case 2.1.2 该节点为父节点的右子树 } else { //将父节点右节点指向该节点的右节点 parent.right = node.left; } //case 2.2 该节点的右子树不为空 } else { //同上 if (parent.left == node) { parent.left = node.right; } else { parent.right = node.right; } } } } int getMinNodeOfTree(BinarySortTreeNode node) { BinarySortTreeNode target = node; //根据二叉排序树特性，直接找到最左边的节点 while (target.left != null) { target = target.left; } //删除该节点 （对应case1） delNode(target.val); //返回最小值 return target.val; }