1. 二叉搜索树的概念

二叉搜索树又称为二叉排序树，它的特点为左子树往后的所有结点都比根节点小，右子树往后的所有结点都比根节点大。根据下图来理解：

编辑

通过上图我们可以观察到，以20为根节点时左侧的所有节点都比20要小，右侧的所有节点都要比20要大。当以20的左子树18、右子树31作为根节点时也是左边节点比根节点小，右边节点比根节点大。

那么以这种结构组成的二叉树，我们就叫做二叉搜索树。因此我们能得出这些性质：

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
• 它的左右子树也分别为二叉搜索树

首先我们要知道，一个节点是由左子树，值，右子树组成，通常左子树用 left 表示，值用 val 表示，右子树用right表示。把三个部分综合起来这样就形成了一个节点，树的根节点用 root 表示因此我们可以定义一个静态内部类 TreeNode 来搭建这个节点：

//节点结构
    static class TreeNode {
        public TreeNode left;//左子树
        public TreeNode right;//右子树
        public int val;//值
        public TreeNode(int val) {
            this.val = val;//构造方法为成员变量赋值
        }
    }
    public TreeNode root;//根节点

这样节点的搭建就完成了，我们可以看到这个节点内包含的 left、val、right 这三个代表量。 下面，我们就来讲解二叉搜索树的操作：查找节点、插入节点、删除节点。

2. 二叉搜索树的操作

2.1 查找节点

查找二叉树的节点，我们根据二叉搜索树的性质下可以列出以下几个条件，

1. 若根节点不为空
2. 根节点等于要查找的节点，返回根节点
3. 根节点大于要查找的节点，在根节点的左子树查找
4. 根节点小于要查找的节点，在根节点的右子树查找
5. 否则，返回null

(1).根节点为空

根节点为空代表这个树是不存在的，因此我们直接返回null即可：

if(root == null) {
        return null;
    }

(2).根节点等于要查找的节点

根节点等于要查找的节点我们直接返回根节点即可，这种情况相当于一下子就找到了。因此它的时间复杂度为O(1)。

编辑

因此，我们可以写出这样的代码：

if(root.val == key) {
        return root;
    }

root.val 是 root 节点值，key 是我们要查找的数据。注意，我们写代码是一步一步来写的，能实现当前的模块，就写当前的代码。最后综合起来并进行修改这样就能写出一段完整的代码。

(3).根节点大于要查找的节点，在根节点的左子树查找

根节点大于要查找的节点，为了满足二叉搜索树的左子树小于根节点的性质，我们要在根节点的左子树进行查找。

编辑

因此，我们可以写出以下代码：

if(root.val > key) {
        root = root.left;
    }

如果root.val大于我们要查找的值key，使根节点变为root的left节点。

(4).根节点小于要查找的节点

根节点小于要查找的节点，为了满足二叉搜索树的右子树大于根节点的性质，在根节点的右子树查找。

编辑

因此，我们可以写出以下代码:

if(root.val < key) {
        root = root.right;
    }

把以上所有的代码综合起来，这样我们就能写出查找结点的方法。我把查找的结点的方法名命为 findNode，方法内的代码根据上方代码进行修改而成。

方法内的流程为：1.判断节点是否为空，为空则返回null。2.在根节点不为空的情况下，判断要查找的节点是否为根节点是则返回根节点，否则判断该节点在根节点的左子树还是右子树，是左子树就把根节点置为左子树，是右子树就把根节点置为右子树。3.没有该节点，返回null。

public class BinarySearchTree {
    //节点结构
    static class TreeNode {
        public TreeNode left;//左子树
        public TreeNode right;//右子树
        public int val;//值
        public TreeNode(int val) {
            this.val = val;//构造方法获取val的值
        }
    }
    //根节点
    public TreeNode root;
    //查找节点
    public TreeNode findNode(int key) {
        TreeNode node = root; //使node为根节点的一个代替
        if (node == null) { //根节点不为空
            return null;
        }
        while (node != null) { //根节点不为空
            if (node.val == key) { 
                return node;//找到根节点就返回node
            }else if (node.val > key) {
                node = node.left;//根节点的值大于查找的值
            }else {
                node = node.right;//根节点的值小于查找的值
            }
        }
        return null;//没有该节点返回null
    }
}

注意，我们直接使用根节点 root 进行操作的话会改变 root 的位置，这样在其他方法使用 root 结点时不能从最初的根节点(最顶层的根据)进行操作，因此我们可以创建一个代替根节点的代替值 node来进行操作，这样无论如何 root 始终是在最初的根节点。