数据结构（5）树形结构——二叉搜索树（JAVA代码实现）

桃扇骨 2023-09-23 16:13 29阅读 0赞

## 5.1.概述 ##

二叉搜索树，也叫二叉查找树、二叉排序树，顾名思义，这种二叉树是专门用来进行数据查找的二叉树。二叉搜索树的查找其实就是二分查找。

**二叉搜索树的定义：**

*  二叉搜索树可以为空
 *  如果二叉搜索树不为空，那么每个有孩子结点的结点，其左孩子的值一定要小于它，其右孩子的值一定要大于它。

**二叉搜索树的操作集：**

既然是专门用来进行查找的二叉搜索树的操作集自然就是增删查，没有改，因为二叉搜索树中的元素都是排序好的，如果直接就地改动某个节点很可能破坏有序性，所以当发现插入的数据有误的时候先删除，再重新插入，一定要保证数据经过了插入流程，这样数据才会在对的位置，才能保证整棵的有序性。

boolean find(Object target);
    Object findMin();
    Object findMax();
    void insert(Object data);
    void delete(Object data);

## 5.2.操作 ##

### 5.2.1.节点 ###

节点实体如下：

public class Node {
        //数据域
        private int data;
        //指针域
        private Node left;
        private Node right;
    
        //遍历标志
        private boolean isOrder;
    
        {
            isOrder=false;
        }
    
        public Node(){
    
        }
    
        public Node(int data){
            this.data=data;
        }
        public int getData() {
            return data;
        }
    
        public void setData(int data) {
            this.data = data;
        }
    
        public Node getLeft() {
            return left;
        }
    
        public void setLeft(Node left) {
            this.left = left;
        }
    
        public Node getRight() {
            return right;
        }
    
        public void setRight(Node right) {
            this.right = right;
        }
    
        public boolean isOrder() {
            return isOrder;
        }
    
        public void setOrder(boolean order) {
            isOrder = order;
        }
    }

### 5.2.2.插入 ###

假设插入35，从根节点开始比较，

35>30，属于30的右子树，30的右孩子不为空，继续向下走，

35<41，属于41的左子树，41的左孩子不为空，继续向下走，

35>33，属于33的右子树。33的右孩子为空，35是33的右孩子。

![1d309c2f1a0041f3be255215038bdc0c.png][]

代码示例：

//记录根节点
        private static Node root=null;
        //用于寻路的指针
        private static Node flag=null;
        public static void insert(Node node){
            if(root==null){
                System.out.println("我插入"+node.getData()+"作为根节点");
                root=node;
            }
    
            flag=root;
    
            while (node.getData()<flag.getData()){
                if(flag.getLeft()==null) {
                    System.out.println("我在"+flag.getData()+"右边插入一个"+node.getData());
                    flag.setLeft(node);
                }
                flag = flag.getLeft();
            }
    
            while(node.getData()>flag.getData()){
                if(flag.getRight()==null) {
                    System.out.println("我在"+flag.getData()+"右边插入一个"+node.getData());
                    flag.setRight(node);
                }
                flag = flag.getRight();
            }
        }

### 5.2.3.查找 ###

#### 1.查找某个值是否存在 ####

二叉搜索树的查找其实就是借助数据结构实现了二分查找，如果当前节点的值大于要查找的值，说明要查找的值只可能存在于当前节点的右子树，如果当前节点的值小于要查找的值，说明要查找的值只可能存在于当前节点的左子树。不断重复以上过程，遇见两种情况终止：

*  当前节点是要查找的值，查找成功，说明值存在。
 *  当前的值不是要查找的值，且节点没有左右子树，是叶子节点，查找失败，说明值不存在。

代码示例：

public static boolean find(int target){
            //从根节点开始
            flag=root;
            while(true){
                //当前节点值为查找值
                if(flag.getData()==target){
                    return true;
                }
                //向右子树查找
                if(target>flag.getData()){
                    flag=flag.getRight();
                }
                //向左子树查找
                if(target<flag.getData()){
                    flag=flag.getLeft();
                }
                //当前节点是叶节点
                if(flag==null){
                    return false;
                }
            }
        }

#### 2.查找最大值 ####

从根节点开始一直沿着右子树的右孩子进行查找，右子树的最后一个右孩子一定是最大值。

public static int findMax(){
            flag=root;
            while(flag.getRight()!=null){
                flag=flag.getRight();
            }
            return flag.getData();
        }

#### 3.查找最小值 ####

从根节点开始一直沿着左子树的左孩子进行查找，左子树的最后一个左孩子一定是最小值。

public static int findMin() {
            flag = root;
            while (flag.getLeft() != null) {
                flag = flag.getLeft();
            }
            return flag.getData();
        }

#### 5.2.4.删除 ####

被删除的节点有三种情况：

*  叶子节点，直接删除即可。
 *  只有一个孩子，用孩子节点接替被删除节点即可。
 *  左右孩子双全，用左子树中最大值接替被删除节点，用右子树中最小值接替被删除节点。

代码示例：

二叉搜索树由于是整体有序的，每个元素的变动都会造成一定范围内需要进行整体的重新排序，且排序过程是重复的，因此这个过程用递归实现更加简洁，用循环会很冗长，此处选用递归实现。

public static void delete(int target){
            flag=root;
            //由于删除节点会引起树的调整，为了以防万一根节点需要重新指向一下
            root=doDelete(flag,target);
        }
    
        private static Node doDelete(Node node,int target){
            //空树直接返回，或者是递归出口1：已经遍历完整棵树
            if(node == null) {
                return null;
            }
            //递归左子树
            if(target < node.getData()) {
                node.setLeft(doDelete(node.getLeft(), target));
            }
            //递归右子树
            if(target > node.getData()) {
                node.setRight(doDelete(node.getRight(), target));
            }
            //执行到此步，说明已经出递归，并且没有走递归出口1返回，说明找到了目标
            //情况1：被删除节点只有一个孩子节点
            //情况2：被删除节点为叶子节点
            //以上两种情况可以合并成一个逻辑处理，即指向自己的孩子节点即可
            if(node.getLeft() == null) {
                return node.getRight();
            }
            if(node.getRight() == null) {
                return node.getLeft();
            }
            //情况3：被删除节点左右孩子双全，找右子树中最小值接替被删除节点，右子树需递归此过程整体做调整
            Node minNode = findMinNode(node.getRight());
            node.setData(minNode.getData());
            node.setRight(doDelete(node.getRight(),minNode.getData()));
            return node;
        }
    
        private static Node findMinNode(Node node){
            while(node.getLeft() != null)
                node = node.getLeft();
            return node;
        }

[1d309c2f1a0041f3be255215038bdc0c.png]: https://img-blog.csdnimg.cn/1d309c2f1a0041f3be255215038bdc0c.png