数据结构——二叉搜索树

• • 引言
  • 说明
  • 代码实现增查删
  • • 创建一个 java 文件，里面放着两个类
    • 创建另一个 java 文件，里面放着一个类 Test，用来测试
  • 代码分析

二叉搜索树又称为（二叉排序树、二叉查找树），什么是二叉搜索树？

它是一棵空树，或者具有下列性质的二叉树
① 它的左子树不为空，则左子树上所有的节点的值均小于它的根节点的值。
② 它的右子树不为空，则右子树上所有的节点的值均大于它的根节点的值。
③ 它的左、右子树也分别为二叉搜索树。

二叉搜索树的中序遍历的数据是一个已排序好的数据。然而，构造一棵二叉搜索树的目的，不是为了排序，而是为了提高查找、添加、删除数据的速度。

本篇博客实现的二叉搜索树的形状如下，也即是对下面这棵树进行操作。

一个是 Node 类，表示某个节点的当前状态
另一个是 SearchTree，表示二叉树的当前状态

class Node{
    public int val;
    public Node left;
    public Node right;

    public Node(int val){
        this.val = val;
    }
}
public class SearchTree {

    public Node root = null;
    public static void main(String[] args) {
        SearchTree searchTree = new SearchTree();
        int[] arr = {10,6,14,4,8,12,17,3,5,7,9,11,13,15,18,16};
        for (int i = 0; i < arr.length; i++) {
            searchTree.insert(arr[i]);
        }
        searchTree.inorder(searchTree.root);
        System.out.println();

        searchTree.remove(6);
        searchTree.inorder(searchTree.root);
    }

    
    public Node search(int key){
        Node cur = root;

        while(cur != null){
            if(key < cur.val){
                cur = cur.left;
            }else if(key > cur.val){
                cur = cur.right;
            }else {
                return cur;
            }
        }
        return null;
    }

    
    public boolean insert(int data){
        if(root == null){
            root = new Node(data);
            return true;
        }

        Node cur = root;
        Node parent = null;
        //比较 parent、cur 与 data，
        //来判断 data 是插入在 parent 节点的左边，还是节点的右边
        while(cur != null){
            if(data < cur.val){
                parent = cur;
                cur = cur.left;
            }else if(data > cur.val){
                parent = cur;
                cur = cur.right;
            }else {
                return false;
            }
        }

        if(data < parent.val){
            parent.left = new Node(data);
            return true;
        }else {
            parent.right = new Node(data);
            return true;
        }
    }

    
    public boolean remove(int key){
        Node cur = root;
        Node parent = null;

        while (cur != null){
            if (key == cur.val){
                removeNode(cur,parent);
                return true;
            }else if(key < cur.val){
                parent = cur;
                cur = cur.left;
            }else {
                parent = cur;
                cur = cur.right;
            }
        }
        return false;
    }

    public void removeNode(Node cur, Node parent){
        if (cur.left == null){
            if(cur == root){
                root = cur.right;
            }else if(cur == parent.left){
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        }else if(cur.right == null){
            if(cur == root){
                root = cur.left;
            } else if (cur == parent.left) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {

            //1. 在 cur 的左树中，找最大值
            //2. 在 cur 的右树中，找最小值

            Node flagParent = cur;
            Node flag = cur.right;
            while (flag.left != null){
                flagParent = flag;
                flag = flag.left;
            }
            cur.val = flag.val;
            if(flag == flagParent.left){
                flagParent.left = flag.right;
            }else {
                flagParent.right = flag.right;
            }
        }
    }

    
    public void inorder(Node root){
        if(root == null) return;

        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }   
}

public class Test {
    public static void main(String[] args) {
        SearchTree searchTree = new SearchTree();
        int[] arr = {10,6,14,4,8,12,17,3,5,7,9,11,13,15,18,16};
        for (int x:arr) {
            searchTree.insertData(x);//往树中添加数据
        }
        System.out.println("------------ 中序遍历 ------------");
        searchTree.inorder(searchTree.root);
        System.out.println();
        System.out.println("------------ 查找 key ------------");
        System.out.println(searchTree.search(0));
        System.out.println("------------ 删除 key ------------");
        searchTree.remove(14);
        searchTree.inorder(searchTree.root);
        System.out.println();
        searchTree.remove(5);
        searchTree.inorder(searchTree.root);
        System.out.println();
        searchTree.remove(16);
        searchTree.inorder(searchTree.root);
        System.out.println();
    }
}

输出结果：

在二叉搜索树中添加数据或查找数据，都较为简单，这都需要按照二叉搜索树的性质来进行操作，二叉搜索树的左子树比双亲节点小，右子树的比双亲节点大，这一独特的性质，使得增查操作效率较高。

而相对来说，删去元素的代码实现并不简单，考虑的情况有很多种。

1. 删除的节点为叶子节点
2. 删除节点的左子树为空
   分三种情况，考虑删除的节点与其双亲节点的位置
3. 删除节点的右子树为空
   分三种情况，考虑删除的节点与其双亲节点的位置
4. 删除节点的左右子树都不为空
   方法① 找此节点左子树的最大值，进行交换当前节点
   方法② 找此节点右子树的最小值，进行交换当前节点