二叉樹的遍歷實現(xiàn)遞歸與非遞歸

本文實現(xiàn)了二叉樹的深度遍歷算法，分為遞歸與非遞歸

遞歸的實現(xiàn)非常簡單，基本上沒啥難度

非遞歸的實現(xiàn)需要根據(jù)遍歷的順序，將遞歸轉(zhuǎn)換成循環(huán)

代碼中的二叉樹如下

遍歷.png

遞歸

遞歸的實現(xiàn)很簡單，此處不做過多贅述

package cn.lillcol.agst.test;

/**
 * 定義 結(jié)點數(shù)據(jù)結(jié)構(gòu)
 */
public class Node {

    //    數(shù)據(jù)域
    String data = "null";
    //    左孩子
    Node leftChild;
    //    右孩子
    Node rightChild;
    //    是否被訪問
    boolean isVisit = false;

    public void setIsVisit(boolean isVisit) {
        this.isVisit = isVisit;
    }

    public boolean getisVisit() {
        return this.isVisit;
    }

    public Node(String data) {
        this.data = data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public void setLeftChild(Node leftChild) {
        this.leftChild = leftChild;
    }

    public void setRightChild(Node rightChild) {
        this.rightChild = rightChild;
    }

    @Override
    public String toString() {
        return this.data;
    }
}


package cn.lillcol.agst.test;

/**
 * 二叉樹遍歷案例遞歸版本
 *
 * @author lillcol
 * @date 2020-01-16 23：56：51
 */
public class BTreeTestRecursion {
    public static void main(String[] args) {
        BTreeTestRecursion bTreeTestRecursion = new BTreeTestRecursion();
        Node bTree = bTreeTestRecursion.createBTree();
        System.out.print("前序遍歷：");
        bTreeTestRecursion.preOrderTraverse(bTree);
        System.out.print("\n中序遍歷：");
        bTreeTestRecursion.inOrderTraverse(bTree);
        System.out.print("\n后序遍歷：");
        bTreeTestRecursion.postOrderTraverse(bTree);
    }

    /**
     * 生成一棵樹
     *
     * @return
     */
    public Node createBTree() {
        Node A = new Node("A");
        Node B = new Node("B");
        Node C = new Node("C");
        Node D = new Node("D");
        Node E = new Node("E");
        Node F = new Node("F");
        Node G = new Node("G");
        Node H = new Node("H");
        Node I = new Node("I");
        A.setLeftChild(B);
        A.setRightChild(C);
        B.setLeftChild(D);
        C.setLeftChild(E);
        C.setRightChild(F);
        D.setLeftChild(G);
        D.setRightChild(H);
        E.setRightChild(I);
        return A;
    }

    /**
     * 前序遍歷遞歸版本
     *
     * @param t
     */
    public void preOrderTraverse(Node t) {
        if (t == null) return;
        System.out.print(t.data + "->");
        preOrderTraverse(t.leftChild);
        preOrderTraverse(t.rightChild);
    }

    /**
     * 中序遍歷 遞歸版本
     *
     * @param t
     */
    public void inOrderTraverse(Node t) {
        if (t == null) return;
        inOrderTraverse(t.leftChild);
        System.out.print(t.data + "->");
        inOrderTraverse(t.rightChild);
    }

    /**
     * 后續(xù)遍歷 遞歸版本
     *
     * @param t
     */
    public void postOrderTraverse(Node t) {
        if (t == null) return;
        postOrderTraverse(t.leftChild);
        postOrderTraverse(t.rightChild);
        System.out.print(t.data + "->");
    }

}

非遞歸

非遞歸的實現(xiàn)比起遞歸相對復(fù)雜些。

核心是利用棧的特性，記錄訪問過的結(jié)點或輸出的結(jié)點

非遞歸的實現(xiàn)中，先序遍歷、中序遍歷是比較簡單的，只要按照便利的順序結(jié)合代碼的注釋基本就可以理解了。

比較難的后續(xù)遍歷，在實現(xiàn)的過程中發(fā)現(xiàn)，如果要按照訪問順序來進(jìn)行實現(xiàn)，很復(fù)雜。

有些實現(xiàn)方式是通過增加一個標(biāo)志位標(biāo)記該借點是否訪問過，但是卻有問題：比如需要考慮很多子樹的情況，判斷情況特別多，只要少一個情況就會出錯。

后面查看資料還有一個實現(xiàn)的方式相對簡單很多，實現(xiàn)如下：
后序遍歷可以看作逆先序遍歷，此處有兩個關(guān)鍵：

  1. 結(jié)果是先序遍歷的逆序
  2. 此處的先序遍歷不是從左到右的先序遍歷，是從右到做的先序遍歷，具體如下圖
    原理.png

下面對比觀察一下結(jié)果：


對比.png
package cn.lillcol.agst.test;

import java.util.Stack;

/***
 * 二叉樹層次遍歷的非遞歸實現(xiàn)版本
 * @author lillcol 20200308
 */
public class BTreeTestNotRecursion {
    public static void main(String[] args) throws InterruptedException {
        BTreeTestNotRecursion bTreeTestNotRecursion = new BTreeTestNotRecursion();
        Node bTree = bTreeTestNotRecursion.createBTree();
        bTreeTestNotRecursion.inOrderTraverse(bTree);
        bTreeTestNotRecursion.preOrderTraverse(bTree);
        bTreeTestNotRecursion.postOrderTraverse(bTree);
    }

    /**
     * 前序遍歷 非遞歸版本
     *
     * @param t
     */
    public void preOrderTraverse(Node t) {
        if (t == null) return;
        Stack<Node> stack = new Stack<>();
//      此處出了t不為空，還需要棧也不為空，否則會停在第一次遍歷到右節(jié)點的位置
        while (t != null || !stack.empty()) {
//            遍歷到樹的最左邊節(jié)點
            while (t != null) {
                stack.push(t);//記錄遍歷過的節(jié)點
                System.out.print(t.data + "->");//先序遍歷，首先輸出父節(jié)點，所以此處需要輸出
                t = t.leftChild;//遍歷父節(jié)點后，下一個遍歷的節(jié)點為左節(jié)點
            }

            if (!stack.empty()) {
//                當(dāng)遍歷完左節(jié)點，需要遍歷右節(jié)點
                t = stack.pop().rightChild;
            }

        }
    }

    /**
     * 中序遍歷 非遞歸版本
     *
     * @param t
     */
    public void inOrderTraverse(Node t) {
        if (t == null) return;
        Stack<Node> stack = new Stack<>();
        //當(dāng)前節(jié)點不為空，或棧中有元素
        while (t != null || !stack.empty()) {
            //一直遍歷左子樹，直到某結(jié)點的左子樹為null，說明到了最下邊的左子樹
            while (t != null) {
                //將每一個便利的左子樹入棧
                stack.push(t);
                t = t.leftChild;
            }
            //當(dāng)遍歷到最下邊的左子樹，就需要開始出棧了
            if (!stack.empty()) {
                //棧頂元素出棧
                Node top = stack.pop();
                System.out.print(top.toString() + "->");
                //遍歷因為是中序遍歷，在輸出一個結(jié)點后，接下來判斷該結(jié)點的右子樹，這和之前一樣相當(dāng)于是一新的樹，重復(fù)之前的操作即可
                t = top.rightChild;
            }
        }
    }

    /**
     * 后續(xù)遍歷 非遞歸版本
     * 核心：后續(xù)遍歷就是 逆先序遍歷 （先序遍歷的順序為父->右結(jié)點->左結(jié)點：和一般的剛好相反）
     * 所以代碼實現(xiàn)需要兩個棧，一個進(jìn)行節(jié)點的先序遍歷，另一個記錄輸出內(nèi)容（因為是逆序，所以根據(jù)棧的特性，最后在遍歷stack2即是最終的后續(xù)遍歷結(jié)果）
     *
     * @param t
     */
    public void postOrderTraverse(Node t) {
        if (t == null) return;
        Stack<Node> stack = new Stack<>();
        Stack<Node> stack2 = new Stack<>();
        while (t != null || !stack.empty()) {
            while (t != null) {
                stack.push(t);//記錄已經(jīng)訪問結(jié)點
//                System.out.print(t.data + "->");正常先序遍歷該在此處輸出
                stack2.push(t);//記錄本該輸出的部分
                t = t.rightChild;
            }

            if (!stack.empty()) {
                t = stack.pop().leftChild;
            }

        }
//        輸出stack2中的記錄即為后續(xù)遍歷結(jié)果
        while (!stack2.empty()) {
            System.out.print(stack2.pop().data + "->");
        }
    }

    /**
     * 生成一棵樹
     *
     * @return
     */
    public Node createBTree() {
        Node A = new Node("A");
        Node B = new Node("B");
        Node C = new Node("C");
        Node D = new Node("D");
        Node E = new Node("E");
        Node F = new Node("F");
        Node G = new Node("G");
        Node H = new Node("H");
        Node I = new Node("I");
        A.setLeftChild(B);
        A.setRightChild(C);
        B.setLeftChild(D);
        C.setLeftChild(E);
        C.setRightChild(F);
        D.setLeftChild(G);
        D.setRightChild(H);
        E.setRightChild(I);
        return A;
    }
}

本文為原創(chuàng)文章，轉(zhuǎn)載請注明出處！?。?/p>

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容