前言：中序和后序遍歷迭代算法比較難获讳，對于初學者需要多花一點時間去理解阴颖，同時需要注意學習方式。我個人看代碼喜歡把代碼放到相關(guān)軟件里面丐膝，比如這里我使用的是CodeBlocks量愧，這樣比較有感覺。其次帅矗，邊畫圖邊理解是一種非常好的方法偎肃。
一、前序遍歷迭代算法
為了更好的說清楚遍歷的迭代算法浑此，決定用這張比較簡單的圖累颂。
不同于遞歸算法，迭代算法需要自己構(gòu)建棧尤勋。所以在學習迭代算法之前需要對棧的概念有所了解喘落。那什么是棧呢？簡單的說棧是一個線性表最冰，棧里面的元素具有線性關(guān)系瘦棋，進入棧的操作也稱為壓棧或者入棧暖哨。類似手槍的彈夾往里面壓入子彈赌朋，當取出子彈時，最先壓入彈夾的子彈肯定是最后一個取出篇裁，所以棧中元素進出棧有個特性沛慢，先進后出，后進先出达布。
//遞歸算法系統(tǒng)已經(jīng)自己構(gòu)建好了棧团甲，迭代算法則需要我們自己構(gòu)建棧。
public static void PreOrderTraverse(BiTree T){
if(T == null)
return;
Stack<BiTree> stack = new Stack<BiTree>();
stack.push(T);
while(!stack.isEmpty()){
BiTree cur = stack.pop();//取出棧頂元素
System.out.println(cur.value + " ");
//關(guān)鍵點：要先壓入右孩子黍聂，再壓入左孩子躺苦，這樣在出棧時會先打印左孩子再打印右孩子（棧：先進后出）
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
}
}
分析：新建一個棧 stack 身腻，將上圖A壓入到了棧中，在循環(huán)中匹厘，首先取出了A嘀趟，打印A，判斷A是否有右孩子愈诚，將右孩子C壓入棧中她按，繼續(xù)判斷A是否有左孩子，將左孩子B壓入棧中炕柔，因為A在stack.pop()時已經(jīng)彈棧了酌泰，所以現(xiàn)在棧里面有兩個元素，最底層元素是C匕累，倒數(shù)第二個元素是B宫莱。再次執(zhí)行循環(huán)，取出棧頂元素（此時的棧頂元素就是B）哩罪，打印B。同理巡验，判斷B是否有右孩子际插，發(fā)現(xiàn)B沒有右孩子，無操作显设。繼續(xù)判斷B是否有左孩子框弛，將D壓入棧中（此時棧中還有兩個元素，最底層的依然是C捕捂，倒數(shù)第二層的是D）瑟枫。再次執(zhí)行循環(huán)，取出了棧頂元素D指攒，打印D慷妙。繼續(xù)判斷D是否有左右孩子，依次類推就可以打印出：ABDGHCEIF允悦。
二膝擂、中序遍歷迭代算法
//中序遍歷迭代算法
void InOderTraverse(BiTree T){
if(T==null)
return;
Stack<BiTree> stack = new Stack<BiTree>();
BiTree cur = T;
while(!stack.isEmpty || T!=null){
if(cur != null){//循環(huán)遍歷左子樹
stack.push(cur);//將結(jié)點壓入棧中
cur = cur.left;//指針指向本結(jié)點的左子樹
}else{
cur = stack.pop();//取出棧頂元素
System.out.println(cur.val+"");//打印cur的值
cur = cur.right;
}
}
}
解析：
while循環(huán)語句外cur已經(jīng)被賦值，進入循環(huán)cur不等于null隙弛，執(zhí)行if語句中的代碼架馋，將A壓入棧中，并且修改cur指針全闷。if執(zhí)行完成以后再次循環(huán)cur仍然不等于null叉寂，就這樣一直循環(huán)遍歷左子樹，左子樹一直壓棧总珠，直到結(jié)點G時（此時棧中元素是ABDG）屏鳍，G沒有左孩子勘纯，所以cur等于null，當再次進行while循環(huán)時孕蝉，執(zhí)行else中的語句屡律，stack.pop()取出棧頂元素（棧先進后出，所以G是棧頂元素）降淮，此時就打印了第一個值G超埋。cur.right發(fā)現(xiàn)G沒有右孩子，所以cur還是null佳鳖，再次循環(huán)又進入到else語句中霍殴，現(xiàn)在stack.pop()方法取出的是元素D。打印D系吩，D是有右孩子的来庭，所以此時的cur經(jīng)過賦值以后是不為空的，下次循環(huán)將進入if語句中穿挨，會將H壓入棧中月弛。然后繼續(xù)判斷H是否有做孩子。以此類推科盛，就實現(xiàn)了中序遍歷帽衙。在本簡書中實現(xiàn)的遍歷方式只是比較常用的，實現(xiàn)方法也不止這一種贞绵！
三厉萝、后序遍歷迭代算法
根據(jù)后序遍歷的規(guī)則，可以知道后序遍歷是左右中結(jié)構(gòu)榨崩，例如G-H-D谴垫、還有E-F-C，最后遍歷根結(jié)點母蛛。為了實現(xiàn)這種規(guī)則的遍歷翩剪，新建了兩個棧，詳情寫在了代碼注釋中彩郊。
void postorderTraversal(BiTree T){
if(T== null)
return;
Stack<BiTree> stack = new Stack<BiTree>();//第一個stack用于添加結(jié)點和它的左右孩子肢专。
// 因為需要左右中輸出，還要進行翻轉(zhuǎn)焦辅，所以第一個棧是中左右壓入博杖。翻轉(zhuǎn)之后就是中右左，最后取出就是左右中了筷登。
Stack<BiTree> outstack = new Stack<BiTree>();//第二個outstack用于翻轉(zhuǎn)第一個stack輸出
stack.push(T);
while( !stack .isEmpty()){//確保所有元素都被翻轉(zhuǎn)轉(zhuǎn)移到第二個stack
BiTree cur = stack .pop();
outstack .push(cur);//把棧頂元素添加到第二個stack
if(cur.left != null){//把棧頂元素的左孩子添加入到第一個stack
stack .push(cur.left);
}
if(cur.right != null){//把棧頂元素的右孩子添加入到第一個stack
stack .push(cur.right);
}
}
while( !outstack .isEmpty()){//遍歷輸出第二個stack剃根，即為后序遍歷
System.out.println(outstack .pop().val+"");
}
}
分析：具體分析和上面的分析方法類似，不行你就畫兩個棧前方，一步步的來狈醉，多想想就OK了
四廉油、層序遍歷迭代算法
這里使用的是寬度優(yōu)先遍歷，什么是寬度優(yōu)先遍歷苗傅？是以離初狀態(tài)的狀態(tài)距離為序進行遍歷抒线。這是官方定義，我也一臉懵逼渣慕，寬度優(yōu)先遍歷說白了就是需要你自己維護一個隊列嘶炭。怎樣維護的？好好體會下面例子逊桦。
//層序遍歷二叉樹迭代
public static void levelTraversal(BiTree T){
if(T==null)
return;
LinkedList<BiTree> stack = new LinkedList<BiTree>()眨猎；
stack.push(T)
while(!stack.isEmpty){
TreeNode cur = stack.removeFirst();//removeFirst():移除此隊列中的第一個元素并返回此列表的第一個元素。
System.out.print(cur.val+"");
if(cur.left != null){
stack.push(cur.left);
}
if(cur.right != null){
stack.push(cur.right);
}
}
}
分析：注意這里創(chuàng)建的是鏈表强经。（自己畫圖）注意removeFirst()方法的作用睡陪，經(jīng)歷了上面的洗禮，這里應(yīng)該不難了匿情，才對兰迫。
五、總結(jié)
到這里二叉樹的基礎(chǔ)部分就結(jié)束了炬称，后面的內(nèi)容多嗎逮矛？多少并不重要，重要的是你已經(jīng)在開始了转砖。
- 二叉樹遍歷（恭喜已經(jīng)完成了）
- 二叉搜索樹
- 二叉搜索樹查找
- 二叉搜索樹插入和刪除
- AVL樹
- 二叉堆的實現(xiàn)
每月更新兩篇鲸伴，質(zhì)量保證府蔗，點擊關(guān)注！
聽說點喜歡的人運氣會一直很好９啊Ｐ粘唷！
