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 查找节点
查找二叉树的节点，我们根据二叉搜索树的性质下可以列出以下几个条件，
- 若根节点不为空
- 根节点等于要查找的节点，返回根节点
- 根节点大于要查找的节点，在根节点的左子树查找
- 根节点小于要查找的节点，在根节点的右子树查找
- 否则，返回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 始终是在最初的根节点。
