二叉樹的三種常用遍歷方式

???? 學(xué)習(xí)過數(shù)據(jù)結(jié)構(gòu)的同學(xué)都清楚，除了層序遍歷外，二叉樹主要有三種遍歷方式：
???????? 1. 先序遍歷
???????? 2. 中序遍歷
???????? 3. 后序遍歷
???? 關(guān)于這三種遍歷方式，我不做贅述，** 網(wǎng)上或者書本上，大家可以去了解一下方庭。 ** 這次我們主要總結(jié)一下二叉樹遍歷的算法的遞歸實現(xiàn)和非遞歸實現(xiàn)厕吉。而重點又落在非遞歸實現(xiàn)上，因為械念，遞歸實現(xiàn)头朱，其實也是書本上的基礎(chǔ)知識，只要去查閱機會有所理解龄减。

遞歸實現(xiàn)

先序遍歷的遞歸實現(xiàn)

???? 我們先定義一個二叉樹的節(jié)點結(jié)構(gòu)作為本博文中的通用節(jié)點项钮。

public class Node{
    public int value;
    public Node left;
    public Node right;
    
    public Node(int data){
        this.value = data;
    }
}

???? 我們知道，二叉樹的遞歸遍歷無非是對一顆非空的二叉樹的每一個節(jié)點希停，做相同的操作(先序烁巫、中序、后序)宠能。二叉樹的先序遍歷就是對每一個節(jié)點來先序遍歷的動作亚隙。代碼如下：

public void preOrder(Node head){
    if(head == null)return;
    
    System.out.print(head.value + " ");
    preOrder(head.left);
    preOrder(head.right);
}

中序遍歷的遞歸實現(xiàn)

???? 同樣的，二叉樹中序遍歷的遞歸實現(xiàn)棍潘，也是建立在同樣的思想上恃鞋。

public void midOrder(Node head){
    if(head == null)return;
    
    midOrder(head.left);
    System.out.print(head.value);
    midOrder(head.right);
}

后序遍歷的遞歸實現(xiàn)

???? ** The same idea , not the same recipe. **

public void posOrder(Node head){
    if(head == null)return;
    
    posOrder(head.left);
    posOrder(head.right);
    System.out.print(head.value);
}

關(guān)于遞歸實現(xiàn)的簡單總結(jié)

???? 從上面的代碼，我們發(fā)現(xiàn)亦歉，在遞歸實現(xiàn)上恤浪，三種遍歷方式的主要區(qū)別就是輸出當(dāng)前頭結(jié)點的值的時機，從而讓遍歷的順序產(chǎn)生區(qū)別肴楷。

非遞歸實現(xiàn)

用遞歸方法解決的問題都可以用非遞歸來實現(xiàn)水由，因為遞歸方法無非是實用函數(shù)棧來保存信息，如果用自己定義的棧來代替函數(shù)棧赛蔫，就可以實現(xiàn)相同的功能砂客。

先序遍歷的非遞歸實現(xiàn)

???? 先來大致分析一下非遞歸方式實現(xiàn)先序遍歷的具體過程：
???????? 1. 申請一個新的stack,然后把頭結(jié)點打入stack中
???????? 2. 從stack中彈出棧頂節(jié)點，記為 head 呵恢，然后打印 head 的值鞠值，然后 ** 把 head 的右孩子壓入棧中，再把 head 的左孩子壓入棧中(注意先后順序)渗钉。 ** 當(dāng)然在做這些操作之前彤恶，都需要一個 ** 非空判斷. ** 。
???????? 3. 重復(fù)步驟2鳄橘，直到 stack 為空声离。

???? 到這里，我們貼上一段代碼：

public void preOrderNoRecur(Node head){
    if(head != null){
    //新建一個椞绷空間术徊，存儲節(jié)點，對應(yīng)過程中的第一步
        Stack<Node> stack = new Stack<Node>();
        //把頭結(jié)點壓入棧中
        stack.add(head);
        while(! stack.isEmpty()){
            head = stack.pop();
            System.out.print(head.value + " ");
            //分別對彈出節(jié)點的右孩子鲸湃、左孩子判空赠涮，按照順序壓入棧中
            if(head.right != null)stack.add(head.right);
            if(head.left != null)stack.add(head.left)
        }
    }
}

** 需要重點理解的就是彈出節(jié)點的左右孩子被壓入棧的時機枝冀。 **建議大家自行畫一個圖推溃，模擬一下程序運行的過程区宇。

中序遍歷的非遞歸實現(xiàn)

???? 同樣的变汪，我們先分析一下中序遍歷非遞歸實現(xiàn)的具體過程：
???????? 1. 申請一個新的 stack 潮孽。** 跟先序遍歷不同的是 ** 相叁，我們需要兩個值凑保，一個cur计技，記錄當(dāng)前遍歷到的節(jié)點的值晒衩，一個head嗤瞎，記錄當(dāng)前二叉樹的根節(jié)點。** 初始時听系，cur = head ** 贝奇。
???????? 2. 把cur代表的節(jié)點壓入棧中，讓cur = cur.left
???????? 3. 重復(fù)步驟2靠胜，直到 cur 為空時掉瞳，從 stack 中彈出一個節(jié)點，記為 outNode ,打印 outNode 的值浪漠。然后讓 cur = outNode.right陕习，繼續(xù)重復(fù)步驟2。
???????? 4. 當(dāng) stack 為空且 cur 為空時址愿，整個遍歷完成该镣。閑話不多說，上代碼响谓。

public void midOrderNoRecur(Node head){
    if(head != null){
        Stack<Node> stack = new Stack<Node>();
        Node cur = head;
        while(!stack.isEmpty() || cur != null){
            if(cur != null){
            //步驟二损合，不停的把以 cur 的左孩子壓入棧中
                stack.push(head);
                cur = cur.left;
            }else{
            //當(dāng) cur 為空時，我們彈出棧頂元素娘纷，然后對其右孩子做相同的事
                Node outNode = stack.pop();
                System.out.print(outNode.value + " ");
                cur = outNode.right;
            }
        }
    }
}

???? ** 實際上, ** 我們可以把這段程序中的 cur , outNode都替換成head嫁审，這樣做可以節(jié)約空間，但是在代碼清晰度上個人覺得會有所降低赖晶。因為是用來總結(jié)律适，所以覺得還是把各個東西寫清晰的好。但是也附上都替換成 head 后的代碼嬉探。

public void midOrderNoRecur(Node head){
    if(head != null){
        Stack<Node> stack = new Stack<Node>();
        while(!stack.isEmpty() || head != null){
            if(head != null){
            //步驟二擦耀，不停的把以 head 的左孩子壓入棧中
                stack.push(head);
                head = head.left;
            }else{
            //當(dāng) head 為空時，我們彈出棧頂元素涩堤，然后對其右孩子做相同的事
                head = stack.pop();
                System.out.print(head.value + " ");
                head = head.right;
            }
        }
    }
}

???? 此處預(yù)留一個位置眷蜓，今天實在太晚了，困的不行胎围，接下面的明天繼續(xù)更吁系。Good Night.
???? 更新......

后序遍歷的非遞歸實現(xiàn)

???? 關(guān)于二叉樹后序遍歷的非遞歸實現(xiàn)德召，我學(xué)習(xí)了兩種方式。一種是利用兩個棧汽纤，另一種是利用一個棧上岗。

兩個棧實現(xiàn)后序遍歷

???? 依然從具體步驟開始：
???????? 1. 申請兩個 stack，分別記為 s1,s2 蕴坪，然后將頭結(jié)點壓入 s1 中
???????? 2. 從 s1 中彈出一個節(jié)點肴掷，記為 cur ，然后 cur 的左孩子和右孩子按順序壓入棧中
???????? 3. 把 cur 壓入 s2 中
???????? 4. 不斷重復(fù)第二步背传、第三步呆瞻、一直到 s1 為空時停止
???????? 5. 從 s2 中依次彈出節(jié)點并打印值

public void posOrderNoRecur(Node head){
    if(head != null){
    //申請兩個棧空間
        Stack<Node> s1 = new Stack<Node>();
        Stack<Node> s2 = new Stack<Node>();
        //把頭結(jié)點壓入棧s1中
        s1.push(head);
        while(!s1.isEmpty()){
        //從s1中彈出一個節(jié)點径玖，并且分別對其左右孩子判空痴脾，壓入s1
            Node cur = head.pop();
            //把彈出的節(jié)點壓入s2
            s2.push(cur);
            if(cur.left != null) s1.push(cur.left);
            if(cur.right != null) s2.push(cur.right);
        }
        
        while(!s2.isEmpty())
            System.out.print(s2.pop().value + " ");
    }
}

** 以上，我們便利用兩個棧完成了二叉樹后序遍歷的非遞歸實現(xiàn)梳星，思想上很簡單赞赖，就是對每個節(jié)點做一次先序遍歷，然后再按照右孩子冤灾，左孩子的順序壓入 s2 中前域，因為我們知道棧的特性之一就是先進后出，按照前面所說的順序把節(jié)點壓入棧中瞳购，再遍歷時就會得到一個正確的后序遍歷话侄。同樣建議大家自己在稿紙上畫圖，模擬過程学赛，幫助理解年堆。 **

一個棧實現(xiàn)后序遍歷

** 明天繼續(xù)... **

???? 用一個棧來實現(xiàn)二叉樹的后序遍歷，多少會有一些麻煩盏浇，我決定采用先貼出代碼的方式变丧。

public void posOrderNoRecur(Node h){
    if(h != null){
        Stack<Node> stack = new Stack<Node>();
        stack.push(h);
        Node c = null;
        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;
            }
        }
    }
}

???? 然后再來說代碼的實現(xiàn)思路，主要是遵從這樣的步驟：
???????? 1. 首先绢掰，依然是申請一個棧痒蓬，記為 stack , 并且設(shè)置兩個變量 h 和 c。在整個過程中滴劲，h 代表最近一次彈出并打印的節(jié)點攻晒，c 代表棧頂節(jié)點，初始情況： h 為 head 班挖， c 為 null鲁捏。
???????? 2. 這個時候(h 為最新彈出節(jié)點，c 為棧頂節(jié)點< ** 并沒有彈出 ** >)有三種情況：
???????????? * 如果 c 的左孩子不為空萧芙，且 h 不是 c 的左孩子也不是 c 的右孩子给梅，那么就把 c 的左孩子壓入棧中假丧。
???????????? * 如果 c 的又孩子不為空，且 h 不是 c 的右孩子动羽，那我們就把 c 的右孩子壓入棧中包帚。
???????????? * 如果上述兩種情況都不滿足，說明 c 的左子樹和右子樹都已經(jīng)打印完畢运吓，然后讓 h = c.
???????????? * 結(jié)束條件： 棧 stack 為空

???? 接下來我們解釋上述步驟的邏輯渴邦，首先，我們剛開始的時候把 h 代表的頭結(jié)點壓入 stack 中拘哨，此時几莽，棧頂節(jié)點即為樹的根，我們另 c = stack.peek()宅静，這個時候，按照我們對后序遍歷的理解站欺，我們應(yīng)該先遍歷頭結(jié)點的左子樹姨夹，如果 c 的 ** 左孩子不為空 ** 的話，這個時候我們的 h 肯定不等于 c 的左孩子/右孩子矾策，因為我們并沒有把左孩子/右孩子壓入棧中磷账，所以我們把 c 的左孩子壓入棧中，而之所以判斷一下 h 所代表的剛彈出的節(jié)點是否為 c 的左孩子/右孩子贾虽，是因為我們要判斷 c 的左右孩子是否有遍歷逃糟。如果有遍歷，那我們自然可以判斷蓬豁， c 的左右孩子已經(jīng)遍歷過绰咽，彈出 c 節(jié)點打印值，然后進入下一次循環(huán)即可地粪。同理的取募，當(dāng) c 的左孩子為空，右孩子不為空時蟆技，我們自然要判斷剛彈出的是否是 c 的右孩子玩敏，然后判斷把 c 的右孩子壓入棧中。
???? 我們講了很多關(guān)于壓入棧的操作质礼，但是我們什么時候輸出呢旺聚，也就是什么時候得到 h 的值呢。最后一個 else 包含的情況有哪些呢眶蕉。很明顯砰粹，就是遍歷到葉子節(jié)點的時候。當(dāng)我們碰到棧頂節(jié)點是葉子節(jié)點的時候妻坝，就會產(chǎn)生彈出伸眶。

總結(jié)

???? 本文主要講了二叉樹非尘眩基礎(chǔ)的三種遍歷方式： 先序遍歷、中序遍歷厘贼、后序遍歷界酒。在實現(xiàn)方式上，我們主要區(qū)分遞歸的實現(xiàn)方式和非遞歸的實現(xiàn)方式嘴秸。遞歸的方式是書本上的內(nèi)容毁欣，非遞歸方式的話，其實都很好理解岳掐，主要應(yīng)該注意的就是壓入棧的時機凭疮，左右孩子壓入棧的順序。這些順序的判斷和分析串述，都是建立在先/中/后序遍歷的特點上的执解。只要清楚所應(yīng)該遵循的規(guī)則，相信就可以寫出正確的程序纲酗。

???? Ps: 花了四天才寫完這篇博客衰腌。第一天太晚，第二天感冒觅赊，第三天出去浪了右蕊。是時候提高一波執(zhí)行力了。
???? ** 博客地址 :** 博客