二叉樹有多種遍歷方法娩梨，有層次遍歷、深度優(yōu)先遍歷览徒、廣度優(yōu)先遍歷等狈定。
本文只涉及二叉樹的先序、中序习蓬、后序的遞歸和非遞歸遍歷纽什。
涉及到的代碼都用Java編寫。
首先給出二叉樹節(jié)點(diǎn)類：
樹節(jié)點(diǎn)：
class TreeNode {
int val;
//左子樹
TreeNode left;
//右子樹
TreeNode right;
//構(gòu)造方法
TreeNode(int x) {
val = x;
}
}
無論是哪種遍歷方法躲叼，考查節(jié)點(diǎn)的順序都是一樣的(思考做試卷的時候芦缰，人工遍歷考查順序)。只不過有時候考查了節(jié)點(diǎn)枫慷，將其暫存让蕾，需要之后的過程中輸出浪规。
如圖1所示笋婿，三種遍歷方法(人工)得到的結(jié)果分別是：
先序：1 2 4 6 7 8 3 5
中序：4 7 6 8 2 1 3 5
后序：7 8 6 4 2 5 3 1
三種遍歷方法的考查順序一致，得到的結(jié)果卻不一樣顿颅，原因在于：
先序：考察到一個節(jié)點(diǎn)后缸濒，即刻輸出該節(jié)點(diǎn)的值，并繼續(xù)遍歷其左右子樹粱腻。(根左右)
中序：考察到一個節(jié)點(diǎn)后庇配，將其暫存，遍歷完左子樹后栖疑，再輸出該節(jié)點(diǎn)的值讨永，然后遍歷右子樹滔驶。(左根右)
后序：考察到一個節(jié)點(diǎn)后遇革，將其暫存，遍歷完左右子樹后揭糕，再輸出該節(jié)點(diǎn)的值萝快。(左右根)
先序遍歷
遞歸先序遍歷
遞歸先序遍歷很容易理解，先輸出節(jié)點(diǎn)的值著角，再遞歸遍歷左右子樹揪漩。中序和后序的遞歸類似，改變根節(jié)點(diǎn)輸出位置即可吏口。
// 遞歸先序遍歷
public static void recursionPreorderTraversal(TreeNode root) {
if (root != null) {
System.out.print(root.val + " ");
recursionPreorderTraversal(root.left);
recursionPreorderTraversal(root.right);
}
}
非遞歸先序遍歷
因?yàn)橐诒闅v完節(jié)點(diǎn)的左子樹后接著遍歷節(jié)點(diǎn)的右子樹奄容，為了能找到該節(jié)點(diǎn)，需要使用棧來進(jìn)行暫存产徊。中序和后序也都涉及到回溯昂勒，所以都需要用到棧。
遍歷過程參考注釋
// 非遞歸先序遍歷
public static void preorderTraversal(TreeNode root) {
// 用來暫存節(jié)點(diǎn)的棧
Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
// 新建一個游標(biāo)節(jié)點(diǎn)為根節(jié)點(diǎn)
TreeNode node = root;
// 當(dāng)遍歷到最后一個節(jié)點(diǎn)的時候舟铜，無論它的左右子樹都為空戈盈，并且棧也為空
// 所以，只要不同時滿足這兩點(diǎn)谆刨，都需要進(jìn)入循環(huán)
while (node != null || !treeNodeStack.isEmpty()) {
// 若當(dāng)前考查節(jié)點(diǎn)非空塘娶，則輸出該節(jié)點(diǎn)的值
// 由考查順序得知，需要一直往左走
while (node != null) {
System.out.print(node.val + " ");
// 為了之后能找到該節(jié)點(diǎn)的右子樹痊夭，暫存該節(jié)點(diǎn)
treeNodeStack.push(node);
node = node.left;
}
// 一直到左子樹為空刁岸，則開始考慮右子樹
// 如果棧已空，就不需要再考慮
// 彈出棧頂元素她我，將游標(biāo)等于該節(jié)點(diǎn)的右子樹
if (!treeNodeStack.isEmpty()) {
node = treeNodeStack.pop();
node = node.right;
}
}
}
先序遍歷結(jié)果：
遞歸先序遍歷： 1 2 4 6 7 8 3 5
非遞歸先序遍歷：1 2 4 6 7 8 3 5
中序遍歷
遞歸中序遍歷
過程和遞歸先序遍歷類似
// 遞歸中序遍歷
public static void recursionMiddleorderTraversal(TreeNode root) {
if (root != null) {
recursionMiddleorderTraversal(root.left);
System.out.print(root.val + " ");
recursionMiddleorderTraversal(root.right);
}
}
非遞歸中序遍歷
和非遞歸先序遍歷類似虹曙，唯一區(qū)別是考查到當(dāng)前節(jié)點(diǎn)時膝宁，并不直接輸出該節(jié)點(diǎn)。
而是當(dāng)考查節(jié)點(diǎn)為空時根吁，從棧中彈出的時候再進(jìn)行輸出(永遠(yuǎn)先考慮左子樹员淫，直到左子樹為空才訪問根節(jié)點(diǎn))。
// 非遞歸中序遍歷
public static void middleorderTraversal(TreeNode root) {
Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
TreeNode node = root;
while (node != null || !treeNodeStack.isEmpty()) {
while (node != null) {
treeNodeStack.push(node);
node = node.left;
}
if (!treeNodeStack.isEmpty()) {
node = treeNodeStack.pop();
System.out.print(node.val + " ");
node = node.right;
}
}
}
中序遍歷結(jié)果
遞歸中序遍歷： 4 7 6 8 2 1 3 5
非遞歸中序遍歷：4 7 6 8 2 1 3 5
后序遍歷
遞歸后序遍歷
過程和遞歸先序遍歷類似
// 遞歸后序遍歷
public static void recursionPostorderTraversal(TreeNode root) {
if (root != null) {
recursionPostorderTraversal(root.left);
recursionPostorderTraversal(root.right);
System.out.print(root.val + " ");
}
}
非遞歸后序遍歷
后續(xù)遍歷和先序击敌、中序遍歷不太一樣介返。
后序遍歷在決定是否可以輸出當(dāng)前節(jié)點(diǎn)的值的時候，需要考慮其左右子樹是否都已經(jīng)遍歷完成沃斤。
所以需要設(shè)置一個lastVisit游標(biāo)圣蝎。
若lastVisit等于當(dāng)前考查節(jié)點(diǎn)的右子樹，表示該節(jié)點(diǎn)的左右子樹都已經(jīng)遍歷完成衡瓶，則可以輸出當(dāng)前節(jié)點(diǎn)徘公。
并把lastVisit節(jié)點(diǎn)設(shè)置成當(dāng)前節(jié)點(diǎn)，將當(dāng)前游標(biāo)節(jié)點(diǎn)node設(shè)置為空哮针，下一輪就可以訪問棧頂元素关面。
否者，需要接著考慮右子樹十厢，node = node.right等太。
以下考慮后序遍歷中的三種情況：
如圖3所示缩抡，從節(jié)點(diǎn)1開始考查直到節(jié)點(diǎn)4的左子樹為空。
注：此時的游標(biāo)節(jié)點(diǎn)node = 4.left == null包颁。
此時需要從棧中查看 Peek()棧頂元素瞻想。
發(fā)現(xiàn)節(jié)點(diǎn)4的右子樹非空，需要接著考查右子樹娩嚼，4不能輸出蘑险，node = node.right。
如圖4所示，考查到節(jié)點(diǎn)7(7.left == null竿音，7是從棧中彈出)和屎，其左右子樹都為空，可以直接輸出7春瞬。
此時需要把lastVisit設(shè)置成節(jié)點(diǎn)7柴信，并把游標(biāo)節(jié)點(diǎn)node設(shè)置成null，下一輪循環(huán)的時候會考查棧中的節(jié)點(diǎn)6宽气。
如圖5所示，考查完節(jié)點(diǎn)8之后(lastVisit == 節(jié)點(diǎn)8)绪氛，將游標(biāo)節(jié)點(diǎn)node賦值為棧頂元素6唆鸡，節(jié)點(diǎn)6的右子樹正好等于節(jié)點(diǎn)8。表示節(jié)點(diǎn)6的左右子樹都已經(jīng)遍歷完成枣察，直接輸出6争占。
此時，可以將節(jié)點(diǎn)直接從棧中彈出Pop()序目，之前用的只是Peek()臂痕。
將游標(biāo)節(jié)點(diǎn)node設(shè)置成null。
// 非遞歸后序遍歷
public static void postorderTraversal(TreeNode root) {
Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
TreeNode node = root;
TreeNode lastVisit = root;
while (node != null || !treeNodeStack.isEmpty()) {
while (node != null) {
treeNodeStack.push(node);
node = node.left;
}
//查看當(dāng)前棧頂元素
node = treeNodeStack.peek();
//如果其右子樹也為空猿涨，或者右子樹已經(jīng)訪問
//則可以直接輸出當(dāng)前節(jié)點(diǎn)的值
if (node.right == null || node.right == lastVisit) {
System.out.print(node.val + " ");
treeNodeStack.pop();
lastVisit = node;
node = null;
} else {
//否則握童，繼續(xù)遍歷右子樹
node = node.right;
}
}
}
后序遍歷結(jié)果
遞歸后序遍歷： 7 8 6 4 2 5 3 1
非遞歸后序遍歷：7 8 6 4 2 5 3 1
有任何錯誤請指正，謝謝叛赚！
寫文字不容易澡绩，且寫且珍惜！
