提示:由于本人沒有精力做那么多流程圖渣蜗，建議你看的時(shí)候自己在紙上畫一畫屠尊，模擬一下順序般堆，不然很難理解邑退。
1.先序遍歷
思路：
（1）用一個(gè)棧保存二叉樹的節(jié)點(diǎn)疫铜，從根節(jié)點(diǎn)開始达箍。
（2）先壓入根節(jié)點(diǎn)邪狞，打印，然后找右孩子害幅，存在就壓入棧元旬，不存在就壓入左孩子。
（3）棧非空既峡，且既沒有右孩子也沒有左孩子的時(shí)候羡榴，彈出棧頂元素并打印，繼續(xù)第2步运敢。
由于操作的順序是：先讓父結(jié)點(diǎn)出棧并打印校仑，然后壓右，再壓左传惠。出棧順序就正好相反迄沫，先彈左，后彈右卦方，實(shí)現(xiàn)了先序遍歷羊瘩。
public static void preOrderUnRecur(Node head) {
System.out.print("先序遍歷: ");
if (head != null) {
Stack<Node> stack = new Stack<>();
stack.add(head);
while (!stack.isEmpty()) {
head = stack.pop();
System.out.print(head.value + " ");
if (head.right != null)
stack.push(head.right);
if (head.left != null)
stack.push(head.left);
}
}
System.out.println();
}
2.中序遍歷：
思路：
（1）當(dāng)前節(jié)點(diǎn)先把自己的左邊界（所有的左孩子節(jié)點(diǎn)）都壓到棧里。
（2）由于一直重復(fù)head = head.left盼砍，肯定會有一個(gè)時(shí)刻尘吗，head.left為空，當(dāng)節(jié)點(diǎn)為空的時(shí)候衬廷，開始彈棧摇予。
具體操作是：從棧中拿出棧頂元素并打印，然后當(dāng)前節(jié)點(diǎn)向右孩子移動吗跋。
（3）重復(fù)前兩步侧戴，當(dāng)棧為空且節(jié)點(diǎn)也為空時(shí)，循環(huán)結(jié)束跌宛。
public static void inOrderUnRecur(Node head) {
System.out.print("中序遍歷: ");
if (head != null) {
Stack<Node> stack = new Stack<>();
while (!stack.isEmpty() || head != null) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
System.out.print(head.value + " ");
head = head.right;
}
}
}
System.out.println();
}
3.后序遍歷：
- 方法1 （使用兩個(gè)棧）
后序遍歷的順序是 左→右→中酗宋，要想壓到棧里再按這個(gè)順序彈出打印的話，壓棧的時(shí)候順序就應(yīng)該是 中→右→左疆拘。那么蜕猫，怎么實(shí)現(xiàn)呢？
我們前面寫第一個(gè)先序遍歷的時(shí)候哎迄，順序是中左右回右。稍微修改一下先序遍歷的代碼，讓那個(gè)棧彈出并打印中節(jié)點(diǎn)之后漱挚，先壓入右孩子翔烁，再壓入左孩子。這樣出棧順序就變成了中右左旨涝。
繼續(xù)修改蹬屹，彈棧時(shí)候棧頂元素不打印，而是壓入另一個(gè)輔助棧，原來那個(gè)棧的出棧打印順序（中右左）就變成了輔助棧的壓棧順序慨默。那么在輔助棧彈棧打印的時(shí)候贩耐，不就是左右中了嗎？
這個(gè)解釋起來比較晦澀厦取，自己拿張紙畫一下流程潮太，模擬出棧順序，你就會很明白蒜胖。
public static void posOrderUnRecur1(Node head) {
System.out.print("后序遍歷: ");
if (head != null) {
Stack<Node> s1 = new Stack<>();
Stack<Node> s2 = new Stack<>();
s1.push(head);
while (!s1.isEmpty()) {
head = s1.pop();
s2.push(head);
if (head.left != null)
s1.push(head.left);
if (head.right != null)
s1.push(head.right);
}
while (!s2.isEmpty()) {
System.out.print(s2.pop().value + " ");
}
}
System.out.println();
}
- 方法2
純粹炫技的做法消别，只用了一個(gè)棧，能看得懂就看台谢，看不懂也沒有關(guān)系寻狂。
public static void posOrderUnRecur2(Node h) {
System.out.print("后序遍歷: ");
if (h != null) {
Stack<Node> stack = new Stack<>();
stack.push(h);
Node c;
while (!stack.isEmpty()) {
c = stack.peek();
if (c.left != null && h != c.left && h != c.right) {
stack.push(c.left);
} else if (c.right != null && h != c.right) {
stack.push(c.right);
} else {
System.out.print(stack.pop().value + " ");
h = c;
}
}
}
System.out.println();
}
完整的代碼（包含了遞歸方式）：
import java.util.Stack;
public class PreInPosTraversal {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static void preOrderRecur(Node head) {
if (head == null) return;
System.out.print(head.value + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
public static void inOrderRecur(Node head) {
if (head == null) return;
inOrderRecur(head.left);
System.out.print(head.value + " ");
inOrderRecur(head.right);
}
public static void posOrderRecur(Node head) {
if (head == null) return;
posOrderRecur(head.left);
posOrderRecur(head.right);
System.out.print(head.value + " ");
}
public static void preOrderUnRecur(Node head) {
System.out.print("先序遍歷: ");
if (head != null) {
Stack<Node> stack = new Stack<>();
stack.add(head);
while (!stack.isEmpty()) {
head = stack.pop();
System.out.print(head.value + " ");
if (head.right != null)
stack.push(head.right);
if (head.left != null)
stack.push(head.left);
}
}
System.out.println();
}
public static void inOrderUnRecur(Node head) {
System.out.print("中序遍歷: ");
if (head != null) {
Stack<Node> stack = new Stack<>();
while (!stack.isEmpty() || head != null) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
System.out.print(head.value + " ");
head = head.right;
}
}
}
System.out.println();
}
public static void posOrderUnRecur1(Node head) {
System.out.print("后序遍歷: ");
if (head != null) {
Stack<Node> s1 = new Stack<>();
Stack<Node> s2 = new Stack<>();
s1.push(head);
while (!s1.isEmpty()) {
head = s1.pop();
s2.push(head);
if (head.left != null)
s1.push(head.left);
if (head.right != null)
s1.push(head.right);
}
while (!s2.isEmpty()) {
System.out.print(s2.pop().value + " ");
}
}
System.out.println();
}
public static void posOrderUnRecur2(Node h) {
System.out.print("后序遍歷: ");
if (h != null) {
Stack<Node> stack = new Stack<>();
stack.push(h);
Node c;
while (!stack.isEmpty()) {
c = stack.peek();
if (c.left != null && h != c.left && h != c.right) {
stack.push(c.left);
} else if (c.right != null && h != c.right) {
stack.push(c.right);
} else {
System.out.print(stack.pop().value + " ");
h = c;
}
}
}
System.out.println();
}
public static void main(String[] args) {
Node head = new Node(5);
head.left = new Node(3);
head.right = new Node(8);
head.left.left = new Node(2);
head.left.right = new Node(4);
head.left.left.left = new Node(1);
head.right.left = new Node(7);
head.right.left.left = new Node(6);
head.right.right = new Node(10);
head.right.right.left = new Node(9);
head.right.right.right = new Node(11);
// recursive
System.out.println("==============遞歸==============");
System.out.print("先序遍歷: ");
preOrderRecur(head);
System.out.println();
System.out.print("中序遍歷: ");
inOrderRecur(head);
System.out.println();
System.out.print("后序遍歷: ");
posOrderRecur(head);
System.out.println();
// unRecursive
System.out.println("============非遞歸=============");
preOrderUnRecur(head);
inOrderUnRecur(head);
posOrderUnRecur1(head);
posOrderUnRecur2(head);
}
}
