二叉樹前序，中序，后序遍歷的迭代實作，實作思路及代碼

用Java描述資料結構之二叉樹，前序遍歷，中序遍歷，后序遍歷這篇博客中我介紹了二叉樹的相關概念和遞回實作的二叉樹的前中后序遍歷，今天來介紹非遞回迭代版遍歷的思路及實作代碼，
首先我們要明白所謂遍歷就是集合中每個節點都要經過，就下面這棵樹而言，我們從根節點開始要怎么走才能經過每個節點？

下面是上圖樹的構建代碼：

public static TreeNode buildTree() {
        // 博客中所用到的樹的構建
        TreeNode a = new TreeNode('a');
        TreeNode b = new TreeNode('b');
        TreeNode c = new TreeNode('c');
        TreeNode d = new TreeNode('d');
        TreeNode e = new TreeNode('e');
        TreeNode f = new TreeNode('f');
        TreeNode g = new TreeNode('g');
        TreeNode h = new TreeNode('h');

        a.left = b; a.right = c;
        b.left = d; b.right = e;
        c.left = f; c.right = g;
        e.right = h;

        return a;
    }

很明顯我們要從根節點出發，左右都可以走，一般我們習慣往左走，我們一路向左走，直到走到沒路可走，即cur == null，用代碼實作這個是這樣的：

//root為根節點
Treenode cur = root;

while(cur != null){
	cur = cur.left;
}

直到我們走到空之后，下一步該怎么辦？

每個節點都有左右兩個方向可走，我們選擇一路向左，走到頭之后我們應該退一步，然后向右走，然后再向左走，再走到盡頭，往回走，向右走一步，，，，，，，就這樣去探路，拿例子來演示如下：

從A出發向左走，到盡頭之后退一步到B往B的右邊走一步到E，繼續向左走，走到頭之后退一步到E，再向右走到H，繼續向左走，走到盡頭之后退一步，，，，，，
我們把上述程序中的退一步稱為回溯，想要實作回溯我們就必須從剛開始向左走的程序中記錄經過的每個節點，而這個回溯很明顯具有后入先出的特性，這讓我們想到用堆疊去記錄（遞回版遍歷實際也是通過堆疊回溯，不過是java虛擬機堆疊，每一個堆疊幀都是以此方法的呼叫）每走到盡頭之后回溯一個節點，然后往這個節點的右邊走，就這樣直到堆疊空了，也就遍歷完了，代碼實作如下：

		TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        //第一次進入時stack為空，但是cur != null 
        //所以 cur != null 是為第一次能進入回圈專門設定的條件
        //當stack為空時結束回圈 
        while (cur != null || !stack.isEmpty()){
            while (cur != null){
            	//入堆疊每個經過的節點，向左走到盡頭時回溯
                stack.push(cur);
                //向左走
         		cur = cur.left;
            }
            //回溯
            TreeNode pop = stack.pop();
            //向右走
            cur = pop.right;
        }

現在我們來說明前序遍歷和中序遍歷（后序遍歷有點不同后面細說）：
每個節點都會經過第一次經過然后向左走，回溯回來經過第二遍然后向右走，向右走完還會回來經過第三遍像下圖：

我們吧第一次經過處理節點稱為先序遍歷或者前序遍歷，第二次經過時處理稱為中序遍歷，第三次經過時處理稱為后序遍歷，
因為前序遍歷是在第一次經過時處理，體現在代碼中就是：
先序遍歷代碼：

//先序遍歷
public static void preorder(TreeNode root){
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);
                System.out.print((char)cur.val + " ");
                cur = cur.left;
            }
            cur = stack.pop().right;
        }
    }

那么中序遍歷就是第二次經過也就是左走到盡頭回溯的時候處理節點

//中序遍歷
 public static void inorder(TreeNode root){
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode pop = stack.pop();
            System.out.print((char)pop.val + " ");
            cur = pop.right;
        }
    }

理解了先序和中序遍歷之后再來看后序遍歷！！！

剩下就是后續遍歷了，為什么說后序遍歷相對前兩種要麻煩一點呢，
我們來一步一步執行一下前序遍歷：

1. cur指向root，入堆疊
   

2. 向左走，走到B，入堆疊
   

3. 向左走到D，入堆疊
   

4. 再向左走，走到 cur == null 了，回溯一個節點，并向右走，執行下面代碼：

			TreeNode pop = stack.pop();
            cur = pop.right;

此時堆疊中是這樣的

走到這里還沒有發現問題，后續遍歷第一個節點也恰巧是D，繼續走

5. 因為D的右邊還是 null，所以需要繼續回溯，繼續執行那段代碼：

			TreeNode pop = stack.pop();
            cur = pop.right;

這次從堆疊中出來的的B節點，但是后序遍歷第二個節點不應該是B，此時的cur指向了E，并且因為E != null,E入堆疊，此時堆疊中是這樣：

6. 向E的左邊走，發現E的左邊是空，那么就要執行回溯操作

			TreeNode pop = stack.pop();
            cur = pop.right;

E會出堆疊，堆疊中如下：

7. 因為E的右邊是H不為null，所以H入堆疊，此時堆疊中如下：

走到這里我們就可以停下來了，這棵樹的后序遍歷是：D H E B F G C A，但是上述的程序中，還沒到第三次經過節點很多節點像B E 節點都已經出堆疊了，H節點走完之后就直接回溯到A節點了，如果要后續遍歷，H節點完了應該先回到E， 回到B 再回到A才對，現在這個代碼在第二次經過的時候就已經讓節點出堆疊，所以這個代碼對于后序遍歷不適用，

所謂后序遍歷就是在第三次經過節點的時候才對節點進行相應的處理，也就是遍歷完右子樹回來的時候才做處理，所以現在的關鍵是怎么才能知道當前是從節點左邊回來還是從右邊回來的問題，

我們需要定義一個參考last指向上一個出堆疊的節點，然后在每次回溯的時候判斷last是不是該節點的右孩子，如果是右孩子則說明是從右邊回溯的，如果不是就是左邊回溯，左邊回溯不用出堆疊，右邊回溯才出堆疊，在出堆疊時執行列印，通過代碼理解：

public static void postorder(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        //專門用來記錄上一個出堆疊的節點
        TreeNode last = null;
        while (cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
			//這里用peek看last是否是右孩子
			//peek.right == null 是用來判斷當前節點有沒有右孩子
			//沒有右孩子就沒必要執行else里的代碼讓cur往右走了
			//就像D節點，在這里判斷了沒有右孩子就直接出堆疊了，沒必要在往其右走再回來
            TreeNode peek = stack.peek();
            if (peek.right == null || peek.right == last){
                System.out.print((char)peek.val + " ");
                last = peek;
                stack.pop();
            }else {
                cur = peek.right;
            }
        }
    }

下面通過執行代碼驗證三個遍歷：

public class Main {
    public static TreeNode buildTree() {
        
        TreeNode a = new TreeNode('a');
        TreeNode b = new TreeNode('b');
        TreeNode c = new TreeNode('c');
        TreeNode d = new TreeNode('d');
        TreeNode e = new TreeNode('e');
        TreeNode f = new TreeNode('f');
        TreeNode g = new TreeNode('g');
        TreeNode h = new TreeNode('h');

        a.left = b; a.right = c;
        b.left = d; b.right = e;
        c.left = f; c.right = g;
        e.right = h;

        return a;
    }
    public static void main(String[] args) {
        TreeNode root = buildTree();
        System.out.print("前序遍歷：");
        Preorder.preorder(root);
        System.out.println();
        System.out.print("中序遍歷：");
        Inorder.inorder(root);
        System.out.println();
        System.out.print("后序遍歷：");
        Postorder.postorder(root);
    }
}