数据结构学习网站：https://www.zhihu.com/question/20368410
http://www.cnblogs.com/skywang12345/p/3603935.html （算法大全）
优秀的数据结构博客 1） http://blog.csdn.net/javazejian/article/details/53375004
2） http://www.cnblogs.com/smyhvae/p/4793339.html（队列与线性表的区别）
《大话数据结构》：读后感
------------数据结构章节---------------
1.数据结构的定义
数据结构是一门研究非数值计算的程序设计中的操作对象，以及它们之间的关系和相关操作等相关问题的学科。
2.数据结构的基本概念和术语
1）数据
2）数据元素：一个数据元素由若干个数据项组成，比如人类的数据元素由人组成
或禽类的数据元素由猪马狗羊组成。
3）数据项：数据项是数据不可分割的最小单位，比如人的五官。
4）数据对象：性质相同（具有相同类型和数据项）的数据元素的集合
5）数据结构：相互之间存在一种或多种特定关系的数据元素的集合
3.数据结构的分类
》逻辑结构
数据对象中数据元素之间的关系
逻辑结构又分为4种：
1）集合结构
2）线性结构
线性结构中数据元素之间是一对一的关系
》物理结构
指数据的逻辑结构在计算机中的存储方式
数组
1）数组之间的复制 ：https://blog.csdn.net/huangbaokang/article/details/75284550
Java-Java中System.arraycopy() 和 Arrays.copyOf()两者之间的区别
https://www.cnblogs.com/yongdaimi/p/5995414.html
https://www.cnblogs.com/ysloong/p/6431127.html （各种实现方法）
4.栈结构
后进先出
push、pop、peek ：限定性的访问方法，使程序易读并且不容易出现错误。
1）栈的概念和实现它的内部数据结构的概念应该完全分开的，栈可以用数组、也可以用链表来实现。
2）
栈操作实用场景：
1）字符串逆序输出
2）分隔符匹配
最后输入的左分隔符需要最先匹配，符合后进先出的特点。
StackX仍然复用上个例子中定义的类
5.队列
循环队列、环绕队列、双端队列、优先级队列、
中缀表达式与后缀表达式
1） java队列相关资料：
https://www.cnblogs.com/samjustin/p/5785078.html
https://www.cnblogs.com/lemon-flm/p/7877898.html
- java队列——queue详细分析 - 低调人生 - 博客园
- java集合--Queue用法 - samjustin - 博客园
2）队列的实际应用环境
情景1：打印发票
下面这段代码的抽象思想：有多个任务要执行，每个任务的数据不同，但是行为相同。可以将各个任务的数据用队列存储，从队列开头取数据执行任务（并将数据从队列里清除），
任务执行完再取下一个数据继续执行任务，以此类推...
注意一点：任务什么时候执行？
我选择在添加完数据之后进行（activateQueue），这样一旦所有的任务执行完毕，再新来一个任务就能立马触发。同时，一个任务执行完毕，也要触发下一个任务。
package com.juli.hf_shangdianke.cz_code.bluetooth.print;
import com.cz.basetool.CodeTool;
import com.cz.basetool.ui_work.util.log.LogController;
import com.cz.basetool.ui_work.util.time.TimeCounter;
import com.cz.blemodule.sdk.core.JuLiBleServerSDK;
import com.juli.hf_shangdianke.cz_code.bluetooth.bridge.PCBleBridger;
import java.util.concurrent.LinkedBlockingQueue;
/**
* Created by XinYi on 2019/3/13.
* BLE 打印机
*/
public class BlePrinter {
private static final String TAG = "BlePrinter";
private static final BlePrinter ourInstance = new BlePrinter();
private OnDataSendResultListener onDataSendResultListener;
private LinkedBlockingQueue<PrintElement> queue = new LinkedBlockingQueue();
private boolean isPrinting = false;
private final TimeCounter timeCounter;
public static BlePrinter getInstance() {
return ourInstance;
}
private BlePrinter() {
isPrinting = false;
timeCounter = new TimeCounter();
}
/**
* 打印发票
* @param cash 收费金额
* @param entryStation 入口
* @param exitStation 出口
* @param carType 车型
*/
public void print(String cash,String entryStation,String exitStation,String carType,OnDataSendResultListener onDataSendResultListener){
add2Queue(new PrintElement(cash, entryStation, exitStation, carType, onDataSendResultListener));
}
/**
* 将打印任务加入队列
* @param printElement
*/
private void add2Queue(PrintElement printElement){
LogController.d(TAG,"加入队列");
queue.offer(printElement);
activateQueue();
}
/**
* 激活队列任务
*/
private void activateQueue(){
if(isPrinting == false){
if(queue.size() > 0){
PrintElement printElement = queue.poll();
realPrint(printElement);
}
}
}
/**
* 调用打印机打印
* @param printElement
*/
private void realPrint(final PrintElement printElement){
isPrinting = true;
String cash = printElement.getCash();
String entryStation = printElement.getEntryStation();
String exitStation = printElement.getExitStation();
final String carType = printElement.getCarType();
LogController.d(TAG,"打印参数(原始)：" + "cash = " + cash + ",entryStation = " + entryStation + ",exitStation = " + exitStation + ",carType = " + carType);
LogController.d(TAG,"打印参数(HEX)：" + "cash = " + CodeTool.StringToHexString(cash) + ",entryStation = " + CodeTool.StringToHexString(entryStation) + ",exitStation = " + CodeTool.StringToHexString(exitStation) + ",carType = " + CodeTool.StringToHexString(carType));
String baowen = "0A0A0A0A0A0A0A0A0A0E202020" + CodeTool.StringToHexString(cash) + "0A140A0A" +
"0A0A0A0A0A0E" + CodeTool.StringToHexString(entryStation) + CodeTool.StringToHexString(exitStation) + "14" +
"0A0A0A0A0A20202020" + CodeTool.StringToHexString(carType) + "20" +
"0A0A200C";
LogController.d(TAG,"打印报文：" + baowen);
output(baowen, printElement.getOnDataSendResultListener());
//超时处理，结束当前有问题的打印任务
timeCounter.setDelayTime(1000);
timeCounter.setTimeCallBack(new TimeCounter.TimeCallBack() {
@Override
public void onTime(int passedCount, long delayMilliSeconds) {
if(passedCount >=5){
timeCounter.stopCount();
printElement.getOnDataSendResultListener().onFailure(new Exception("打印超时"));
isPrinting = false;
activateQueue();
}
}
});
timeCounter.startCount();
}
/**
* 蓝牙透传数据给PC机
* @param data 打印报文
* @param onDataSendResultListener 发送结果
*/
public void output(String data, OnDataSendResultListener onDataSendResultListener){
this.onDataSendResultListener = onDataSendResultListener;
JuLiBleServerSDK.getInstance().getPure33ProtocolSender().send("C1",data);
}
/**
* 标记通讯成功
*/
public void onSendDataSuccess(){
timeCounter.stopCount();
if(onDataSendResultListener != null){
onDataSendResultListener.onSuccess();
}
isPrinting = false;
activateQueue();
}
public interface OnDataSendResultListener{
void onSuccess();
void onFailure(Exception e);
}
} - 定义队列任务抽象类
我发现实际工作经常有类似的需要队列来执行的任务，于是抽象出了一个队列任务类：
package com.cz.basetool.ui_work.util.data;
import java.util.concurrent.LinkedBlockingQueue;
import android.util.Log;
/**
* 抽象队列处理工具类
* 应用场景：适用于从一处读取数据，然后执行数据对应的任务。但是往往任务还没有执行完，又收到了数据，导致任务执行混乱。
* 所以编写此类将读取的数据存入队列，然后依次从队列中取数据执行完任务再取下一个数据执行任务，依次类推。
* T:可以自己封装数据
* @author XinYi
*/
public class AbsQueueTaskHelper<T> {
protected final String TAG = this.getClass().getSimpleName();
private boolean isTaskRunning = false;
private OnTaskActivateListener onTaskActivateListener;
private LinkedBlockingQueue<T> queue = new LinkedBlockingQueue();
private static AbsQueueTaskHelper instance = new AbsQueueTaskHelper();
protected AbsQueueTaskHelper(){
isTaskRunning = false;
}
public static AbsQueueTaskHelper getInstance(){
return instance;
}
public void init(){
isTaskRunning = false;
queue.clear();
}
/**
* 将数据加入队列
* @param item
*/
public void join(T item){
Log.d(TAG,"加入队列");
queue.offer(item);
activateTask();
}
/**
* 取队列数据执行任务
*/
public void next(){
Log.d(TAG,"执行下一个任务");
isTaskRunning = false;
activateTask();
}
/**
* 激活队列任务
*/
private void activateTask(){
if(isTaskRunning == false){
if(queue.size() > 0){
T item = queue.poll();
if(onTaskActivateListener != null){
isTaskRunning = true;
onTaskActivateListener.onTaskActivate(item);
}
}
}
}
/**
* 用于客户端调用自己的业务
* @param onTaskActivateListener
*/
public void setOnTaskActivateListener(
OnTaskActivateListener onTaskActivateListener) {
this.onTaskActivateListener = onTaskActivateListener;
}
public interface OnTaskActivateListener<T> {
void onTaskActivate(T item);
}
} 随便定义一个简单的实现类：
/**
* Created by XinYi on 2019/3/27.
* 测试队列任务抽象类
*/
public class TestAbsQueueTaskHelper extends AbsQueueTaskHelper<String> {
private TestAbsQueueTaskHelper() {
super();
}
} 进行单元测试：
@Test
public void testAbsQueueTaskHelper() {
TestAbsQueueTaskHelper.getInstance().init();
TestAbsQueueTaskHelper.getInstance().setOnTaskActivateListener(new AbsQueueTaskHelper.OnTaskActivateListener() {
@Override
public void onTaskActivate(Object item) {
Log.d("TestAbsQueueTaskHelper", "onTaskActivate: 执行任务---" + item);
MainHandler.getInstance().postDelayed(new Runnable() {
@Override
public void run() {
TestAbsQueueTaskHelper.getInstance().next();
}
},100);
}
});
new Thread(){
@Override
public void run() {
//模拟读取数据，加入队列。
TestAbsQueueTaskHelper.getInstance().join("1111");
TestAbsQueueTaskHelper.getInstance().join("2222");
TestAbsQueueTaskHelper.getInstance().join("3333");
}
}.start();
} 打印结果如下：
可以发现对接起作用了，数据是立马缓存，任务是依次排队执行。只是上面的工具类得注意
TestAbsQueueTaskHelper.getInstance().next(); 这句话的调用时机，特别执行某个任务有异常时，如果想下个任务继续执行，就得调用上面这个方法。
（Java）固定长度队列的实现 - CSDN博客 （当然也可以是固定List）
6.链表
LinkedList、
6-1.ArrayList
1)https://blog.csdn.net/liuzhigang1237/article/details/7197074 (Arrays.asList，不能使用Iterator执行remove方法)
2)ArrayList源码分析
http://www.cnblogs.com/skywang12345/p/3308556.html
2-1）在动态扩充数组容量时用到一个方法Arrays.copyOf()
https://www.cnblogs.com/linbingdong/p/5289812.html
该方法会创建一个新的长度的数组，并且会复制原数组到原有数组里。
2-2）
7.哈希表
https://blog.csdn.net/yyyljw/article/details/80903391 （哈希表的底层是数组，只不过结合了数组和链表的特性）
http://www.cnblogs.com/jijiji/p/4856805.html
https://www.jianshu.com/p/526970086e4e （java中的HashTable类介绍）
1）哈希函数：关键字到内存单元的映射
如何构造哈希函数？
2）哈希冲突的解决：通过哈希函数计算的地址可能会一样
https://blog.csdn.net/qq_41230365/article/details/81058217 （哈希表原理，直观通俗易懂。）
https://www.jianshu.com/p/5a2a5f6de440 （哈希表原理，讲解十分全面。）
- 负载因子：https://blog.csdn.net/zhao_miao/article/details/82684868
负载因子是元素个数与哈希表大小的一个比值，负载因子直接关系到哈希冲突的概率。
8.堆
https://www.jianshu.com/p/6b526aa481b1
http://www.cnblogs.com/JVxie/p/4859889.html
http://www.pianshen.com/article/2534703715/ （带图的）
一种特殊的二叉树，
1）它是一棵完全二叉树
注意二叉树与数组的索引的映射的顺序
2）分为小堆根与大堆根
- 小堆根：小的元素在父结点 （降序排序使用大根堆）
上浮算法： 子结点与父结点交换。当前元素的父结点的数组索引为当前元素索引/2取整，比较大小交换。
下沉算法： 父结点与子结点交换。由于子结点有2个，子结点会先做比较，然后父结点再与更小的子结点做比较。
- 大堆根：大的元素在父结点 （升序排序使用大根堆）
同小堆根算法，只是比较的符号不一样 。
注意大堆根、小堆根结构，映射后的数组并不一定是有序的！
9.数据类型
抽象数据类型：接口实现的
10.枚举
https://www.w3cschool.cn/java/codedemo-484047820.html （获取枚举的名称）
******数据结构在实际开发中的体现与应用******
Java语言本身就设计了一系列的数据结构，如数组、集合,但实际中需要对这些基本的数据结构进行排兵布阵。
实际开发场景1： 稍微复杂的关于checkbox复用的问题.做一个折叠的分组列表，里面有checkbox,有全选和取消全选进行删除的功能。如下图：
为了防止复用的问题，我搞了几个map集合来存储它的状态：
每一个标题（组）有是否展开、checkbox是否可见、是否选中的状态，每一个章节（组内成员）也有checkbox是否可见、是否选中的状态，在标题的长按、点击、checkbox的点击事件以及章节的checkbox的点击事件中，都要对这些状态进行保存和联动刷新以及复用之后的刷新。
最后，差不多一个Adapter类写了531行代码，关于Map的操作遍眼都是，“碎片化”十分的严重，而且数据与view的显示交互在一起，自己真的是看不下去，就重构了一把。下面是我重构的思路：
步骤1）：数据结构的设计
这里的数据结构就是针对状态保存的数据结构了，从内到外设计了2个数据结构，也就是2个类，
章节状态结点和标题状态结点.
章节状态结点：
/**
* author:Created by ZhangChen on 2016/9/20 0020.
* detail:章节结点，保存checkbox的状态 ：是否选中与是否可见
*/
public class ChapterCheckBoxStateNode {
public int positionInGroup ; //在分组中的索引
public View chapterView ;
public boolean isVisible ; //是否可见
public boolean isChecked; //是否选中
public TitleStateNode parentNode ; //父结点 子结点的改变可能要联动父结点的变化
public ChapterCheckBoxStateNode() {
resetState();
}
public ChapterCheckBoxStateNode(int positionInGroup, TitleStateNode parentNode) {
this.positionInGroup = positionInGroup;
this.parentNode = parentNode;
}
public void clear(){ //恢复原始状态
resetState();
}
private void resetState(){
this.isVisible = false;
this.isChecked = false;
}
} 标题状态结点：
/**
* author:Created by ZhangChen on 2016/9/20 0020.
* detail:标题结点，保存标题checkbox的状态 ：是否选中与是否可见
* 保存章节是否折叠的状态
*/
public class TitleStateNode {
public int position; //getView中的position
public View convertView;
public boolean isExpanded ; //是否折叠
public boolean isTitleCheckBoxVisible; //checkbox是否可见
public boolean isTitleCheckBoxChecked; //checkbox是否选中
public boolean isActivated ; //是否处于激活状态，激活（checkbox可见）
public Map<Integer,ChapterCheckBoxStateNode> chapterCheckBoxStateNodes; //章节状态结点
public TitleStateNode() {
resetState();
chapterCheckBoxStateNodes = new HashMap<>();
}
private void resetState(){
isExpanded = false;
isTitleCheckBoxVisible = false;
isTitleCheckBoxChecked = false;
isActivated = false;
}
public TitleStateNode(int position, View convertView) {
this();
this.position = position;
this.convertView = convertView;
}
public void clear(){ //恢复原始状态
resetState();
Set<Map.Entry<Integer, ChapterCheckBoxStateNode>> chapterCheckBoxStateNodesEntry = chapterCheckBoxStateNodes.entrySet();
for(Iterator<Map.Entry<Integer, ChapterCheckBoxStateNode>> it = chapterCheckBoxStateNodesEntry.iterator();it.hasNext();){
Map.Entry<Integer, ChapterCheckBoxStateNode> chapterCheckBoxStateNodeEntry = it.next();
chapterCheckBoxStateNodeEntry.getValue().clear(); //调用相应子节点恢复到初始状态
}
}
} 步骤2）：结点的初始化
在Adapter的成员位置实例化了一个Map集合存储getView对应的position处的标题结点
private Map<Integer,TitleStateNode> titleStateNodesMap = new HashMap<>(); getView()方法（重点）：
---1)初始化标题结点对象
注意通过containsKey方法判断，保证只初始化一次。
(!.containsKey(position)){
.put(positionTitleStateNode(positionexpandableLayout))} 下面是没有设计数据结构之前的初始化Map代码，一对比就发现经过设计的数据结构的魅力了。
(!.containsKey(position)){
Log.(+ position).put(position)(){
.put(position)}
}
(!.containsKey(position)){
Log.(+ position).put(position)}
(!.containsKey(position)){
Log.(+ position).put(position)(){
.put(position)}
}
(!.containsKey(position)){
Log.(+ position).put(positionHashMap<IntegerBoolean>())}
(!.containsKey(position)){
Log.(+ position).put(positionHashMap<IntegerBoolean>())} ---2)得到对应position的状态结点，得到状态结点的章节结点，准备动态添加章节的view和初始化章节结点
TitleStateNode titleStateNode = .get(position)Map<IntegerChapterCheckBoxStateNode> chapterCheckBoxStateNodes = titleStateNode. 章节结点view动态添加以及相关的事件对状态结点进行保存和实时刷新
标题CheckBox事件以及折叠组件的事件处理与状态结点的更新
其它操作）：结点的遍历操作
a)选中标题结点，标题下的所有章节节点全部选中。
b)取消选中标题结点，标题下的所有章节节点全部取消选中。
c)章节的结点全部选中的时候，标题节点应全部选中。
d)章节的结点有一个未选中的时候，如果标题节点是选中状态，要取消选中。
e)全选功能：所有标题结点及其对应的章节结点全部选中。
f)取消全选功能：所有标题结点及其对应的章节结点全部取消全选。
g)删除功能：遍历所有的标题节点及下属的章节结点，拼接所有的章节节点的id传给删除接口。
从遍历操作，可以体会到良好的数据结构带来种种好处。解决之前多个map的“碎片化”，使数据与数据之前
连接十分的紧密，环环相扣，游刃有余。
作为一个外行人员，稍微能感受到一点了计算机的魅力，在此就写下了，忘路过的同行多提点建议。
------------算法章节---------------
十大编程算法助程序员走上高手之路
http://www.myexception.cn/other/1825523.html
1.算法和数据结构的关系
就像《梁山伯与祝英台》、《罗密欧与朱丽叶》中的故事主角的关系，两个主角少了一个这戏就不好看了。作
者说了，数据结构与算法要结合起来说才能有意思。
2.算法的定义
算法是对解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个动作。
3.算法的特性
输入输出、有穷性、确定性、可行性
4.
时间不够用，中间的以后慢慢写。。。
5.算法效率的评估
事前估算方法
判断算法，就是判断算法对于同一个问题执行的次数，一般一个算法都对应着一个函数，参数n的不同，算法的优越
度可能就不一样。
判断一个算法的效率时，函数中的常数项和其它次要项常常可以忽略，可应常常观注主项（最高阶项）的阶数。
6.算法时间复杂度
事前估算方法
度可能就不一
关于时间复杂度 http://blog.sina.com.cn/s/blog_6b32b0870100u0od.html
时间复杂度的表示方法：大O表示法，T(n) = O(f(n));
推导大O阶的方法：
常数阶：O(1)，不管n有多大，只要是个常数，就写成1。
单纯的分支结构（不包含在循环结构中），时间复杂度就是O(1).
示例：
int sum =0,n = 100;
sum = (1+n)*n/2;
sum = (1+n)*n/2;
...
sum = (1+n)*n/2;
printf("%d",sum); 线性阶：O(n)，循环中的代码要执行n次。
分析算法的时间复杂度，关键是要分析循环结构的运行情况。
int i;
for( i = 0;i < n; i++)
{
/*时间复杂度为O(1)的程序步骤序列*/
} 对数阶：O(log2n)，循环中的代码要执行log2n次。
int count = 1;
while(count < n)
{
count = count *2; //有多个少个2相乘等于n，求对数得到log2n
} while和for的区别，while事先不会知道执行多少次。
平方阶：O(n2)双重for循环。
int i,j;
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
/*时间复杂度为0(1)的程序步骤序列*/
}
} O(m*n)双重for循环。
int i,j;
for(i = 0; i < m; i++)
{
for(j = 0; j < n; j++)
{
/*时间复杂度为0(1)的程序步骤序列*/
}
} nLogn：典型的堆排序的时间复杂度。
其它例子
下面这个的时间复杂度怎么推算呢？ O(n2)
int i,j;
for(i = 0; i < n; i++)
{
for(j = i; j < n; j++) //注意j从i开始
{
/*时间复杂度为0(1)的程序步骤序列*/
}
} n+(n-1)+...+1 = n(n-1)/2 （这不是高斯算法的时间复杂度，而是高斯算法公式！)
再来一个，时间复杂度为O(n)
int i,j;
for(i = 0; i < n; i++)
{
function(i);
}
void function(int count)
{
printf("%d",count);
} 7.常见时间复杂度
8.时间复杂度的最坏情况与平均情况
9.空间复杂度
-----------线性表章节---------------
-----------------------------------二叉树总结----------------------------------
最近面试老是被问到树这种数据结构，就硬着头皮看了一下，记录一下心得吧。
图论基础：https://blog.csdn.net/saltriver/article/details/54428685
https://blog.csdn.net/saltriver/article/details/54428750 （树的一些基本概念）
二叉树的分类：http://www.cocoachina.com/articles/25518
https://blog.csdn.net/linjpg/article/details/80910806 （满二叉树、完全二叉树、平衡树、红黑树等）
树的旋转（难点）：https://blog.csdn.net/qq_24336773/article/details/81712866
1.树的特性
1) 从根到其它任何一个节点，有且仅有一条唯一的路径。
应用场景：文件目录
2）当树没有分支时，其实它就是一个链表
2.树的一些概念
对象：父节点、子节点、叶节点（叶子节点）、子树、层
行为：访问、遍历（按一定顺序访问树的所有节点）
3.二叉树
每个节点至多有两个子节点的树
概念：左子节点、右子节点
4.java版的二叉树的先序遍历、中序遍历以及后序遍历(递归以及非递归方式)
http://www.tuicool.com/articles/UzU3Ub
上面这个例子，其实不太好理解，我以梁勇作的《数据结构与算法分析》中的表达式树为例，来说明
先序遍历、中序遍历、后序遍历的区别：
下面是一张表达式树的树图
为了用java代码构造树模型，我对树图的节点进行了编号：根结点R，左侧结点依次用L加上数字来表
示，右侧结点依次用R+数字来表示。
结点类
public class Node {
private Object data;
private Node leftNode;
private Node rightNode;
//适用于只有数据没有左右子结点的结点
public Node(Object data) {
this.data = data;
this.leftNode = null;
this.rightNode = null;
}
//适用于有或没有左右子结点的结点
public Node(Object data, Node leftNode, Node rightNode) {
this.data = data;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
... //getter and setter method
} 主类：
public class BiaoDaShiTree {
public static Node init()
{
Node L5 = new Node("c");
Node L4 = new Node("b");
Node L3 = new Node("*",L4,L5);
Node L2 = new Node("a");
Node L1 = new Node("+",L2,L3);
Node R7 = new Node("g");
Node R6 = new Node("f");
Node R5 = new Node("e");
Node R4 = new Node("d");
Node R3 = new Node("*",R4,R5);
Node R2 = new Node("+",R3,R6);
Node R1 = new Node("*",R2,R7);
Node root = new Node("+",L1,R1);
return root;
}
public static void main(String[] args)
{
Node root = init();
System.out.println("前序遍历");
preorderTravesal(root);
System.out.println();
System.out.println("中序遍历");
inorderTravesal(root);
System.out.println();
System.out.println("后序遍历");
postorderTravesal(root);
}
//前序遍历
public static void preorderTravesal(Node root)
{
System.out.print(root.getData());
Node leftNode = root.getLeftNode();
Node rightNode = root.getRightNode();
if(leftNode !=null)
{
preorderTravesal(leftNode);
}
if(rightNode != null)
{
preorderTravesal(rightNode);
}
}
//中序遍历
public static void inorderTravesal(Node root)
{
Node leftNode = root.getLeftNode();
Node rightNode = root.getRightNode();
if(leftNode !=null)
{
inorderTravesal(leftNode);
}
System.out.print(root.getData());
if(rightNode != null)
{
inorderTravesal(rightNode);
}
}
//后序遍历
public static void postorderTravesal(Node root)
{
Node leftNode = root.getLeftNode();
Node rightNode = root.getRightNode();
if(leftNode !=null)
{
postorderTravesal(leftNode);
}
if(rightNode != null)
{
postorderTravesal(rightNode);
}
System.out.print(root.getData());
}
} 打印结果：
为什么这样打印，递归的具体的流程是什么？
总结归纳：
-------------------------------------------------------------------------------------
前序遍历：对结点的处理工作（2个例子就是打印结点数据）在对结点诸儿子结点计算之前进行的。
后序遍历：对结点的处理工作（2个例子就是打印结点数据）在对结点诸儿子结点计算之后进行的。
中序遍历：对结点的处理工作（2个例子就是打印结点数据）在对结点诸儿子结点计算之间进行的。
6.二叉树的节点操作
1）插入一个节点 （其实很简单）
确定新插入节点的位置
2）查找最大值与最小值
3）删除节点
答案：根据结点的位置分为3种情况：
1）结点是叶子结点
2）结点只有一个子结点
3）结点有大于2个子结点 （********）
用要删除的结点的中序后继结点代替要删除的结点
7.递归与尾递归总结
http://www.cnblogs.com/Anker/archive/2013/03/04/2943498.html
深度递归：
有时要做压力测试，由于接口是异步的，所以通过递归方式实现测试。但是如果如果递归次数过多，可能会有栈溢出的错误。这时可以采用队列的形式实现相关逻辑。
｜递归算法实战：
1）求连续签到的算法：
这个算法要抓住2个重点
***1：2条线，一条线是实际签到的日期序列，另一条线是实际时间的日期序列。
***2：递归的规律是比较上面的2条线，递归不停止，两条线向前推移。
/**
* @param latestDayIndex 绝对的，记录签到记录的索引。
* @param currentCalendarDay 当前天，相对的（并不是指的最近的一天）
* @return
*/
private int getContinuedDays(int latestDayIndex,CalendarDay currentCalendarDay){
CalendarDay latestSignedDate = allSignedDays.get(latestDayIndex);
if(latestDayIndex >= 1){
if(CalendarDayCompareUtil.is2CalendarDaySame(latestSignedDate,currentCalendarDay) || CalendarDayCompareUtil.isTheDay_CurrentDayBefore1Day(latestSignedDate,this.currentCalendarDay)){
//继续往前递归
return getContinuedDays(latestDayIndex - 1,CalendarDayCompareUtil.getBeforeDay(latestSignedDate));
}else{
return latestDayIndex;
}
}else{
return latestDayIndex;
}
} 8.二叉查找树
1）二叉查找树的定义：对于二叉查找树，它的任意节点X，它的左子树中的所有的项小于X的项，它的
右子树的所有的项大于X的项。
java二叉查找树实现 http://my.oschina.net/indestiny/blog/208297
9.AVL树
https://blog.csdn.net/qq_25343557/article/details/89110319
AVL树旋转：https://blog.csdn.net/weixin_30363263/article/details/85702725
https://blog.csdn.net/qq_24336773/article/details/81712866
10.红黑树
http://www.360doc.com/content/18/0904/19/25944647_783893127.shtml
https://www.cnblogs.com/skywang12345/p/3245399.html
面试中问到的关于二叉树的问题
1.二叉树怎么删除结点
答案：根据结点的位置分为3种情况：
1）结点是叶子结点
2）结点只有一个子结点
3）结点有大于2个子结点
2.二叉树怎么寻找两个结点的最低父结点
这个算法用java语言来写的少，基本是用c来写的。
寻找二叉树两个结点的最低共同父节点 http://www.cnblogs.com/venow/archive/2012/08/31/2664969.html
结合以前对图论的研究，我自己对这个问题也想到了一种解法：
因为树任意两个点之间的路径是唯一确定的，可以计算待求的两个节点到父结点的路径，然后分
离出两条路径之间的相同结点，再取到根结点的长度最长的结点即为最低父结点。
所以拿到一个需求的时候，首先最好不根考虑代码，先大体从宏观分析如何去实现。
9.二叉树的应用场景
1） Huffman编码：压缩数据
2）
-----------------------------------红-黑树总结--------------------------------http://www.cnblogs.com/skywang12345/p/3245399.html1.二叉树存在的问题
插入的数据是有序的话，二叉树就会变得不平衡。
2.红-黑树的诞生
1) 防止二叉树变成非平衡树
其它的平衡树还有AVL树、多叉树
-----------------------------------2-3-4树--------------------------------
http://blog.csdn.net/u010555682/article/details/51986232
-----------------------------------图--------------------------------1.一些概念
顶点
邻接
路径
连通图与非连通图，有向图，带权图
有向图：出度与入度的概念 https://blog.csdn.net/qq_43824791/article/details/88792899
2.图的表示
顶点的连接关系表示：邻接矩阵（二维数组）与邻接表（链表数组）
3.图的搜索
1）深度优先遍历法DFS
用栈来实现
2）广度优先遍历法BFS
用队列实现
-----------------------------------排序总结----------------------------------
https://www.runoob.com/w3cnote/merge-sort.html （10大经典排序算法）
基于比较的排序算法最坏时间复杂度为nlogn
基于非比较的排序算法
作为一名程序员，基本的算法应该用真实的代码就根准确无误地写出来。而写出来的基础并不是背下代码，而是对算法真正地去理解了。
以整型数组为例，来说明每种排序（从小到大）方式的实现。
int[] arr = new int[]{4,2,7,8,1}; 数据的两个元素置换抽取的方法
private static void swap(int[] arr, int i, int j) {
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
} 1.选择排序
外层for循环，依次遍历除末尾之外的所有元素；内层for循环，依次遍历外层for遍历的元素后面
的所有元素。
private static void choiceSort(int[] arr) {
for(int i = 0; i < arr.length -1 ; i ++)
{
for (int j = i + 1; j < arr.length ; j++)
{
if(arr[j] < arr[i])
{
swap(arr, i, j);
}
}
}
} 2.冒泡排序
https://blog.csdn.net/zcl_love_wx/article/details/83576962 （看不懂打我，竖着画图就直观了。）
外层for循环，不再是表示遍历元素的意思，而是表示循环的次数；（确定要冒泡的元素）
内层for循环，从0索引位置往后遍历，截止位置受外层for循环的控制。（置换，使元素冒泡。）
外层for循环，执行n-1次，每执行一次，内层循环执行次数就减1。
注意：冒泡的外层for循环代码和排序一样，但是表示的意义却是截然不同的。
private static void MaoPaoSort(int[] arr) {
for(int i = 0; i < arr.length - 1; i++)
{
for (int j = 0; j < arr.length - i - 1; j ++)
{
if(arr[j + 1] < arr[j])
{
swap(arr,j,j+1);
}
}
}
} 对于冒泡算法，可以进行优化。即如果集合元素本身是有效的，在第一次遍历的过程中，如果没有
发生置换，则用boolean值表示有序的，后面也就不用再去比较了。
3.插入排序
http://www.cnblogs.com/xiaoming0601/p/5862793.html
https://www.jianshu.com/p/27e14bb8539e
插入排序类似打扑克牌，接到牌之后，对牌进行整理，从小到大排列的过程。
原理：外层for循环和选择排序一样，也是遍历所有的元素。内层循环是从外层循环的索引位
置，向索引为0的位置进行遍历。如果发现内层循环的索引位置的值大于外层循环索引位置的
值，则向数组整体向右移动。
代码是如何实现的呢？
1）用for循环来实现
private static void insertSort2(int[] arr) {
int j = -1;
for(int i = 1; i < arr.length ; i ++)
{
int temp = arr[i];
for(j = i; j > 0 && arr[j-1] > temp ;j--)
{
arr[j] = arr[j - 1]; //数组依次向右移动
}
arr[j] = temp; //插入元素，将要比较的元素放到合适的位置。
}
} 2）用while循环来实现
for(int i = 1; i < arr.length ; i ++)
{
int j = i ;
int temp = arr[i];
while(j > 0 && arr[j-1] > temp )
{
arr[j] = arr[j - 1];
j--;
}
arr[j] = temp;
} 插入排序有1个好处：如果要比较的元素本身就是有序的，则只会走外层for循环，不会走内层循
环。但是选择排序与冒泡排序则需要加入一个boolean值方可达到优化的效果。
进行插入排序的数组，有序程度越高、数据量越小越高效。
高级排序
https://blog.csdn.net/KevinDYZS/article/details/79689722
4.希尔排序（缩减增量排序）
在插入排序的基础上优化的一种算法
这种排序稍微有些复杂，用三层循环实现，相当于对于若干数组的插入排序。时间复杂度和增量序列有关。最坏情况最小时间复杂度可达N的1.5次方，是第1种打破二次时间复杂度的排序算法。
http://www.cnblogs.com/chengxiao/p/6104371.html （讲解的挺详细）
https://blog.csdn.net/qq_39207948/article/details/80006224 （看过不会来打我）
不同的增量序列对希尔算法有着不同的时间复杂度。
5.快速排序
5-1）划分算法 http://blog.csdn.net/oxuanboy1/article/details/51295300
5-2）快速排序 http://blog.csdn.net/it_zjyang/article/details/53406764
注意选取基准值后，从最左或者最右比较。
时间复杂度最好是nlogn，最坏情况是n2。
6.基数排序
就是按照个、十、百。。。数字位置进行比较
7.堆排序 (nlogn)
https://blog.csdn.net/u010452388/article/details/81283998 （太他妈经典了，老子竟然看懂了。）
算法步骤(以升序为例)：
1》将无序数组构造成大堆根结构 （上浮算法）
此时索引为0的元素为最大值
2》固定最大值再构造堆
此时索引为0的元素最大值与最后一个元素交换之后，固定最后一个索引。
取除固定元素之后的所有元素再构造大堆根。
...
如此循环往复，最终就会得到一个升序的数组。
可见，算法与数据结构是相辅相成的，算法有时就得依托于数据结构。
堆排序时间复杂度推理：https://blog.csdn.net/runrun117/article/details/80288237
https://blog.csdn.net/qq_39032310/article/details/87470670
8.归并排序
https://www.ituring.com.cn/book/miniarticle/62897 （对各种算法的时间复杂度有总结图表）
http://www.sohu.com/a/307758292_120066333
https://www.cnblogs.com/chengxiao/p/6194356.html
https://www.jianshu.com/p/33cffa1ce613
归并排序的时间复杂度稳定在nlogn，无论最好最坏都是这么大。但是在合并子列表的时候，需要有个temp数组，所以空间复杂度会增加。
9.计数排序
10.桶排序
11.基数排序
-----------------------------------查找总结----------------------------------1.二分查找/折半查找
记住一点：二分查找的元素必须是有序的
private static void halfSearch(int[] arr, int target) {
int min = 0,max = arr.length -1,mid = -1;
while(max >= min) {
mid = (min + max)/2;
if(target < arr[mid]) {
max = mid - 1;
}else if(target > arr[mid]) {
min = mid + 1;
}else{
break;
}
}
System.out.println("target,index = " + mid + "value = " + arr[mid]);
} ******算法在实际开发中的体现与应用******
实际开发场景1： 我做过的一个app有做题的功能，需要对答案。对于多选题，比如服务器返回的正确答案是ABCD,但是用户选择顺序可能不同,假如是BDCA。怎么判断用户的选择是否是正确，即怎么判断两个字符串在这种规则(两个字符串总能在对方的串里找到对应的字符且两个串的字符个数相等)下是否相等呢？
这是我一开始想到的算法：把两个字符串的字符分别用2个Set集合存储起来，然后比较两个Set
集合。
(String str1String str2){
Set<Character> set1 = HashSet<>()Set<Character> set2 = HashSet<>()(i = i < str1.length()i++) {
set1.add(str1.charAt(i))}
(i = i < str2.length()i++) {
set2.add(str2.charAt(i))}
(set1.equals(set2)){
}
} 这是ios另外一个同学的思路，先排序再比较，我又再写了个算法：
(String str1String str2){
[] charArray1 = str1.toCharArray()[] charArray2 = str2.toCharArray()Arrays.(charArray1)Arrays.(charArray2)String s1 = Arrays.(charArray1)String s2 = Arrays.(charArray2)System..print(+ s1 + + s2)s1.equals(s2)} -----------------------------------字符串相关的数据结构----------------------------------
1.Java中的StringBuilder
如果有大量超长的字符串需要拼接，果然采用此类。在实际开发中，我试验过如果串长度超过10W个字节，用String来拼接需要5分钟，用StringBuilder只要1秒钟。这就让我有了探究StringBuilder底层数据结构的一个欲望。
StringBuilder清空的几种方式：setLength(0),replace(0,lastIndex,"")