二叉排序树（Java实现）
1.二叉排序树的定义
二叉排序树，又叫二叉查找树，如果非空，则具有以下性质：
若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
它的左右子树也分别为二叉排序树。
由定义可得出 二叉排序树的一个重要性质： 中序遍历该二叉树可以得到一个结点值递增的有序序列。
2.结点定义
//二叉排序树的节点 class Node{ int value;//存储的元素值 Node left;//左子树 Node right;//右子树 public Node(int value) {//构造方法 this.value = value; } @Override public String toString() {//为了在遍历时能够清晰地看到遍历结果，重写了toString()方法 return "Node{" + "value=" + value + '}'; } }
3.二叉排序树的基本操作
3.1创建二叉排序树
假设遍历这样一个数组：{7,3,10,12,5,1,9,2}，根据二叉排序树的定义，7为树的根节点，3<7，3就是7的左子树，10>7，10就是7的右子树；12>7，在7的右子树遍历，12>10，12就是10的右子树；5<7，在7的左子树遍历，5>3，5就是3的右子树；1<7，在7的左子树遍历，1<3，1就是3的左子树；9>7，在7的右子树遍历，9<10，9就是10的左子树；2<7，在7的左子树遍历，2<3，继续往3的左子树遍历，2>1，故2就是1的右子树。经过上述步骤，二叉排序树创建完成，很明显，创建二叉树是可以使用到递归的。下面我们来看看这棵树的结构，以帮助大家理解。
网上很多有关二叉树的实现都用的是C、C++，这可能对于一些只会Java的同学不太友好（比如我），所以，我在掌握了创建的思路之后，就自己用Java实现了一波，代码如下，创建二叉树的核心方法如下：
（1）首先在节点类（Node.java）中编写add()方法
//添加节点的方法 public void add(Node node){ if (node==null){//待添加的节点为空，就直接return return; } //判断传入的节点的值，和当前的节点的值之间的关系 if (node.value<this.value){//要插入节点的值<当前节点的值，说明该节点要插到当前节点的左子树 if (this.left==null){//如果当前节点的左子节点为空，直接把插入的节点作为当前节点的左子树 this.left=node; }else {//如果当前节点的左子节点不为空，递归向左子树添加 this.left.add(node); } }else {//要插入节点的值>=当前节点的值,，说明该节点要插到当前节点的右子树 if (this.right==null){//如果当前节点的右子节点为空，直接把插入的节点作为当前节点的右子树 this.right=node; }else {//如果当前节点的左子节点不为空，递归向右子树添加 this.right.add(node); } } }
（2）在二叉排序树类中调用节点类中的add()方法，从而实现添加，这么处理是为了体现面向对象编程的特性和实现类之间的解耦。
class BinarySortTree{//创建二叉排序树 private Node root;//树的根节点 //添加节点的方法 public void add(Node node){ if (root==null){ root=node;//如果root为空，直接让root指向node }else { root.add(node); } } //中序遍历 public void infixOrder(){ if (root!=null){ root.infixOrder(); } else { System.out.println("二叉排序树为空，无法遍历"); } }
(3)测试一下该BST（二叉排序树的英文首字母）的创建：
public class BinarySortTreeDemo { public static void main(String[] args) { int [] arr={7,3,10,12,5,1,9,2}; BinarySortTree binarySortTree = new BinarySortTree(); for (int i = 0; i < arr.length; i++) { binarySortTree.add(new Node(arr[i])); } //中序遍历二叉排序树 binarySortTree.infixOrder(); } }
运行结果如下：
我们发现，中序遍历的结果是和元素的大小顺序是一致的，说明我们的二叉树创建是正确的。
3.2查找二叉排序树的某个节点和某个节点的父节点
设value为要查找的节点的值
若 value == 当前节点的value，则查找成功，返回该节点。
若value < 当前节点的value，则进一步递归查找左子树。
若value > 当前节点的value，则进一步递归查找右子树。
代码实现之：
（1）Node类中编写search()和searcheParent()方法
public Node search(int value){ if (this.value==value){//找到的就是该节点 return this; }else if (value<this.value){//如果要查找的值小于当前节点，向左子树递归查找 //如果左子节点为空，说明再也不会找到，返回null if (this.left==null){ return null; } //如果左子节点不为空，继续递归查找，即左子节点调用该search()方法 return this.left.search(value); }else { //如果右子节点为空，说明再也不会找到，返回null if (this.right==null){ return null; } //如果右子节点不为空，继续递归查找，即左右节点调用该search()方法 return this.right.search(value); } } /** * 查找要某节点的父节点 * @param value 要查找的节点的值 * @return 如果找到就返回，否则就返回null */ public Node searchParent(int value){ //如果当前节点就是要查找的节点的父节点，就返回 if ((this.left!=null&&this.left.value==value)|| (this.right!=null&&this.right.value==value)){ return this; }else { //如果要查找的值小于当前节点的值，并且当前节点的左节点不为空 if (value<this.value&&this.left!=null){ return this.left.searchParent(value);//向左子树递归查找 }else if (value>=this.value&&this.right!=null){ return this.right.searchParent(value);//向右子树递归查找 }else { return null; } } }
这两个查找的方法，在后面删除节点时需要用到。
（2）在BinarySortTree类中调用search()和searchParent()方法
//查找指定的节点 public Node search(int value){ if (root==null){ return null; }else { return root.search(value); } } //查找要节点的父节点 public Node searchParent(int value){ if (root==null){ return null; }else { return root.searchParent(value); } }
3.3删除节点
删除节点有以下三种情况：
- 被删除的节点是叶子节点
- 被删除的节点只有左子树或者只有右子树
- 被删除的节点既有左子树，也有右子树
（1）先来看看第一种情况（删除2||5||9||12）：
（1.1）调用search(int value)方法，查找到要删除的节点，设为targetNode；
（1.2）调用searchParent(int value)方法，查找到要删除的节点的父节点，设为parentNode；
（1.3）根据targetNode是parentNode的左子节点或右子节点来确定是parentNode.left=null还是parentNode.right=null。
（2）再看看第二种情况（删除1）：
（2.1）调用search(int value)方法，查找到要删除的节点，设为targetNode；
（2.2）调用searchParent(int value)方法，查找到要删除的节点的父节点，设为parentNode；
（2.3）就有parentNode.left=targetNode.left或parentNode.right=targetNode.left或parentNode.left=targetNode.right或parentNode.right=targetNode.right这四种基本情况。当然还要考虑，如果要删除的节点没有父节点时，这个节点就是根节点，那么就直接将该节点引用指向它的左子树或右子树，即： root=targetNode.left或root=targetNode.right。
（3）最后看看第三种情况（删除3）：
（3.1）调用search(int value)方法，查找到要删除的节点，设为targetNode；
（3.2）调用searchParent(int value)方法，查找到要删除的节点的父节点，设为parentNode；
（3.3）查找到要删除的节点的右子树中的左子树的最小节点，然后将该最小节点的值保存，并将该值赋给要删除的节点的值，然后把这个最小节点删除，这就实现了逻辑上的删除具有左子树和右子树的节点的操作。
比如要删除这里的3，就找3的右子树，从节点5开始遍历，然后找5的左子树，假设是4，那么就把4的值赋给3，然后把4这个节点删除。
显然，这个思路也是很好理解的，如果不懂的话，可以加我微信交流：973593026
代码实现之：
/** * 返回以node为根节点的二叉排序树的最小节点，并删除这个最小的节点 * @param node * @return */ public int deleteRightTreeMin(Node node){ Node target=node; //循环查找左节点，就会找到最小值 while (target.left!=null){ target=target.left; } //这是target就指向了最小节点 deleteNode(target.value);//删除之 return target.value; } //删除指定的节点 public void deleteNode(int value){ if (root==null){ return; }else { Node targetNode = search(value); if (targetNode==null){//未找到要删除的节点 return; } //如果targetNode没有父节点 if (root.left==null&&root.right==null){ root=null; } //遭到targetNode的父节点 Node parentNode = searchParent(value); //如果要删除的节点是叶子节点 if (targetNode.left==null&&targetNode.right==null){ //判断targetNode是父节点的左子节点还是右子节点 if ((parentNode.left!=null)&&(parentNode.left.value==value)){ parentNode.left=null; }else if ((parentNode.right!=null)&&(parentNode.right.value==value)){ parentNode.right=null; } }else if (targetNode.left!=null&&targetNode.right!=null){//删除有两棵子树的节点 int minVal = deleteRightTreeMin(targetNode.right); targetNode.value=minVal; }else {//删除只有一棵子树的节点 if (targetNode.left!=null){//有左子树 if (parentNode!=null){ //如果targetNode是parentNode的左子节点 if (parentNode.left.value==value){ parentNode.left=targetNode.left; }else {//targetNode是parentNode的右子节点 parentNode.right=targetNode.left; } }else { root=targetNode.left; } }else {//有右子树 if (parentNode!=null){ if (parentNode.left.value==value){ parentNode.left=targetNode.right; }else { parentNode.right=targetNode.right; } }else { root=targetNode.right; } } } } }
4.总结
二叉排序树其实蛮简单的，关键是要掌握好它的思路，这样代码的问题就迎刃而解了，下面是全部的代码，大家有兴趣可以参考一下。另外，我有深入了解Java虚拟机（第三版）的电子版资源，有需要的话加我微信973593026来领取。
package Day37; /** * @Author Zhongger * @Description 二叉排序树，将一颗数组创建成一棵二叉树，并使用中序遍历来遍历二叉树 * @Date 2020.3.7 */ public class BinarySortTreeDemo { public static void main(String[] args) { int [] arr={7,3,10,12,5,1,9,2}; BinarySortTree binarySortTree = new BinarySortTree(); for (int i = 0; i < arr.length; i++) { binarySortTree.add(new Node(arr[i])); } //中序遍历二叉排序树 binarySortTree.infixOrder(); } } class BinarySortTree{//创建二叉排序树 private Node root; /** * 返回以node为根节点的二叉排序树的最小节点，并删除这个最小的节点 * @param node * @return */ public int deleteRightTreeMin(Node node){ Node target=node; //循环查找左节点，就会找到最小值 while (target.left!=null){ target=target.left; } //这是target就指向了最小节点 deleteNode(target.value);//删除之 return target.value; } //查找要删除的节点 public Node search(int value){ if (root==null){ return null; }else { return root.search(value); } } //查找要删除的节点的父节点 public Node searchParent(int value){ if (root==null){ return null; }else { return root.searchParent(value); } } public void deleteNode(int value){ if (root==null){ return; }else { Node targetNode = search(value); if (targetNode==null){//未找到要删除的节点 return; } //如果targetNode没有父节点 if (root.left==null&&root.right==null){ root=null; } //遭到targetNode的父节点 Node parentNode = searchParent(value); //如果要删除的节点是叶子节点 if (targetNode.left==null&&targetNode.right==null){ //判断targetNode是父节点的左子节点还是右子节点 if ((parentNode.left!=null)&&(parentNode.left.value==value)){ parentNode.left=null; }else if ((parentNode.right!=null)&&(parentNode.right.value==value)){ parentNode.right=null; } }else if (targetNode.left!=null&&targetNode.right!=null){//删除有两棵子树的节点 int minVal = deleteRightTreeMin(targetNode.right); targetNode.value=minVal; }else {//删除只有一棵子树的节点 if (targetNode.left!=null){//有左子树 if (parentNode!=null){ //如果targetNode是parentNode的左子节点 if (parentNode.left.value==value){ parentNode.left=targetNode.left; }else {//targetNode是parentNode的右子节点 parentNode.right=targetNode.left; } }else { root=targetNode.left; } }else {//有右子树 if (parentNode!=null){ if (parentNode.left.value==value){ parentNode.left=targetNode.right; }else { parentNode.right=targetNode.right; } }else { root=targetNode.right; } } } } } //添加节点的方法 public void add(Node node){ if (root==null){ root=node;//如果root为空，直接让root指向node }else { root.add(node); } } //中序遍历 public void infixOrder(){ if (root!=null){ root.infixOrder(); } else { System.out.println("二叉排序树为空，无法遍历"); } } } class Node{//节点 int value; Node left; Node right; public Node(int value) { this.value = value; } @Override public String toString() { return "Node{" + "value=" + value + '}'; } /** * 查找要删除的节点 * @param value 要删除的节点的值 * @return 如果找到返回该节点，否则返回null */ public Node search(int value){ if (this.value==value){//找到的就是该节点 return this; }else if (value<this.value){//如果要查找的值小于当前节点，向左子树递归查找 //如果左子节点为空 if (this.left==null){ return null; } return this.left.search(value); }else { //如果右子节点为空 if (this.right==null){ return null; } return this.right.search(value); } } /** * 查找要删除节点的父节点 * @param value 要删除的节点的值 * @return 如果找到就返回该节点，否则就返回null */ public Node searchParent(int value){ //如果当前节点就是要删除的节点的父节点，就返回 if ((this.left!=null&&this.left.value==value)|| (this.right!=null&&this.right.value==value)){ return this; }else { //如果要查找的值小于当前节点的值，并且当前节点的左节点不为空 if (value<this.value&&this.left!=null){ return this.left.searchParent(value);//向左子树递归查找 }else if (value>=this.value&&this.right!=null){ return this.right.searchParent(value);//向右子树递归查找 }else { return null; } } } //添加节点的方法 public void add(Node node){ if (node==null){ return; } //判断传入的节点的值，和当前子树的节点的值的关系 if (node.value<this.value){ //如果当前节点的左子节点为空 if (this.left==null){ this.left=node; }else { //递归向左子树添加 this.left.add(node); } }else {//添加的节点的值大于当前节点的值 if (this.right==null){ this.right=node; }else {//递归向右子树添加 this.right.add(node); } } } //中序遍历 public void infixOrder(){ if (this.left!=null){ this.left.infixOrder(); } System.out.println(this); if (this.right!=null){ this.right.infixOrder(); } } }
