【Java 数据结构】实现一个二叉搜索树

1、认识二叉搜索树
从字面上来看，它只比二叉树多了搜索两个字，我们回想一下，如果要是在二叉树中查找一个元素的话，需要遍历这棵树，效率很慢，而二叉搜索树，则会效率高很多，为什么呢？

二叉搜索树，可以是一棵空树，或者是具有以下的性质：

若它的左子树不为空，则左树上所有的节点都小于根节点
若它的右子树不为空，则右树上所有节点的都大于根节点
它的左子树和右子树也分别为二叉搜索树
通俗来讲，左孩子都小于父节点，右孩子都大于父节点，以此类推，这里我们画图来认识下二叉搜索树：

当然二叉搜索树不要求是完全二叉树或满二叉树，甚至会出现单分支的二叉搜索树，所以针对这种特殊的情况进行了优化也就延申而来的 AVL树，这个是后续的话题。

仔细观察上图，可以观察出二叉搜索树的一个新特性：

中序遍历二叉搜索树是有序的，所以二叉搜索树也被称为二叉排序树。

2、实现一个二叉搜索树
2.1 成员变量

    private TreeNode root; //存放根节点
 
    private static class TreeNode {
        private int val;
        private TreeNode left;
        private TreeNode right;
        private TreeNode(int val) {
            this.val = val;
        }
    }
}