二分搜索树的原理与Java源码实现

了解二叉查找树之前，先来看看折半查找法,也叫二分查找法在一个有序的整数数组中（假如是从小到大排序的），如果查找某个元素，返回元素的索引。
如下：
思想很简单:1先找到数组中间元素target与6比较2如果target比6大，就在数组的左边查找3如果target比6小，就在数组的右边查找
java实现代码如下：

文章图片
测试代码如下：

文章图片
输出折半查找的关键是数组必须有序，一次过滤掉一半的数据，时间复杂度为O（logN）。上面是以2为底的， N为数组的元素个数.
折半查找和下面的要讲的二分搜索树是有一样的思想
2二分搜索树定义二分搜索树定义双叫二分查找树，其定义如下1若它的左子树不为空，则左子树上所有的节点的值均小于根结点的值2若它的右子树不为空，则右子树上所有的节点的值均大于根结点的值3它的左右子树也分别为二分搜索树
由二叉搜索树的定义可知，它前提是二叉树，并且采用了递归的定义方式。再得，它的节点满足一定的关系，左子树的节点一定比父节点的小，右子树的节点一定比父节点的大。
构造一棵二叉搜索树的目的，其实目的不是为了排序，是为了提高查找，删除，插入关键字的速度。
下面我们用图和代码来解释二叉树的查找，插入，和删除。比如下图就是一个二叉搜索树
文章图片
2.0二叉搜索树的定义和节点的定义
二叉搜索树中存放的都是key 。先看下二叉树的定义

文章图片
二叉树中节点的定义
文章图片

文章图片
类的定义和类中节点的定义都有了。二分搜索树的定义如下：
文章图片

文章图片
2.1二叉搜索树的插入
1如果这棵树为空，新建一个节点，作为根2如果要插入的key比根节点大，就插入到右子树中3如果要插入的key比根节点小，就插入到左子树中4如果要插入的key和根节点相等，就更新当前节点的value代码如下：

文章图片

文章图片
2.2二叉搜索树的查找
和上面向一棵二叉搜索树插入一个节点一样。向一棵二叉搜索树中查找一个节点也是类似1如果根节点为空，不用查找了，返回null2如果key比根节点的key要大，在右子树中查找3如果key比根节点的key要小，在左子树中查找4如果key和根节点的key相等，返回根节点
代码实现如下：

文章图片
2.3二叉搜索树的遍历
根据根节点的访问顺序，可以把遍历分为前序遍历，中序遍历，后序遍历前序遍历：先访问根节点，再前序遍历左右子树中序遍历：先中序遍历左子树，再访问根节点，后中序遍历右子树后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点二叉树的遍历有前序遍历，中序遍历，后序遍历，层序遍历（也叫做广度优先遍历）如下图的二叉搜索树。