五、查找节点
1、查找某个节点
（1）在树类中添加查找方法，跟上面的写法一样，根节点不存在返回空，存在调用节点的查找方法。
public Node search(int value) { if (root == null) { return null; } return root.search(value); }
（2）在节点类中添加查找方法。我们先判断当前节点的值是否与要查的值相等，相等的话直接返回当前节点就结束了，本来不想等的话，我们应该同时判断左节点、右节点的值是否符合，但这是二叉排序数，左子树的值肯定小于右子树的值，我们只需要将父节点的值与所传值进行比较，所传值大，我们去右边找，反之亦然，这样的效率就相当于我们写的二分查找，节约了一半的时间（只有平衡二叉树才能真正达到）
public Node search(int value) { if (this.value == value) { return this; } else if (this.value > value) { if (this.leftNode != null) { return leftNode.search(value); } } else if (this.value < value) { if (this.rightNode != null) { return this.rightNode.search(value); } } return null; }
2、查找某个节点的父节点
（1）在树类中添加查找父节点方法，跟上面的写法一样，根节点不存在返回空，存在调用节点的父节点查找方法。
public Node searchParent(int value) { if (root == null) { return null; } return root.searchParent(value); }
（2）在节点类中添加查找父节点方法，与查找某个节点的方法区别是，对于查找父节点，我们拿到当前节点后，比较的是当前节点的子节点值是否与所传参数值相等，相等返回当前节点。因为子节点与所传值相等了，当前这个节点就是父节点了。
//查找该节点的父节点,如果是根节点以及不存在值将会返回null public Node searchParent(int value) { //如果该Node左节点或者右节点匹配参数值，返回当前节点 if ((this.leftNode != null && this.leftNode.value == value) || (this.rightNode != null && this.rightNode.value == value)) { return this; } else { //该节点的值大于参数值，去左边找 if (this.value > value && this.leftNode != null) { return leftNode.searchParent(value); } else if (this.value < value && this.rightNode != null) { return rightNode.searchParent(value); } } return null; }
六、删除节点
1、其删除一个节点需要考虑对应节点的状态，具体的说就是，是否存在左右节点，等等。需要按照以下情况讨论。
（1）.查找待删除节点，在查找的同时需要记录一下待删除节点的父亲。
（2）.如果待删除节点的左右节点都不存在，那么直接删除。
（3）.如果待删除节点左子树存在右子树不存在，或者左子树不存在右子树存在。直接将其子树中存在的一边候补上来即可。
（4）.如果待删除节点左右子树都在，这个情况是最复杂的。需要按照二叉排序树的性质从其左子树或者有子树中选择节点补到待删除节点的位置。 如果从左子树中选，就应该选择左子树中最右边的那个叶子节点（即中序排序中待删除节点的前驱节点） 如果从右子树中选，就应该选择有子树中最左边的那个叶子节点（即中序排序中待删除节点的后继节点）。
2、代码如下
（1）查找当前节点和查找父节点的方法在上面有提到。
（2）当待删除节点同时左右子树都存在时，我们要是选择左子树上的节点补上去，根据定义，为了保证删除后还是一个二叉排序数，肯定选择中序排序时，该删除节点的前一个，由定义可知，前一个肯定是左子树最右边的叶子节点（前躯），可自行实现，此处实现为查找出待删除节点右子树中找中序排序的后继节点。代码见下一步。
public void delete(int value) { //查找待删除节点 Node target = search(value); if (target != null) { //在查找的同时需要记录一下待删除节点的父亲 Node parent = searchParent(value); //2.如果待删除节点的左右节点都不存在，那么直接删除。 if (target.leftNode == null && target.rightNode == null) { if (parent.leftNode != null && parent.leftNode.value == value) { parent.leftNode = null; } else { parent.rightNode = null; } //3、待删除的左右节点都存在情况 } else if (target.rightNode != null && target.leftNode != null) { //此处删除后继节点，注意前驱和后继节点是中序排列后的该删除节点的前一个或者后一个节点。 int min = deleteMinNode(target.rightNode); target.value = min; //待删除节点左子树存在右子树不存在,直接将其子树中存在的一边候补上来即可 } else { if (target.rightNode != null) { if (parent.leftNode != null && parent.leftNode.value == value) { parent.leftNode = target.rightNode; } else { parent.rightNode = target.rightNode; } } else { if (parent.leftNode != null && parent.leftNode.value == value) { parent.leftNode = target.leftNode; } else { parent.rightNode = target.leftNode; } } } } }
（3）待删除节点右子树中找中序排序的后继节点方法，找到后删除并返回节点值即可，但是要考虑两种情况，一是该后继节点右子树可能存在，要是存在我们需要返回后继节点值后，把后继节点右子树节点补到后继节点上，我们直接再次调用删除节点方法，把后继节点传进去，即可考虑到这种情况，代码如下：
private int deleteMinNode(Node node) { Node target = node; while (target.leftNode != null) { target = target.leftNode; } //删除该节点 delete(target.value); return target.value; }
七、测试
1、调用以上方法进行灵活测试即可，示例如下，其余自行实现即可。
public static void main(String[] args) { int[] arr = new int[]{7, 3, 10, 12, 5, 1, 9}; BinarySortTree tree = new BinarySortTree(); for (int i : arr) { //添加节点 tree.addNode(new Node(i)); } //遍历 tree.middleSort(); //查找某个节点 Node search = tree.search(9); //删除某个节点 tree.delete(3); }
八、总结
以上就是对于二叉排序树java版实现的总结，
