二叉排序树（Java实现）

浅浅的花香味﹌ 2023-07-14 03:20 25阅读 0赞

## 二叉排序树（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的右子树。经过上述步骤，二叉排序树创建完成，很明显，创建二叉树是可以使用到递归的。下面我们来看看这棵树的结构，以帮助大家理解。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70]  
网上很多有关二叉树的实现都用的是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();
        }
    }

运行结果如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 1]  
我们发现，中序遍历的结果是和元素的大小顺序是一致的，说明我们的二叉树创建是正确的。

##### 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.  被删除的节点只有左子树或者只有右子树
3.  被删除的节点既有左子树，也有右子树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 2]

**（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();
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70]: /images/20230529/ea98b106cb2b407681ecf63926340b8d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 1]: /images/20230529/60a63dc6d2114586a8bf37843a712833.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 2]: /images/20230529/cae882a4bbaa47318ae49661b1eff70c.png