二叉排序树代码实现（java版）
一、定义
1、一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的结点。
二、基础代码
1、先定义一个节点类，包括左节点、右节点、值三个实例变量。
public class Node {
private Node leftNode;
private Node rightNode;
private int value;
public Node(int value) {
this.value = value;
}
}
2、定义一个二叉排序树类，包括根节点。
public class BinarySortTree {
private Node root;
}
3、开发测试类，用于测试。
（1）测试类中我们定义类一个arr数组，使用for循环生成节点添加到树中，该add()方法的下面会讲到。
public class Test {
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));
}
}
}
三、插入节点
1、实现思路：
在二叉排序树中肯定需要一个add方法来添加节点，如果是一颗空树，我们直接将节点添加到根节点就行了，如果不是空树，我们肯定得递归调用节点的add方法了，因为根据二叉排序数的概念，左叶子节点的值<父节点的值<右节点的值，所以我们每次拿到当前节点，都需要判断当前节点与添加节点的值，看往左节点添加还是右节点添加，递归下去，只到找到要添加节点的位置为空时，递归停止，直接将节点添加。
2、代码如下：
（1）树类的add（）方法
public void addNode(Node node) {
if (root == null) {
root = node;
} else {
root.add(node);
}
}
（2）节点类的add（）方法
public void add(Node node) {
if (node == null) {
return;
}
if (this.value > node.value) {
if (this.leftNode == null) {
this.leftNode = node;
} else {
this.leftNode.add(node);
}
} else {
if (this.rightNode == null) {
this.rightNode = node;
} else {
this.rightNode.add(node);
}
}
}
四、遍历排序二叉树 上面我们实现了添加节点，接下来实现排序二叉树的遍历，根据定义和插入节点可知，要想得到一个有序的遍历，只有中序排序才能实现，因为中序遍历是按照左节点，然后父节点，最后右节点的顺序遍历，我们插入就是实现了左节点值<父节点值<右节点。如果使用前序或者后序遍历，出来的就无序了。
1、在树类中添加遍历方法
（1）遍历时，我们需要先判断根节点是否为空，如果为空，直接返回即可，不为空再调用节点类的排序方法。
public void middleSort() {
if (root == null) {
return;
}
root.middleSort();
}
2、在节点类中添加遍历方法
（1）先判断左节点是否有值，如果有，我们就让左节点接着调用遍历方法，只到左节点为空了，我们打印当前节点的值，当前节点就是父节点，然后再判断右节点，不为空就递归调用。
public void middleSort() {
if (this.leftNode != null) {
this.leftNode.middleSort();
}
System.out.println(this.value);
if (this.rightNode != null) {
this.rightNode.middleSort();
}
}
五、查找节点
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版实现的总结
腾讯云开发者
