平时写业务代码的时候很少写对应的算法，因为很少会在内存中存储大量数据，在需要比较大量数据的查找时，多会依赖的中间件，而中间件底层就应用了很多不同算法，尤其是树结构的查找存储算法，二分查找算法在树里面有大量应用。
二分查找算法
也称折半查找（Binary Search），它是一种效率较高的查找方法，时间复杂度O（log2n），要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列 ，在数据量大的情况，比线性查找性能高；在数据量少的情况和线性查找差不多
线性查找和二分查找效果对比：https://www.cs.usfca.edu/~galles/visualization/Search.html
线性查找
二分查找
编码实现
public class BinarySearch {
public static void main(String[] args) {
// 定义一个有序数组
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
// 要查找的元素
int target = 7;
// 调用二分查找算法
int index = binarySearch(arr, target);
if (index == -1) {
System.out.println("查找的元素不存在");
} else {
System.out.println("查找的元素下标为：" + index);
}
}
/**
* 二分查找算法
*
* @param arr 有序数组
* @param target 要查找的元素
* @return 返回元素在数组中的下标，如果没有找到返回-1
*/
public static int binarySearch(int[] arr, int target) {
// 记录开始位置
int start = 0;
// 记录结束位置
int end = arr.length - 1;
// 记录中间位置
int mid;
// 循环查找
while (start <= end) {
// 计算中间位置
mid = (start + end) / 2;
// 比较中间位置的值
if (arr[mid] == target) {
// 找到元素，返回下标
return mid;
} else if (arr[mid] < target) {
// 中间元素小于目标元素，则在右边查找
start = mid + 1;
} else {
// 中间元素大于目标元素，则在左边查找
end = mid - 1;
}
}
// 没有找到元素
return -1;
}
}二叉树
什么是树
是一种非线性的数据结构，它具有层次结构，根节点是树的最高层，叶节点是最低层。
树可以分为二叉树、平衡树、红黑树、B树、B+树等。
| 常见术语 | |
| 根节点 | 在非空树中没有前驱结点的结点，被称为根节点（注意，只有一个根节点） |
| 父节点 | 每个节点除了根节点外，都有一个父节点 |
| 子节点 | 每个节点都可以有1个或多个子节点 |
| 叶节点 | 没有子节点的节点称为叶节点 |
| 节点的度 | 结点所拥有子树个数，叶子结点就是度为0的结点 |
| 树的度 | 树里的各个节点度的最大值 |
| 层数 | 根节点为第一层，往下一次递增。 |
| 高度（深度） | 结点的深度指从根节点自顶向下逐层累加至该结点时的深度，树的深度是树中深度最大的结点的深度。 |
| 路径 | 从一个节点到另一个节点的序列称为路径 |
| 森林 | 由一组树组成的集合称为森林 |
什么是二叉树？
树有很多种，但是每一个结点最多只有两个子节点的树，被称作为二叉树。二叉树的子节点又分成左节点与右节点。二叉树遍历过程中，每个结点都被访问了一次，时间复杂度是 O(n)
在树的大家族中，二叉树是特别高频使用的树，利用二叉树特性，变种延伸特别多，完全二叉树、满二叉树、二叉查找树（二叉排序树）、平衡二叉树(AVL树)、B-Tree、B+Tree、红黑树（自平衡的二叉查找树，JDK 1.8后的HashMap的存储结构） ...
二叉树的遍历
二叉树分成根节点、左子树和右子树， 根据根节点什么时候被访问，把二叉树遍历分成三种方式。
前序遍历：首先访问根节点，然后先是访问左子树，最后才到右子树
以上图为例，顺序为：A B D H E I J C F G
中序遍历：首先访问左子树，然后到根节点，最后才到右子树
以上图为例，顺序为：D H B I E J A F C G
后序遍历：首先访问左子树，然后到右子树，最后才到根节点
以上图为例，顺序为：H D I J E B F G C A
二叉树拓展
满二叉树
每个节点都有0个或者2个子节点的二叉树，叶节点都在最底层的二叉树，节点的总数=2^n-1（n为层数）外观看上去是完整的一个三角形。如节点总数=2^4-1=15
完全二叉树
只有最下面两层节点的度可以小于2，并且最下层的叶节点集中在靠左连续的边界，只允许最后一层有空缺结点且空缺在右边，完全二叉树需保证最后一个节点之前的节点都齐全；对任一结点，如果其右子树的深度为j，则其左子树的深度必为j或j+1；如果把G节点删除的话，它就不属于完全二叉树了，因为它的叶子结点已经是不连续了。
两者区别
满二叉树的叶节点都在最底层；完全二叉树只有最下面两层节点的度可以小于2，且最下层的叶节点集中在靠左的边界。
编码分析
树的遍历分为：
1、深度优先遍历：对每一个可能的分支路径深入到不能再深入为止，且每个节点只访问一次，访问完一颗子树再去访问后面的子树；
1）前序遍历：首先访问根节点，然后先是访问左子树，最后才到右子树；
2）中序遍历：首先访问左子树，然后到根节点，最后才到右子树；
3）后序遍历：首先访问左子树，然后到右子树，最后到根节点；
2、广度优先遍历：从根节点到叶子节点的层次关系，一层层横向遍历各个节点，访问树结构的第 n+1 层前必须先访问完第 n 层
编码
深度优先遍历 实现二叉树的插入、前序、中序、后序查找。树的定义本身是递归定义，因此采用递归的方法去实现树的三种遍历，容易理解而且代码很简洁
public class BinaryTree {
// 根节点
TreeNode root;
public void insertNode(int data) {
root = insert(root, data);
}
private TreeNode insert(TreeNode treeNode, int data) {
//如果是空则插入第一个节点
if (treeNode == null) {
return new TreeNode(data);
}
//插左边
if (data < treeNode.data) {
treeNode.leftChild = insert(treeNode.leftChild, data);
}
//插右边
else if (data > treeNode.data) {
treeNode.rightChild = insert(treeNode.rightChild, data);
} else {
treeNode.data = data;
}
return treeNode;
}
// 前序遍历
public void preOrder(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.data + " ");
preOrder(root.leftChild);
preOrder(root.rightChild);
}
// 中序遍历
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.leftChild);
System.out.print(root.data + " ");
inOrder(root.rightChild);
}
// 后序遍历
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.leftChild);
postOrder(root.rightChild);
System.out.print(root.data + " ");
}
}
class TreeNode {
int data;
//左节点
TreeNode leftChild;
//右节点
TreeNode rightChild;
TreeNode(int data) {
this.data = data;
}
}测试
public static void testBinaryTree(){
BinaryTree btt=new BinaryTree();
btt.insertNode(93);
btt.insertNode(33);
btt.insertNode(51);
btt.insertNode(21);
btt.insertNode(102);
btt.insertNode(42);
btt.preOrder(btt.root);
System.out.println();
btt.inOrder(btt.root);
System.out.println();
btt.postOrder(btt.root);
}输出结果
前序：93 33 21 51 42 102
中序：21 33 42 51 93 102
后序：21 42 51 33 102 93 
