上一篇文章講述了樹的概念蟋软， 特征以及分類， 旨在讓我們理解什么是樹， 樹的一些常用的概念是什么幼驶，樹的分類有哪些等艾杏。如果還對這些不了解， 可以先看上一篇文章大話數(shù)據(jù)結(jié)構(gòu)之樹（一）盅藻。同時购桑，上一篇還留了一個小作業(yè)，其用意就是讓你根據(jù)自己的收獲氏淑，檢測一下是否真正理解了勃蜘。
本篇的主要內(nèi)容
什么是遞歸？
如何創(chuàng)建一顆樹假残？
二叉樹的遍歷
其中二叉樹的遍歷包含前序缭贡， 中序， 后序以及層序遍歷辉懒，包含遞歸與常規(guī)兩種實現(xiàn)方式阳惹。
本篇將會以上圖為參照， 生成一顆簡單的二叉樹眶俩，并執(zhí)行遍歷操作莹汤。
二叉樹是如何創(chuàng)建的？
在創(chuàng)建之前颠印， 我們還是要明確兩點概念：
-
什么是二叉樹纲岭？
樹是由一個根節(jié)點（樹根）衍生出的數(shù)據(jù)結(jié)構(gòu)， 每個節(jié)點（葉子節(jié)點除外）最多包含兩個子節(jié)點的樹稱為二叉樹线罕。
樹的最小單位是節(jié)點
上一篇說過止潮， 樹節(jié)點的信息包含兩部分： 1） 與其他節(jié)點的關(guān)系 2） 值 。 以上圖為例钞楼， 一個圓圈代表一個節(jié)點沽翔， 它有兩個元素組成： 與其他節(jié)點連接的線以及本身的值A(chǔ),B,C,D,E,F。
- 樹節(jié)點的關(guān)系
在二叉樹中窿凤，主要利用的關(guān)系有兩個： 父親節(jié)點（A）與子節(jié)點（BC）仅偎， 根據(jù)位置分為左孩子節(jié)點(B)與右孩子節(jié)點（C）。以下分別用父親和左孩子雳殊，右孩子指代橘沥。
那么如何創(chuàng)建一顆樹呢？
先來實現(xiàn)一個節(jié)點夯秃， 根據(jù)以上關(guān)系介紹座咆，節(jié)點的內(nèi)容有4個： 父親是誰痢艺？ 左孩子是誰？ 右孩子是誰介陶？ 值是什么堤舒？那么這里我們設(shè)定值的類型為String， 用來存儲A哺呜， B ~ F舌缤。如果你想實現(xiàn)一顆樹結(jié)構(gòu)，推薦使用泛型某残。
public class TreeNode {
public TreeNode parent;
public String data;
public TreeNode left;
public TreeNode right;
public TreeNode(String data) {
this.data = data;
}
public TreeNode(TreeNode parent, String data) {
this.parent = parent;
this.data = data;
}
public TreeNode(String data, TreeNode left, TreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
public TreeNode(TreeNode parent, String data, TreeNode left, TreeNode right) {
this.parent = parent;
this.data = data;
this.left = left;
this.right = right;
}
}
有了樹節(jié)點国撵，我們來創(chuàng)建一顆樹，步驟有兩步：
- 創(chuàng)建樹節(jié)點
- 創(chuàng)建樹節(jié)點之間的聯(lián)系
public static TreeNode createTree() {
// 創(chuàng)建根節(jié)點A
TreeNode a = new TreeNode("A");
// 創(chuàng)建A的子節(jié)點BC玻墅， 父節(jié)點指向A
TreeNode b = new TreeNode(a, "B");
TreeNode c = new TreeNode(a, "C");
// 創(chuàng)建關(guān)系介牙， A的左孩子和右孩子分別是B和C
a.left = b;
a.right = c;
// 創(chuàng)建B的子節(jié)點DE， 父節(jié)點指向B
TreeNode d = new TreeNode(b, "D");
TreeNode e = new TreeNode(b, "E");
// 創(chuàng)建關(guān)系澳厢， B的左孩子和右孩子分別是D和E
b.left = d;
b.right = e;
// 創(chuàng)建C的子節(jié)點F, 父節(jié)點指向C
TreeNode f = new TreeNode(c, "F");
// 創(chuàng)建關(guān)系环础， C的右孩子是F
c.right = f;
return a;
}
通過以上代碼， 一顆二叉樹就形成了（參照開始圖）剩拢。如果不明白喳整，可以對著上圖和注釋理解一下。
樹的遍歷涉及到遞歸以及非遞歸實現(xiàn)裸扶， 那么首先肯定是要明白一個概念的框都，什么是遞歸？ 如果理解不了遞歸呵晨， 那么遞歸的實現(xiàn)無疑是無病呻吟魏保； 那么要遞歸遍歷，則要先理解遞歸摸屠； 要理解遞歸疾嗅，首先要明白一種數(shù)據(jù)結(jié)構(gòu)姑裂， 那就是棧。那么我們從棧開始說起。
棧Stack
在數(shù)據(jù)結(jié)構(gòu)系列文章中扎附，有一篇提到了棧败许，如果不明白棧是什么肌蜻，可以返回看一下大話數(shù)據(jù)結(jié)構(gòu)之Vector,Stack谋旦。
本文中涉及的遞歸需要對棧的思想有一個清晰的認識，這樣能更好理解遞歸的概念桑嘶。
棧是一種后進先出的數(shù)據(jù)結(jié)構(gòu)炊汹。 在日常生活中，有很多這樣的現(xiàn)象逃顶，如一箱水果讨便，一池水等充甚； 他們的特點是相似的，比如容器的出入口只有一個霸褒， 后放入的水果或后流入的水伴找，總是被先拿出來或者先流出來。我們用一個圖來表示一下棧結(jié)構(gòu)
在上圖的棧中废菱， 只有一個入口與出口技矮。 我們不斷把小球放入，分別記為1昙啄， 2， 3寸五， 4梳凛； 那么取出時，肯定只能是4梳杏， 3韧拒， 2， 1十性。 入棧的操作我們常常稱之為壓棧叛溢，即放入了壓到棧底了。 在Android中的Activity就是以棧的形式管理的劲适。
遞歸
明白了棧的原理楷掉， 我們再來看遞歸。 這是一個很繞很難正確理解的概念霞势，很多時候我們覺得懂了烹植，其實不是。
先來看一下遞歸的定義
程序調(diào)用自身的編程技巧稱為遞歸（ recursion）愕贡。它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解草雕，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計算，大大地減少了程序的代碼量固以。一般來說墩虹，遞歸需要有邊界條件、遞歸前進段和遞歸返回段憨琳。當邊界條件不滿足時诫钓，遞歸前進；當邊界條件滿足時篙螟，遞歸返回尖坤。
以上是遞歸的官方定義，相信了之后很多人自然而然的進入會懵逼狀態(tài)闲擦。我們來分解一下
程序調(diào)用自身稱為遞歸慢味。我們平時喜歡說：以此類推场梆； 什么情況下，才能說以此類推呢纯路？ 比如斐波那契數(shù)列： 一個數(shù)列或油，每個數(shù)是之前兩個數(shù)的和，如1驰唬， 1顶岸， 2， 3叫编， 5辖佣， 8， 13... 我們說不完了搓逾，OK卷谈，以此類推。那么我們來總結(jié)以此類推的條件： 1. 我們可以清晰的描述每一次運算（N = N之前兩個數(shù)的和） 2. 過程很復(fù)雜（無限長）霞篡，我們說不完了世蔗。這個以此類推，說的就是“遞“的概念朗兵； 那么我們平常用污淋，肯定不可能用一個無限大的數(shù)，沒有盡頭余掖。然后考試會讓你計算10次計算就行了寸爆，也就是只要10次就返回了，這是“歸”的概念盐欺。
遞歸的條件有三： 邊界條件而昨，前進段和返回段。 那么計算10次就是邊界條件找田，你只要計算10次就行了歌憨，不需要讓你一直計算下去；在程序中墩衙，如果無限循環(huán)的一直執(zhí)行下去务嫡，那是一定要崩潰的。 什么是前進段和返回段漆改？ 當我們算了不到10次時心铃，我們需要一直算下去，這就是前進段挫剑； 當我們算到10次了去扣，我們不要再算了，這是返回段樊破。
再看斐波那契數(shù)列愉棱， 讓我們算一各斐波那契數(shù)列唆铐， 簡單嗎？如果要算第10次的結(jié)果奔滑，必然要知道第8和9次的結(jié)果艾岂，直到追溯到第1次和第2次；但是在這個大的計算工程中朋其，我們只需要關(guān)注一點王浴， f(n) = f(n - 1) + f(n - 2)就行了，這是核心計算梅猿。使用遞歸氓辣，我們就相當于只關(guān)注核心的計算，核心的實現(xiàn)袱蚓， 至于這么大一個工程怎么辦钞啸， 就讓它這么循環(huán)下去就行了。當然癞松，實際使用中必須要有邊界爽撒。
再看遞歸的定義入蛆，調(diào)用自身响蓉。上面說了，遞歸只關(guān)注核心實現(xiàn)哨毁， 像斐波那契數(shù)列一樣枫甲， 因為是要重復(fù)的執(zhí)行 f(n) = f(n - 1) + f(n - 2)。 因為要得到第10次結(jié)果f(10), 必然需要f(9), f(8)扼褪。f(9)又要得到f8, f7, 知道追根溯源到f1想幻。因此這個過程是重復(fù)的，因此要一次次調(diào)用自身话浇。
我們總結(jié)一下以上的解釋脏毯，然后再以例子驗證。
- 遞歸是調(diào)用自身的過程幔崖， 這是用法
- 遞歸要有邊界食店，這是保證可以執(zhí)行完畢的前提條件
斐波那契數(shù)列說了這么久， 來個例子
public static int febo(int n){
if(n==1){
return 1;
}
if(n==2){
return 1;
}
return febo(n-1)+febo(n-2);
}
結(jié)合代碼解釋一下定義赏寇。 假如我們要求第10個斐波那契數(shù)吉嫩， 也就是febo(10)。 我們使用蠻力來算的話嗅定， 先從1開始算自娩， 那么就是（大家閃開，我要念經(jīng)了Ｇ恕）：
第一個是1忙迁， 第2個是1脐彩， 第3個是2， 第4個3动漾， 第5個是5丁屎， 第6個是8 ...
1, 1, 2, 3, 5, 8, 13...
就算是使用for循環(huán)來算，也是相當麻煩旱眯，用定義來說晨川，這是一個復(fù)雜的工程。 然而我們現(xiàn)在只需要調(diào)用febo(10)就可以得出結(jié)果了删豺， 是不是應(yīng)了定義那句話： 把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解共虑。最后問題小的我們知道核心算法就可以了。這就是遞歸的好處呀页。
我們再來看febo的實現(xiàn)
return febo(n-1)+febo(n-2);
這是核心算法妈拌。我們的定義是什么來著？ 程序調(diào)用自身蓬蝶。 再看我們的核心實現(xiàn)尘分，可不就是嘛。
再來分析下實現(xiàn)丸氛， 我們是從10開始培愁，不斷地遞減的，n - 1, n - 2缓窜。也就是從10向0靠近定续。如果我們不加限制， 程序會一直執(zhí)行下去禾锤，崩潰私股；這顯然不是我們想要的，因此我們需要邊界恩掷，我們的邊界是什么呢倡鲸？ 第一個數(shù)是1， 第二個也是1黄娘。當n ==1時峭状， 返回1； n == 2時也返回1寸宏。我們來分析下三要素：
- 我們從10開始追溯追溯直到2就不調(diào)用自身了宁炫， 直接返回了。 那么我們邊界就是 n > 2吧氮凝。
- n > 2時羔巢，我們要不斷往前求和， 求f(9)~f(3)， 不斷前進竿秆， 這就是前進段
- n = 2 | n = 1時启摄， 直接返回了，這就是返回段幽钢。
注意： 在使用遞歸時歉备，一定要注意3要素。
通過以上分析匪燕， 應(yīng)該知道遞歸是什么鬼了蕾羊。遞歸就是不斷調(diào)用自己， 直到一定的條件終止帽驯，返回我們想要的結(jié)果龟再。遞歸中實現(xiàn)的是核心的算法實現(xiàn)，它可以把復(fù)雜的問題尼变，拆分為細小的問題解決利凑。
以上說了這么多，無非是想讓我們明白：
什么是遞歸嫌术？
遞歸解決什么問題哀澈？
遞歸如何使用？ 注意的問題是什么度气？
看到這里割按，希望你們可以停下，自己寫一個遞歸的小例子蚯嫌，這樣才能更深刻哲虾。
以下通過2個例子來鞏固以下丙躏，兩個例子一個帶返回值择示，一個不帶
遞歸示例1
依次打印從1到10（哇，這個好簡單晒旅！為了練習遞歸栅盲，請強制使用遞歸實現(xiàn)）
public static void main(String[] args) {
for(int i = 0; i < 10; i++) {
System.out.println(i);
}
print(0, 10);
}
private static void print(int num, int max) {
if (num > max) {
return;
}
System.out.println(num);
print(++num, max);
}
這是一個很簡單的例子。 但不要掉以輕心废恋。雖然我們可以使用循環(huán)輕松實現(xiàn)谈秫， 但是很多問題足夠復(fù)雜，是循環(huán)解決不了的鱼鼓。print(）方法是我們的核心方法拟烫，就是打印。你可以分析一下三要素是什么迄本？ 看看是否真正理解了遞歸的定義硕淑。相對于不斷for循環(huán)打印， 我們只調(diào)用了一次print(0, 10)方法就得到了我們想要的結(jié)果。
遞歸示例2
求第10個斐波那契數(shù)
public static int febo(int n){
if(n==1){
return 1;
}
if(n==2){
return 1;
}
return febo(n-1)+febo(n-2);
}
public static void main(String[] args) {
febo(10);
}
上面已經(jīng)分析過了置媳，不再重復(fù)分析于樟。 到這里，很多人奇怪了拇囊，遞歸就遞歸迂曲，你為什么先將棧呢？接下來借著斐波那契數(shù)列來講解一下遞歸的原理寥袭。
遞歸其實是一個不斷壓棧的過程路捧。 febo(10)為例的話真心太長，下面以febo(5)為例說明, 以下記為F5
F5 = F4 + F3 = (F3 + F2) + F3 = (F2 + F1) + F2 ) + F3;
1 2 3
這是F5的計算過程传黄，每一次嵌套(每個括號表示一次嵌套)都會把 + 后面的部分壓棧鬓长，因為按執(zhí)行順序，必須先執(zhí)行 + 前面的部分尝江。上面標注數(shù)字的+部分為每次嵌套后壓棧的部分涉波， 第一次 + F3不執(zhí)行， 第二次 + F2不執(zhí)行炭序， 第三次 + F1不執(zhí)行啤覆。F5的遞歸計算過程，最后轉(zhuǎn)化為了先計算出F1與F2, 然后是F3, 再然后F4惭聂。 + 前面部分都計算出結(jié)果后窗声，再從 + F1開始向后計算，知道 + F3辜纲。
我們可以看出這個過程笨觅， 計算F5的值， F5是最后得到最終值的耕腾； 是先計算F1,F2见剩； 根據(jù)F1 + F2計算F3; 根據(jù)F2 + F3計算F4， 最后才是F5扫俺。
理解了棧的原理之后苍苞，你會發(fā)現(xiàn)，你媽狼纬，這和棧的原理是一樣的啊羹呵，后進先出。F5最先開始調(diào)用疗琉，卻在最后執(zhí)行冈欢； F1是最后調(diào)用， 卻在最開始執(zhí)行盈简。
以后會遇到復(fù)雜的情況凑耻，心里時刻裝著一個棧犯戏，分析起來會容易很多。
遞歸的優(yōu)勢是可以輕易的把一個復(fù)雜的問題簡單化拳话， 轉(zhuǎn)化為最簡單最核心的實現(xiàn)先匪。 遞歸的缺點也很明顯， 遞歸很容易出現(xiàn)問題弃衍，所以一定要保證邊界的正確性呀非，確保不會出現(xiàn)死循環(huán)，一直執(zhí)行镜盯。 其次是遞歸相對于常規(guī)實現(xiàn)來說岸裙，資源的消耗高很多，效率低很多速缆。所以想使用遞歸的你降允，一定要謹慎。
樹的遍歷
樹的遍歷有4種方式艺糜，分別是前序遍歷剧董， 中序遍歷， 后序遍歷以及按層遍歷破停； 其中翅楼，前中后序的遍歷說的是父節(jié)點;層序則是按層進行遍歷。下圖是一個小的滿二叉樹真慢，以圖為例
上面提到毅臊，前序，中序黑界，后序是指父節(jié)點的優(yōu)先級管嬉。子節(jié)點的順序都是按從左到右。
前序遍歷： A（父節(jié)點在前） B（左孩子） C（右孩子）
中序遍歷： B A C
后序遍歷： B C A
層序遍歷： A B C
看出問題來了么朗鸠？ 前序是先遍歷父節(jié)點蚯撩， 后序是后遍歷父節(jié)點，中序則是父節(jié)點在中間童社。層序是按層來遍歷的求厕，第一層只有A著隆， 第二層B和C扰楼。
小圖來說明概念， 這個大圖再次拿過來美浦，來解除一些疑惑弦赖。
前： A B D E C F
中： D B E A C F
后： D E B F C A
層： A B C D E F
前序解析： 先遍歷A ， 然后遍歷左子樹BDE浦辨， 最后遍歷右子樹CF; 左子樹先遍歷父節(jié)點B ,然后左孩子D蹬竖，右孩子E； 右子樹先遍歷C, 然后是右孩子F。 最后的結(jié)果： A B D E C F
遍歷是從根節(jié)點開始币厕，以子樹為單位的列另，而不僅僅是左孩子。最后拼接而成最終遍歷結(jié)果旦装。以前序分析為例页衙，中序和后序就是上述結(jié)果。中序是先遍歷左子樹阴绢， 然后根節(jié)點店乐，最后右子樹。后序是左子樹呻袭， 右子樹眨八， 根節(jié)點。
層遍歷則是按層級進行遍歷左电， 第一層A 廉侧， 第二層 B C ， 第三層 D E F 篓足。
在面試中伏穆，或許會出現(xiàn)給你前中后序任意兩個，來還原樹的題目纷纫，因此在這點上枕扫，我們最好可以思考一下這些排序的特點。
前序： 第一個元素必然是根節(jié)點
后序： 最后一個元素必然是根節(jié)點
層序： 第一個元素必然是根節(jié)點
剩下的就是考驗?zāi)愕姆治瞿芰α巳杩１热缪糖疲呀?jīng)前序和中序，如何推測后序染簇？
- 由前序得参滴， 根節(jié)點是A
- 代入根節(jié)點A， 得知A的左子樹是DBE, 右子樹是CF
- 由前序得知锻弓，A的左孩子必定是B砾赔，（由2知，A有左子樹青灼， 那么根據(jù)前中后規(guī)則暴心， B必然是左孩子）
- 前序B D E得知兩種情況， 1） B有左孩子D 右孩子E 2） B無左孩子杂拨， 有右子樹DE
- 中序D B E得知专普， B一定有左孩子，因為左中右嘛弹沽，沒有左孩子不可能存在D B這樣的排序
- 根據(jù)4 和 5檀夹，排序4下的2）筋粗，得知左子樹就是B的左孩子D， 右孩子E
- 由前序得知炸渡， C是A的右孩子（A有右子樹娜亿，所以一定存在根節(jié)點）
- 前序CF，中序CF得知蚌堵， F是C的右孩子（中序F在C之后）
9.得出最終的樹
根據(jù)上述例子暇唾， 大家最好鍛煉一下兩兩組合推測出樹是什么樣的？ 這樣可以加深對樹遍歷的理解辰斋。
樹是如何遍歷的策州？ 上面已經(jīng)講述的足夠清晰， 我們只需要注意一點宫仗，就是一定是子樹而非單純的子節(jié)點够挂。如前序就是根節(jié)點然后左子樹右子樹。接下來藕夫，我們使用代碼來實現(xiàn)樹的遍歷孽糖。
遞歸實現(xiàn)遍歷
樹的遍歷，采用遞歸實現(xiàn)特別好理解毅贮，幾乎和定義一致办悟；但是有一個前提，一定要明白什么是遞歸滩褥？還不明白遞歸的小伙伴建議回上面理解一下遞歸的定義以及特點病蛉。
public static void travelPreOrder(TreeNode root) {
// 前序遍歷， 遍歷順序： parent -> left -> child
if (root == null) {
return;
}
System.out.println(root.data);
travelPreOrder(root.left);
travelPreOrder(root.right);
}
public static void travelMidOrder(TreeNode root) {
// 中序遍歷瑰煎， 遍歷順序： left -> parent -> child
if (root == null) {
return;
}
travelMidOrder(root.left);
System.out.println(root.data);
travelMidOrder(root.right);
}
public static void travelPostOrder(TreeNode root) {
// 后序遍歷铺然， 遍歷順序： left -> child -> parent
if (root == null) {
return;
}
travelPostOrder(root.left);
travelPostOrder(root.right);
System.out.println(root.data);
}
看到書的遍歷的遞歸實現(xiàn)，是不是眼前一亮酒甸！樹的遍歷從根節(jié)點一步步直到所有的葉子節(jié)點魄健， 還是蠻復(fù)雜的；但是我們知道遍歷的規(guī)則插勤，因此就有了上述實現(xiàn)沽瘦，這就是遞歸 的威力。上述實現(xiàn)為按遍歷方式打印樹的節(jié)點农尖，以trabelPreOrder為例析恋， 就是先遍歷根節(jié)點（輸出root.data）, 然后遍歷左子樹trabelPreOrder（root.left）也即左孩子的子樹；最后是右子樹卤橄。
遞歸實現(xiàn)就不做解釋了绿满，掃一眼就知道什么意思，前提是真正明白了遞歸和遍歷的原理窟扑。下面重點來看非遞歸的實現(xiàn)方式喇颁。
非遞歸遍歷
先來看前序遍歷的非遞歸實現(xiàn)
public static void travelPre(TreeNode root) {
TreeNode parent = root;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || parent != null) {
while (parent != null) {
System.out.println(parent.data);
stack.push(parent);
parent = parent.left;
}
if (!stack.isEmpty()) {
parent = stack.pop();
parent = parent.right;
}
}
}
首先來詳細的分析一下，雖然我們已經(jīng)知道了前序遍歷是怎么遍歷的嚎货；但是代碼和根據(jù)樹寫遍歷還是不同的橘霎。
- 遍歷的順序是左子樹， 根殖属， 右子樹（記住姐叁，一定是子樹哦）
- 遍歷是從根節(jié)點開始的
- 上圖的前序遍歷是： A B D E C F
- 分析： A B D 是左孩子，左孩子的左孩子... 左孩子窮盡到盡頭也即最左的左孩子洗显，也就是D
- 分析： 然后是E外潜， 從最左的左孩子開始，遍歷該節(jié)點的右子樹挠唆，從B的右子樹E, 到A的右子樹C
- 分析： 左子樹遍歷完畢处窥，開始遍歷右子樹。（同樣的套路）
根據(jù)分析來看代碼玄组，我們上面說過滔驾， 理解遞歸的最好的方式是棧，后進先出俄讹。那么實現(xiàn)自然以棧為存儲結(jié)構(gòu)哆致。
while (parent != null) {
System.out.println(parent.data);
stack.push(parent);
parent = parent.left;
}
- 先看分析一（最左側(cè)箭頭）：
先是遍歷左子樹，不斷尋找左孩子節(jié)點患膛。上述代碼的作用是摊阀， 先訪問根節(jié)點（打印）踪蹬， 然后不斷遍歷該節(jié)點的左子樹部服，直到找到最左左孩子。 上圖中的最左側(cè)的箭頭计福， 從A開始蝉绷，打印A； 然后遍歷A的左子樹枝缔， 即從A的左孩子B開始布疙， parent = parent.left（此時的parent成了B）， 還是先打印B愿卸，然后遍歷B的左子樹灵临， 直到最左的左孩子D，D沒有左孩子了趴荸。
我們手動分析一下遍歷過程
- 遍歷根節(jié)點A
- A的左子樹是BDE, 遍歷左子樹
- A的左子樹的根節(jié)點是B儒溉，遍歷B
- B的左子樹是D（雖然只有一個節(jié)點）
- 遍歷D， D沒有左子樹发钝， D沒有右子樹顿涣， D子樹結(jié)束
- 從D向上回溯波闹， B遍歷，B左子樹遍歷涛碑，開始遍歷右子樹E
- 遍歷E精堕， E沒有左子樹，也沒有右子樹蒲障， E子樹結(jié)束歹篓， B的右子樹結(jié)束， A的左子樹結(jié)束
- 回溯到A揉阎， A遍歷完成庄撮， A的左子樹遍歷完成， 遍歷A的右子樹CF
- 遍歷C, C沒有左子樹毙籽， C有右子樹F
- 遍歷F, F沒有左子樹洞斯，也沒有右子樹， F子樹結(jié)束惧财， C子樹結(jié)束巡扇，A的右子樹遍歷結(jié)束
- 整個樹的遍歷結(jié)束
根據(jù)上述遍歷過程的分析，對比前序遍歷的定義垮衷，好好的理解一下厅翔。 我們理解很深的是： 1）我們遍歷的是子樹， 而不單單是子節(jié)點搀突； 2）右子樹的遍歷和左子樹套路是一樣的 3） 先遍歷根節(jié)點刀闷，一路向左找，這樣既遍歷了根節(jié)點ABD, 又遍歷了左子樹B是A的左子樹根節(jié)點仰迁， D又是B的左子樹根節(jié)點甸昏。然后遍歷右子樹的過程是從D到B到A的，這是一個從低端回溯的過程徐许∈┟郏可以看圖的箭頭， 先從A向下到D雌隅， 然后從D向上到A翻默；A的右子樹的遍歷原理相同。
再來看上面的源碼恰起， 從A開始修械，不斷打印根節(jié)點；然后parent -> parent.left检盼。 也即一級一級不斷指向左孩子A -> B ->D肯污。這段代碼結(jié)束后，我們的棧中存儲的是A B D, 打印的根節(jié)點A B D, 當然B相對A來說是左子樹，但是在A的左子樹中相當于根節(jié)點蹦渣，是相對的哄芜。然后我們打印到D了， 根據(jù)上面的分析過程剂桥， 開始從D回溯到A忠烛，打印右子樹属提∪ǘ海看下面的代碼
if (!stack.isEmpty()) {
parent = stack.pop();
parent = parent.right;
}
左子樹的根節(jié)點都入棧了，此時為A B D, 那么開始出棧了冤议。 棧是后進先出的斟薇，第一個肯定是D了， 然后開始遍歷D的右子樹恕酸，要結(jié)合上面一段代碼堪滨。D沒有右子樹，然后出棧的是B蕊温， 遍歷E的子樹了袱箱；最后是A的右子樹CF。
再來總結(jié)一下這個過程义矛，左子樹的遍歷永遠是一個不斷向左向下尋找的過程发笔。 A的左子樹是BD, 不斷向左向下。 B的右子樹只有一個E凉翻，可能不明顯了讨。如果E有一個左孩子G, 那么E的左子樹遍歷也是不斷向左向下尋找的過程。找尋到子樹的最左的節(jié)點后制轰， 又是一個回溯的過程前计。比如A - B - D , 然后從D - B - A回溯右子樹。這就是典型的棧結(jié)構(gòu)垃杖。
平行的向左下的箭頭都是找尋左子樹的過程男杈。
平行的向右上的箭頭都是回溯的過程。
再看代碼整體调俘，我們不斷通過左子樹的壓棧伶棒，右子樹的出棧，最終遍歷整個樹脉漏。到這里苞冯，最好結(jié)合的分析和代碼多想一下，非遞歸的方式侧巨，真的很難理解舅锄。
前序遍歷講述的足夠詳細了， 那么中序就不仔細講了，因為套路是一樣的皇忿。先仔細琢磨畴蹭，多琢磨幾遍，理解之后再看中序遍歷的源碼
public static void travelMiddle(TreeNode root) {
if (root == null) {
return;
}
TreeNode parent = root;
Stack<TreeNode> stack = new Stack<>();
// A B D
while (!stack.isEmpty() || parent != null) {
while (parent != null) {
stack.push(parent);
parent = parent.left;
}
// ABD GH I
// A
// B C
// D E F
// G
// H I
if (!stack.isEmpty()) {
parent = stack.pop();
System.out.println(parent.data);
parent = parent.right;
}
}
}
以上是中序遍歷鳍烁， 代碼很相似叨襟。我們就要分析一下前序，中序的區(qū)別在哪幔荒？ 根節(jié)點的遍歷順序糊闽。 前序遍歷時，沒加入一個根節(jié)點爹梁， 就打印了右犹。然后中序呢， 我們要先打印完左子樹后姚垃， 才能打印根節(jié)點念链。怎么做呢？ 左子樹必須遍歷完成后积糯，才能打印根節(jié)點掂墓。 那么 BDE都打印了，才能打印A看成。 先遍歷BDE, 要打印B,必須先打印D吧君编，有沒有什么啟發(fā)？ 左子樹的遍歷是從最左孩子開始的绍昂。先找啦粹，最左孩子，所以入棧操作同前序窘游，找到最左孩子D唠椭。因為最左孩子的特點是沒有左子樹的啊，有的話就不是最左了忍饰。所以出棧后打印D贪嫂， 沒有左子樹，打印了根節(jié)點D, 那么接下來就是D的右子樹了艾蓝，這時parent -> parent.right 指向右子樹力崇。D打印完后，回溯到B赢织，回溯到A亮靴， 以此類推...
接下來再說后序， 相比于前序中序于置，后序相對復(fù)雜一些茧吊，也更難理解一些。我們結(jié)合代碼來分析一下
public static void travelPost(TreeNode root) {
final boolean isDebug = false;
if (root == null) {
return;
}
TreeNode target = root;
Stack<TreeNode> stack = new Stack<>();
stack.add(target);
while (!stack.isEmpty() || target != null) {
//從指定節(jié)點開始， 找到最左子節(jié)點（特點：沒有左子樹）
// 禁止再次壓棧 visitCount == 0
while (target != null && target.visitCount == 0) {
target.visitCount = 0;
stack.push(target);
if (isDebug)
System.out.println("++++入棧： " + target.data);
target = target.left;
}
if (!stack.isEmpty()) {
target = stack.lastElement();
if (target.left == null && target.right == null) {
// 沒有左右子樹搓侄，為葉子節(jié)點 -> 左（Null） 根（target） 右（Null）
// 葉子節(jié)點只訪問一次瞄桨， 等同左右子樹遍歷結(jié)束
target.visitCount = 2;
}
if (target.left == null && target.right != null) {
if (target.visitCount == 0) {
target.visitCount = 1;
}
}
final int visitCount = target.visitCount;
if (visitCount == 1) {
// 1. 左子樹遍歷結(jié)束，開始遍歷右子樹
target = target.right;
if (isDebug)
System.out.println("^^^^^將要訪問： " + target.data);
}
if (visitCount == 2) {
// -> 左右子樹都遍歷結(jié)束讶踪，遍歷根節(jié)點
// 訪問根節(jié)點
final TreeNode popNode = stack.pop();
System.out.println(popNode.data);
if (isDebug)
System.out.println(">>>>>出棧并訪問： " + popNode.data);
if (stack.isEmpty()) {
return;
}
// 回溯
target = stack.peek();
// 一顆子樹遍歷結(jié)束后芯侥，回溯的節(jié)點訪問數(shù) + 1
target.visitCount++;
if (isDebug)
System.out.println("<<<<<回溯到： " + target.data);
}
}
}
}
后序遍歷的非遞歸實現(xiàn)，網(wǎng)上有很多方法乳讥。 以上是根據(jù)自己的理解不斷調(diào)試的結(jié)果柱查。感覺還是比較好理解。
先來看上圖的后序遍歷過程
D E B | F C | A
要遍歷A雏婶，先遍歷左子樹BDE, 然后遍歷右子樹CF
遍歷是從最左子節(jié)點D開始物赶， 那么如何找到D 白指？ 就是從A到D的尋找算法留晚。上面說過兩條線： 一個尋找， 一個回溯告嘲。
從A尋找D错维，尋找線，如果認真看過上面的前中序遍歷橄唬， 應(yīng)該很快就想起來赋焕，就是那個while循環(huán)
找到了D， 然后從D開始回溯直到A仰楚。
5.后序遍歷中隆判，每個節(jié)點是訪問兩次的，比如B僧界，D子樹遍歷結(jié)束侨嘀，回溯到B； 然后遍歷右子樹E捂襟， 結(jié)束后咬腕，還是回到B。訪問了兩次葬荷，第一次是左子樹遍歷結(jié)束涨共； 第二次是右子樹遍歷結(jié)束。有些節(jié)點可能沒有左子樹宠漩，或右子樹举反，甚至都沒有，如D扒吁，其實也是兩次火鼻。只不過我們直接判斷l(xiāng)eftChild為空， rightChild為空，省略了而已凝危。
6.那么A的左子樹波俄，順序就是D E B ,其實執(zhí)行是D -> B -> E -> B
7.以此類推
在分析代碼之前，我們先普及兩個點：
- 怎么實現(xiàn)第二次經(jīng)過節(jié)點B, 才會訪問B呢蛾默？ 我們在TreeNode中加入了一個變量visitCount（訪問次數(shù)）懦铺。默認初始是沒訪問的visitCount = 0; 當左子樹遍歷完成， 那么visitCount = 1; 右子樹遍歷完成支鸡， 那么visitCount = 2冬念。 也就是說只有當visitCount = 2 并且經(jīng)過了B節(jié)點時，才會遍歷B牧挣， 此時整棵B的子樹就遍歷完成了急前。
2.既然加了visitCount, 那么不同的visitCount代表著什么意義，又需要執(zhí)行什么操作呢瀑构？ 左子樹遍歷是個神奇的東西裆针。如在A尋找D的過程中， 棧的結(jié)構(gòu)是：A B D寺晌。 D就是一棵只有一個節(jié)點的子樹世吨， B的左子樹。D遍歷完成后呻征，也同時意味著B的左子樹完成了耘婚，這時候同時設(shè)置B的訪問是1。然后再指向B的右子樹陆赋，遍歷E沐祷。我們總結(jié)一下：
2.1 只有在左子樹或右子樹遍歷完成后， 才會visitCount + 1攒岛。
2.2 B的 左子樹遍歷完成后赖临， visitCount = 1, 此時的動作是切換到B的右孩子E，遍歷右子樹
2.3 B的右子樹遍歷完成后阵子， visitCount = 2, 此時的動作是訪問根節(jié)點B, 然后回溯到A思杯。是的，B這棵子樹遍歷完成挠进，意味著A的左子樹遍歷完成了色乾，同時A的visitCount 就是1了。
- 特殊處理领突。 比如葉子節(jié)點D暖璧，這種沒有左子樹，也沒有右子樹君旦，默認初始化visitCount就是2了澎办。因為沒有啊嘲碱，不需要遍歷，相當于已經(jīng)遍歷完了局蚀，因此訪問的時候直接就訪問D了麦锯，然后出棧。
理解了上面3條解析琅绅，看代碼就不會懵逼了扶欣。一起看吧
//從指定節(jié)點開始， 找到最左子節(jié)點（特點：沒有左子樹）
// 禁止再次壓棧 visitCount == 0
while (target != null && target.visitCount == 0) {
target.visitCount = 0;
stack.push(target);
if (isDebug)
System.out.println("++++入棧： " + target.data);
target = target.left;
}
從A開始千扶，不斷尋找直到找到D（D沒有左孩子）料祠。此時入棧，默認visitCount是0的澎羞，也就是初始化值髓绽。至于為什么判斷==0才能入棧呢？是為了防止重復(fù)入棧妆绞。大家看顺呕， A尋找D時，ABD都入棧了摆碉。 D遍歷結(jié)束后塘匣， 回溯到B了，這時候B肯定不能再次入棧了吧巷帝，當然也不能出棧，因為還要遍歷右子樹扫夜。
target = stack.lastElement();
if (target.left == null && target.right == null) {
// 沒有左右子樹楞泼，為葉子節(jié)點 -> 左（Null） 根（target） 右（Null）
// 葉子節(jié)點只訪問一次， 等同左右子樹遍歷結(jié)束
target.visitCount = 2;
}
取棧頂元素笤闯，棧（ABD）此時棧頂是D堕阔，后進先出】盼叮看看是不是葉子節(jié)點（沒有左孩子超陆，也沒有右孩子，不孕不育）浦马，如果是葉子節(jié)點时呀，相當于左右子樹遍歷都結(jié)束了，上面說過晶默，此時visitCount設(shè)置為2谨娜， 所有的葉子節(jié)點都是直接訪問的，因為沒有子樹可以遍歷了磺陡。上面說過visitCount = 2, 對應(yīng)的操作就是訪問根節(jié)點D趴梢，然后出椖螅回溯。
再往下就看到我們的操作了
final int visitCount = target.visitCount;
if (visitCount == 1) {
// 1. 左子樹遍歷結(jié)束坞靶，開始遍歷右子樹
target = target.right;
if (isDebug)
System.out.println("^^^^^將要訪問： " + target.data);
}
if (visitCount == 2) {
// -> 左右子樹都遍歷結(jié)束憔狞，遍歷根節(jié)點
// 訪問根節(jié)點
final TreeNode popNode = stack.pop();
System.out.println(popNode.data);
if (isDebug)
System.out.println(">>>>>出棧并訪問： " + popNode.data);
if (stack.isEmpty()) {
return;
}
// 回溯
target = stack.peek();
// 一顆子樹遍歷結(jié)束后，回溯的節(jié)點訪問數(shù) + 1
target.visitCount++;
if (isDebug)
System.out.println("<<<<<回溯到： " + target.data);
}
上面提到過彰阴，VisitCount = 1時躯喇，對應(yīng)的是訪問右子樹，因為此時左子樹遍歷結(jié)束了硝枉。 VisitCount = 2時廉丽， 對應(yīng)的是訪問根節(jié)點，然后回溯妻味。 右子樹是怎么訪問的罢埂？ target指向了右孩子责球，然后向下執(zhí)行完了焦履，重新走while(), while的作用說了很多次了，以右孩子為根節(jié)點雏逾，遍歷右子樹嘉裤，這時候肯定又是一個重復(fù)的過程了，先從根節(jié)點找最左的子節(jié)點栖博，然后2屑宠，3，4...
VisitCount = 2時仇让，訪問根節(jié)點了典奉。 怎么訪問呢？ 先訪問并出棧
final TreeNode popNode = stack.pop();
System.out.println(popNode.data);
僅僅訪問出棧還不夠啊丧叽，訪問 + 出棧卫玖，說明以target為根節(jié)點的子樹訪問完成了。但是還要繼續(xù)往上回溯啊踊淳，就是接下來的操作假瞬，回溯到B， 然后B.VisitCount_++;(D就是B的左子樹迂尝，D結(jié)束了脱茉，B的VisitCount當然要+1了，此時就是1了)雹舀。 這兩個順帶的操作一定要搞清楚芦劣， D樹的結(jié)束，就是B左子樹的結(jié)束说榆。為什么中間還要一個判斷空棧呢虚吟？ 想一下寸认，如果最后訪問了A，那就結(jié)束了啊串慰，不然崩了偏塞，A是最后一個棧元素， A都出棧了邦鲫，你還peek啥灸叼。
眼尖的伙計發(fā)現(xiàn)了，你中間還有一段是什么鬼庆捺？ 兄弟說的是這個吧
if (target.left == null && target.right != null) {
if (target.visitCount == 0) {
target.visitCount = 1;
}
}
前面說古今，很多人納悶了，又說過滔以，說的啥捉腥？ 葉子節(jié)點沒有左子樹右子樹，相當于左右子樹遍歷結(jié)束了你画，可以直接訪問根節(jié)點抵碟。 那么一個節(jié)點沒有左子樹，只有右子樹呢坏匪？ 這時當然就相當于左子樹遍歷完畢了拟逮。又有好事的說了，那只有左子樹适滓，沒有右子樹的情況呢敦迄？ 乖別鬧，我們的操作有右子樹遍歷和根節(jié)點遍歷粒竖，卻沒有左子樹遍歷颅崩，因為左子樹遍歷是順帶的。
沒有右子樹蕊苗，毫不影響。
剛開始寫后序沿彭，一邊琢磨一邊修改朽砰， 耗時良久。 寫完之后喉刘，總結(jié)發(fā)現(xiàn)瞧柔，其實并沒有想的那么麻煩。
明確順序 睦裳， 左子樹 -> 右子樹 -> 根節(jié)點
明確主線： 從A-B-D（尋找）造锅， 從底部開始遍歷，逐層向根節(jié)點A回溯廉邑，直至A的左子樹都遍歷完成哥蔚。也即D樹遍歷倒谷，B 樹遍歷，A樹遍歷
3.以一棵子樹BDE為例糙箍， D是葉子節(jié)點渤愁，直接訪問， B的左子樹遍歷結(jié)束深夯， 然后回溯到B跳B的右子樹抖格。如果B的右子樹不只是E，而是E下面還有子節(jié)點咕晋。 那么以E為根節(jié)點雹拄，還是執(zhí)行以上邏輯，即從E開始尋找最左的子節(jié)點掌呜， 從最左的子節(jié)點開始滓玖，執(zhí)行BDE樹的過程。然后一級一級回溯到子樹的根節(jié)點E站辉。所以呢撞，無論是從根節(jié)點尋找最左的子節(jié)點， 還是左根右的遍歷饰剥，都是重復(fù)的過程殊霞。這樣思路就分明了
樹的遍歷是一步步拆分的過程，比如A樹（A作為根節(jié)點）汰蓉， 然后拆分為左子樹（B樹）和右子樹（C樹）绷蹲。這時A就是一個獨立的頂點。 然后B樹和C樹為獨立的樹顾孽。 先遍歷左子樹C樹祝钢，然后拆分C樹，這樣一級級拆分到最后若厚，每棵子樹只有一個節(jié)點拦英，根節(jié)點。然后從底部到頂部测秸，從左子樹到右子樹到根節(jié)點疤估，重復(fù)的回溯，知道根節(jié)點A霎冯，結(jié)果就出來了铃拇。
6.從上面的分析來看源碼， 先尋找最左子節(jié)點沈撞，然后判斷特殊情況慷荔， 如果visitCount = 1時跟（如B）， 切換到右子樹（E）缠俺。 之后就是重復(fù)上面的過程显晶，以右子樹的根節(jié)點作為根節(jié)點贷岸， 再尋找最左子節(jié)點。因為棧的后進先出特性吧碾，右子樹的所有子樹遍歷完成后凰盔， B樹的根節(jié)點B第二次出棧， 訪問B倦春，B可以pop移出棧了户敬。然后指向B的父節(jié)點A， 然后繼續(xù)上面的過程睁本， 結(jié)束尿庐。
好了，后序遍歷解析的足夠詳細了呢堰，如果還不明白抄瑟，多看幾遍，慢慢就明白了（一定要邊看邊寫）枉疼。
最難的部分已經(jīng)過去了皮假，最后解析一下按層遍歷的實現(xiàn)。
按層級遍歷骂维，是從根節(jié)點A出發(fā)惹资， 不斷保存當前層的子節(jié)點，這樣一層一層的遍歷航闺，直到最后一層褪测。
上圖的樹，按層遍歷流程：
遍歷第一層A潦刃， 移除第一層A侮措， 保存A的子節(jié)點BC（第二層）
遍歷第二層BC,移除BC, 保存B和C的子節(jié)點 DEF
遍歷DEF, 結(jié)束
我們看上面的過程，是怎么遍歷的乖杠？ 遍歷第N層分扎， 移除第N層，然后保存N+1層胧洒。然后遍歷N+1層笆包， 以此類推... 如果仔細看，我們會發(fā)現(xiàn)一個規(guī)律略荡，那就是保存子節(jié)點時， 從按從左右到的順序歉胶，遍歷時汛兜，也是按該順序。 先進先出通今，我們想到了一個數(shù)據(jù)結(jié)構(gòu)粥谬， 隊列Queue
public static void travelLevel(TreeNode root) {
if (root == null) return;
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
final TreeNode node = queue.poll();
if (node != null) {
System.out.println(node.data);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
}
層序遍歷很簡單肛根，那么簡單的來解釋一下代碼。
A入隊列漏策， 此時隊列中是A, 第一層
開始
A出隊列派哲， 這時隊列為空；加入A的子節(jié)點BC, 這是第二層掺喻，此時隊列是BC
B出隊列芭届， 這時隊列為C； 加入B的子節(jié)點DE;隊列中有CDE, C為第二層的感耙， DE為第三層褂乍。因為C排在隊列首位，因此下一次出隊列必然是C, C出棧后第二層就遍歷完成了即硼。
C出隊列逃片，此時隊列是DE; 第二層遍歷完畢。 然后加入F只酥， 此時隊列是DEF, 全是第三層的節(jié)點褥实。
D出隊列， D沒有左右孩子裂允； E出隊列损离，E也沒有左右孩子； F出隊列叫胖， F也沒有左右孩子草冈。
遍歷完畢。
再看我們的遍歷順序
A 第一層
B C 第二層
D E F 第三層
這就是按層的遍歷瓮增，每一層是上一層所有節(jié)點的所有子節(jié)點怎棱。
好了，到這里二叉樹的遍歷就全部結(jié)束了绷跑。你還有疑問嗎拳恋？ 如果還不明白，多看幾遍砸捏；然后還不明白谬运， OK，可以留言給我垦藏。
下一篇的內(nèi)容將是二叉搜索樹梆暖，又稱二叉排序樹， 二叉查找樹掂骏，這是一種很重要的數(shù)據(jù)結(jié)構(gòu)轰驳，二分法的由來便是從這種數(shù)據(jù)結(jié)構(gòu)衍生而來了。
