一、什么是二叉搜索树

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

来源：百度百科_二叉搜索树

二、二叉搜索树的性质

二叉搜索树本质也是一棵二叉树
每个根节点的值大于其左子树所有节点的值
每个根节点的值小于其右子树所有节点的值
每一课子树都是一棵二叉搜索树
存储的元素必须具有可比较性

三、二叉搜索树的构造

1. 构造基本的二叉搜索树

/**
 * @author Dream_飞翔
 * @date 2022/1/17
 * @time 20:16
 * @email 1072876976@qq.com
 */
public class BST<E extends Comparable<E>> {
    // 声明二分搜索树的节点类
    private class Node {
        // 存放节点值的变量
        public E e;
        // 指向左子树和右子树的变量
        public Node left, right;
        public Node (E e) {
            this.e = e;
            // 将左子树和右子树初始化为空
            left = null;
            right = null;
        }
    }
    // 二分搜索树的根节点
    private Node root;
    // 当前二分搜索树存储的元素的个数
    private int size;
    public BST() {
        // 初始化时二分搜索树根节点为空
        root = null;
        // 存储了0个元素
        size = 0;
    }
    // 获取当前二分搜索树存储元素个数的方法
    public int size() {
        return size;
    }
    // 判断当前二分搜索树是否为空
    public boolean isEmpty() {
        return size == 0;
    }
}

在这里继承Comparable的原因是在二叉搜索树中每一个元素都应该是可进行比较的，因此继承了Comparable接口。

2. 向二叉搜索树中添加元素

本文中向二叉搜索树中添加元素时默认没有重复元素的情况，如果要包括有重复元素的情况只需要更改规则为左子树的每一个节点值小于等于根节点的值，右子树的每一个节点的值大于等于根节点的值即可，之后我会专门写一篇文章来实现这样的情况。在本文中向二叉搜索

树中插入新的元素的方式主要使用递归的方式。

在BST.java文件中添加如下方法：

    // 向二分搜索树中添加新的元素e
    public void add (E e) {
        // 首先进行判断当前二分搜索树是否为空
        if (root == null) {
            // 创建一个新的根节点
            root = new Node(e);
            // 元素个数加 1
            size++;
        }
        // 如果二分搜索树不为空，则将当前元素添加到节点中
        add(root,e);
    }
    // 向以node为根的二分搜索树中插入元素e
    private void add (Node node, E e) {
        // 如果当前插入的元素和节点的元素值相同，说明当前元素已经插入到了节点中
        if (e.equals(node.e)) {
            return;
        // 如果当前元素小于根节点的值并且根节点的左子树为空
        } else if (e.compareTo(node.e) < 0 && node.left == null) {
            node.left = new Node(e);
            size++;
            return;
        // 如果当前元素大于根节点的值并且根节点的右子树为空
        } else if (e.compareTo(node.e) > 0 && node.right == null) {
            node.right = new Node(e);
            size++;
            return;
        }
        if (e.compareTo(node.e) < 0) {
            // 递归调用本身，在左子树中插入当前元素
            add(node.left, e);
        } else {
            // 递归调用在右子树中插入当前元素
            add(node.right, e);
        }
    }

在这里递归的终止条件分为三种情况：

第一种情况为当前插入元素的值与二叉搜索树中的某一个节点的值相同，此时认为当前元素已经存在与二叉搜索树中。
此时遍历到叶子节点并且当前元素的值小于此时叶子节点的值，将当前元素作为新的叶子节点（左子树）后返回
此时遍历到叶子节点并且当前元素的值大于此时叶子节点的值，将当前元素作为新的叶子节点（右子树）后返回

3. 改进插入元素的方法

在上面所写的代码中，if判断语句过于多，代码显得很冗长并且可读性差，因此可以改变一种思路向二叉搜索树中添加元素

在刚才的代码中遍历到叶子节点时只是进行了对当前节点是否存在子节点的判断，实际上并未递归到底，因此可以将递归的终止条件修改为如果当前正在遍历的节点为空时，将要插入的元素作为参数构造出一个新的节点并将新的节点返回，将此时add方法的返回值由void更改为Node类型。此时在插入元素后，当前二叉搜索树的左子树或右子树就发生了改变，因此在递归调用add方法时要将返回的更改后的左右子树的值分别赋值给原本的左右子树。在对外展现的add方法中调用时也可以省略当前根节点是否为空的判断，因

为本身要返回的就是一个新的节点。

因此新的插入元素的方法可以修改为：

  // 向二分搜索树中添加新的元素e
    public void add (E e) {
        // 如果二分搜索树不为空，则将当前元素添加到节点中
        root = add(root,e);
    }
  // 返回插入新节点后二分搜索树的根
  private Node add (Node node, E e) {
    if (node == null) {
      size++;
            return new Node(e);
        }
        if (e.compareTo(node.e) < 0) {
      // 递归调用本身，在左子树中插入当前元素
            node.left = add(node.left, e);
    } else if (e.compareTo(node.e) > 0){
      // 递归调用在右子树中插入当前元素
      node.right = add(node.right, e);
    }
      // 将改变后的二分搜索树进行返回
    return node;
  }

在这里并没有对要进行插入的元素值与节点值相等的情况进行处理，因此在递归调用本身进行右子树的插入时要使用else if来进行判断。

四、二叉搜索树的查询

对于二分搜索树的查询操作来说，只需要对二叉搜索树的每一个节点中存储的元素进行查看即可。在查询时也创建一个私有的contains方法进行递归操作，传入参数为当前要进行遍历的二叉搜索树和要查询的元素。

首先先对当前传来的二叉搜索树进行是否为空的判断，如果为空则直接返回false，接着将元素的值与节点中的值进行比较，如果比较结果等于0则说明当前二叉搜索树中存在当前元素，如果小于0则继续调用contains方法对左子树进行遍历查询，如果大于0则继续对右子树进行遍历查询。

    // 查看当前的二分搜索树中是否存在元素e
    public boolean contains (E e) {
        return contains(root, e);
    }
    // 查询以node为根的二分搜索树中是否存在元素e
    private boolean contains(Node node, E e) {
        if (node == null) {
            return false;
        }
        // 将元素e与节点中的值进行比较
        if (e.compareTo(node.e) < 0) {
            return contains(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            return contains(node.right, e);
        } else {
            return true;
        }
    }

五、测试

接下来就创建测试类Main.java对下图的二叉搜索树进行构造并进行遍历

1. 测试类代码

/**
 * @author Dream_飞翔
 * @date 2022/1/17
 * @time 22:08
 * @email 1072876976@qq.com
 */
public class Main {
    public static void main(String[] args) {
        // 创建一棵二分搜索树
        BST<Integer> bstTree = new BST<>();
        // 首先对二分搜索树是否为空进行判断
        System.out.println("当前二分搜索树是否为空：" + bstTree.isEmpty());
        // 查看当前二分搜索树中的元素个数
        System.out.println("二分搜索树中的元素个数为：" + bstTree.size());
        // 向二分搜索树中插入根节点
        bstTree.add(33);
        bstTree.add(28);
        bstTree.add(40);
        bstTree.add(19);
        bstTree.add(31);
        bstTree.add(35);
        bstTree.add(45);
        // 判断当前二分搜索树是否为空
        System.out.println("当前二分搜索树是否为空：" + bstTree.isEmpty());
        // 查看当前二分搜索树中的元素个数
        System.out.println("二分搜索树中的元素个数为：" + bstTree.size());
        System.out.println("------------------- 接下来查看二分搜索树中包含的元素 -------------------");
        System.out.println("二分搜索树中是否包含元素33：" + bstTree.contains(33));
        System.out.println("二分搜索树中是否包含元素28：" + bstTree.contains(28));
        System.out.println("二分搜索树中是否包含元素40：" + bstTree.contains(40));
        System.out.println("二分搜索树中是否包含元素19：" + bstTree.contains(19));
        System.out.println("二分搜索树中是否包含元素31：" + bstTree.contains(31));
        System.out.println("二分搜索树中是否包含元素35：" + bstTree.contains(35));
        System.out.println("二分搜索树中是否包含元素45：" + bstTree.contains(45));
        System.out.println("二分搜索树中是否包含元素100：" + bstTree.contains(100));
    }
}

2. 运行结果

六、源码（改进后）

/**
 * @author Dream_飞翔
 * @date 2022/1/17
 * @time 20:16
 * @email 1072876976@qq.com
 */
public class BST<E extends Comparable<E>> {
    // 声明二分搜索树的节点类
    private class Node {
        // 存放节点值的变量
        public E e;
        // 指向左子树和右子树的变量
        public Node left, right;
        public Node (E e) {
            this.e = e;
            // 将左子树和右子树初始化为空
            left = null;
            right = null;
        }
    }
    // 二分搜索树的根节点
    private Node root;
    // 当前二分搜索树存储的元素的个数
    private int size;
    public BST() {
        // 初始化时二分搜索树根节点为空
        root = null;
        // 存储了0个元素
        size = 0;
    }
    // 获取当前二分搜索树存储元素个数的方法
    public int size() {
        return size;
    }
    // 判断当前二分搜索树是否为空
    public boolean isEmpty() {
        return size == 0;
    }
    // 向二分搜索树中添加新的元素e
    public void add (E e) {
        // 如果二分搜索树不为空，则将当前元素添加到节点中
        root = add(root,e);
    }
    // 向以node为根的二分搜索树中插入元素e
    // 返回插入新节点后二分搜索树的根
    private Node add (Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        }
        if (e.compareTo(node.e) < 0) {
            // 递归调用本身，在左子树中插入当前元素
            node.left = add(node.left, e);
        } else if (e.compareTo(node.e) > 0){
            // 递归调用在右子树中插入当前元素
            node.right = add(node.right, e);
        }
        // 将改变后的二分搜索树进行返回
        return node;
    }
    // 查看当前的二分搜索树中是否存在元素e
    public boolean contains (E e) {
        return contains(root, e);
    }
    // 查询以node为根的二分搜索树中是否存在元素e
    private boolean contains(Node node, E e) {
        if (node == null) {
            return false;
        }
        // 将元素e与节点中的值进行比较
        if (e.compareTo(node.e) < 0) {
            return contains(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            return contains(node.right, e);
        } else {
            return true;
        }
    }
}

七、总结

以上便是二叉搜索树的构造以及简单查询的递归实现，在本文中的二叉搜索树没有对当插入元素的值与树中某一节点的值相同的情况，在进行完二叉搜索树的先序、中序、后序以及层序遍历后会对插入元素的值与某一节点值相同的情况进行实现。

二叉搜索树的构造（Java实现）