二叉树BinaryTree是每个节点最多只有两个节点的树形结构，两个节点分别称为左子树和右子树。
为什么要使用树结构？
通过另外一篇文章Hash哈希表 散列表我们可以看到数组和链表这两种数据结构的优点和缺点，为了提高读取、操作的效率，除了使用Hash表外，我们还可以选择树结构，比如利用二叉树既可以保证读取检索速度同时也能保证插入、删除、修改的速度。
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
为什么要使用哈希表？首先我们来看下数组和链表的特点：
那我们能不能综合这两者的优点，创建一个查询（寻址）容易同时操作（插入、删除）也容易的数据结构？
答案就是哈希表，它能兼顾数组和链表的优点。
哈希表存储数据的结构图：
该图左边是一个数组，每个数组存储内容指向一个链表。
散列函数，能将一个元素根据该函数转换为哈希表的数组下表。
散列函数的常见实现方式：
index = key % p在上边文章总结了常见的排序算法，本文接着上篇内容来介绍总结常见的查找算法。
BinarySearch遍历待查找的数列，逐个比较，直到匹配项介绍。
public static int seqSearch(int[] array, int findVal) {
int length = array.length;
for(int i = 0; i < length; i ++) {
if(findVal == array[i]) {
return i;
}
}
return -1;
}Binary Search二分查找也称折半查找，搜索的特点是：每经历一次比较，都是搜索范围缩小一半。
查找思路：
中值公式：
排序，给定一组数，按照指定顺序进行排列的过程。
排序算法有很多，一般可以分为二类：
内部排序，即使用内存
各个算法时间复杂度比较：
术语说明：
a原来就在b前面，而a = b，完成排序后a仍在b的前面。a原来就在b前面，而a = b，完成排序后a可能在b的后面。冒泡排序思想：
通过对待排序序列从前向后，依次比较相邻的元素，逆序则交换，使得值较大的元素逐渐从前移到后部，类似冒泡从底部逐渐冒上来（排好序）。
冒泡排序代码如下：
/**
* 冒泡排序
* <pre>
* 重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序逆序(即排序标准)就把他们交换过来。
* 走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
* </pre>
* @author jyoryo
*/
public class BubbleSort {
public static void main(String[] args) {
int size = 100000;
int array[] = new int[size];
for(int i = 0; i < size; i++) {
array[i] = (int)(Math.random() * size * 1000);
}
// System.out.println(Arrays.toString(array));
long current = System.nanoTime();
// bubbleSort(array);
bubbleSort2(array);
System.out.println(System.nanoTime() - current);
// System.out.println(Arrays.toString(array));
}
// 冒泡排序
public static void bubbleSort(int[] array) {
int length = array.length;
for(int i = 0; i < length; i ++) {
for(int j = 0; j < (length - i - 1); j ++) {
if(array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
}
// 冒泡排序（优化过）
public static void bubbleSort2(int [] array) {
int length = array.length;
boolean flag = false; //标志是否经过交换
for(int i = 0; i < length; i++) {
for(int j = 0; j < (length - i - 1); j++) {
if(array[j] > array[j + 1]) {
flag = true;
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
// 在一趟排序中未发生交换
if(!flag) {
break ;
}
// 重置标志
flag = false;
}
}
}递归，简单地说就是方法自己调用自己，每次调用时传入不同的变量。
使用递归，可以有助于我们解决复杂问题，同时可以使代码保持简洁。
递归解决问题：
使用递归注意事项：
StackOverflowError异常，退出程序；return，就会返回发起调用它的方法，谁调用，就将返回结果返回给谁。该问题是一个小球从迷宫的起点出发，怎么走才能到达终点。
实现代码：
/**
* 小球走迷宫
* <br />
* 一个小球充下面的地图"S"点开始出发，走到"E"到达终点
* S：起点
* E：终点
* <pre>
* 1 1 1 1 1 1 1
* 1 S 0 0 0 0 1
* 1 0 0 0 0 0 1
* 1 1 1 0 0 0 1
* 1 0 0 0 0 0 1
* 1 0 0 0 0 0 1
* 1 0 0 0 0 E 1
* 1 1 1 1 1 1 1
* </pre>
* @author jyoryo
*/
public class Maze {
public static void main(String[] args) {
// 迷宫地图
int [][] map = new int[8][7];
// 上下墙
for(int i = 0; i < 7; i++) {
map[0][i] = 1;
map[7][i] = 1;
}
// 左右墙
for(int i = 0; i < 8; i++) {
map[i][0] = 1;
map[i][6] = 1;
}
// 障碍物
map[3][1] = 1;
map[3][2] = 1;
print(map);
run(map, 1, 1);
System.out.println("~~~完成迷宫~~~");
print(map);
}
/**
* 走法
* 地图上每个点值说明：0:表示该点没有走过； 1:表示墙； 2:表示通路可以走； 3:表示该点走过，但是走不通
* @param map 地图
* @param i 出发点行索引
* @param j 出发点列索引
* @return
*/
public static boolean run(int[][] map, int i, int j) {
// 到终点
if(map[6][5] == 2) {
print(map);
return true;
}
// 该点没有走过，开始走
if(map[i][j] == 0) {
/*
* 走的策略：下→右→上→左
*/
map[i][j] = 2;
// 下走
if(run(map, i + 1, j)) {
return true;
}
// 右走
else if(run(map, i, j + 1)) {
return true;
}
// 上走
else if(run(map, i - 1, j)) {
return true;
}
// 左走
else if(run(map, i, j - 1)){
return true;
}
// 走不通,回溯更改
else {
map[i][j] = 3;
return false;
}
}
return false;
}
// 打印地图
private static void print(int [][] array) {
for(int i = 0; i < array.length; i++) {
for(int j = 0; j < array[i].length; j++) {
System.out.printf("%d\t", array[i][j]);
}
System.out.println();
}
}
}汉诺塔算法的思路：
n-1个盘子由A移到B；n个盘子由A移到C；n-1个盘子由B移到C。实现代码如下：
public class TowerOfHanoi {
private static int counter = 0; // 计数器
public static void main(String[] args) {
char a = 'A', b = 'B', c = 'C';
System.out.println("请输入圆盘数：");
Scanner scanner = new Scanner(System.in);
int number = scanner.nextInt();
hanoi(number, a, b, c);
scanner.close();
}
public static void hanoi(int n, char a, char b, char c) {
if(1 == n) {
move(1, a, c);
return ;
}
// 递归，将A上的编号{n - 1}盘移动到B， C为辅助塔
hanoi(n - 1, a, c, b);
// 将编号为{n}盘移动到C
move(n, a, c);
// 递归，将B上的编号{n - 1}盘移动到C， A为辅助塔
hanoi(n - 1, b, a, c);
}
public static void move(int diskNo, char from, char to) {
System.out.printf("第%d次移动，将%d号盘从%s→%s。\n", ++counter, diskNo, from, to);
}
}public class EightQueensPuzzle {
// 使用一维数组表示，数组索引表示所在行；对应值为该行皇后排放的列
int max = 8;
int [] array = new int[max];
int counter = 0;
public static void main(String[] args) {
EightQueensPuzzle queensPuzzle = new EightQueensPuzzle();
queensPuzzle.queue(0);
System.out.printf("一共由%d种摆法！", queensPuzzle.counter);
}
// 排放第n个皇后
private void queue(int n) {
// 8皇后都已摆放好
if(n == max) {
print();
return ;
}
for(int i = 0; i < max; i++) {
array[n] = i;
// 不冲突
if(valid(n)) {
queue(n + 1);
}
}
}
// 当放置第n个皇后，检测是否与前已排的有冲突(同一行、同一列、同一斜线)
private boolean valid(int n) {
for(int i = 0; i < n; i++) {
// array[i] == array[n] 表示在同一列
// Math.abs(n - 1) == Math.abs(array[n] - array[i]) 表示在同一斜线上
if(array[i] == array[n] || (Math.abs(n - i) == Math.abs(array[n] - array[i]))) {
return false;
}
}
return true;
}
// 打印
private void print() {
counter ++;
for(int i = 0; i < array.length; i++) {
System.out.printf("%d\t", array[i]);
}
System.out.println();
}
}数据结构是算法的基础，一般数据结构可以分为：线性结构、非线性结构。
本文章主要是对于常用的线性数据结构进行总结。
常见的线性数据结构有：
ArrayLinkedListQueueStackSparseArray稀疏数组：如果数组中大部分的元素值都未被使用（或都为0），在数组中仅有少部分的空间使用，因此造成内存空间的浪费，为了解决这问题，并且不影响数组中原有的元素值，采用的一种压缩的方式来表示原数组的内容。
稀疏数组处理方法：
二维数组转稀疏数组
count。count创建稀疏数组sparseArray[count + 1][3]。稀疏数组还原原始二维数组