資料結構學習網站：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,"")