面試算法--遞歸/循環(huán)實(shí)現(xiàn)二叉樹的前丶中丶后序遍歷

一丶利用二叉樹前序順序構(gòu)建二叉樹

"#" 代表空結(jié)點(diǎn)

/**
     * 
     *               A
     * 
     *          B           C
     * 
     *      D       E     #         F 
     * 
     *    #   #   #   #           #    #
     * 
     * 
     * A B D## E## C # F ## 利用前序遍歷快速反向創(chuàng)建二叉樹
     */
    public void createBinaryTreePre(ArrayList<String> data) {

        createBinaryTree(data);
    }

    private Node createBinaryTree(ArrayList<String> data) {

        if (0 == data.size()) {
            return null;
        }

        String d = data.get(0);

        if ("#".equals(d)) {
            data.remove(0);
            return null;
        }

        Node node = new Node(0, d);
        data.remove(0);

        if (null == root) {
            root = node;
        }

        node.leftChild = createBinaryTree(data);

        node.rightChild = createBinaryTree(data);

        return node;
    }

二丶遞歸實(shí)現(xiàn)二叉樹前中后序遍歷

/**
     * 遞歸方式實(shí)現(xiàn)前序遍歷
     */
    public void recursionPrerEgodic(Node node) {

        if (null == node) {
            return;
        }

        // 先輸出根節(jié)點(diǎn)
        System.out.println("數(shù)據(jù)：" + node.data);

        // 輸出左邊節(jié)點(diǎn) 根節(jié)點(diǎn)左邊的可以看成是一個(gè)子樹，遞歸調(diào)用此方法即可
        recursionPrerEgodic(node.leftChild);

        // 輸出右邊節(jié)點(diǎn)
        recursionPrerEgodic(node.rightChild);
    }

    /**
     * 遞歸方式實(shí)現(xiàn)中序遍歷
     */
    public void recursionMidEgodic(Node node) {

        if (null == node) {
            return;
        }

        // 先遞歸輸出左邊的節(jié)點(diǎn)
        recursionMidEgodic(node.leftChild);

        // 先輸出根節(jié)點(diǎn)
        System.out.println("數(shù)據(jù)：" + node.data);

        // 最后輸出右邊節(jié)點(diǎn)
        recursionMidEgodic(node.rightChild);
    }

        /**
     * 遞歸方式實(shí)現(xiàn)后序遍歷
     */
    public void recursionPostEgodic(Node node) {

        if (null == node) {
            return;
        }

        // 先遞歸輸出左邊的節(jié)點(diǎn)
        recursionPostEgodic(node.leftChild);

        // 最后輸出右邊節(jié)點(diǎn)
        recursionPostEgodic(node.rightChild);

        // 先輸出根節(jié)點(diǎn)
        System.out.println("數(shù)據(jù)：" + node.data);
    }

三丶循環(huán)實(shí)現(xiàn)二叉樹前中后序遍歷

/**
     * 循環(huán)方式實(shí)現(xiàn)前序遍歷 借助棧實(shí)現(xiàn)
     */
    public void loopPreEgodic(Node node) {

        if (null == node) {
            return;
        }

        // 借用棧實(shí)現(xiàn)
        Stack<Node> stack = new Stack<Node>();

        stack.push(node);

        while (!stack.isEmpty()) {

            // 從棧中取出數(shù)據(jù)。
            node = stack.pop();

            // 取出數(shù)據(jù)
            System.out.println("數(shù)據(jù)：" + node.data);

            // 因?yàn)槭歉?左 右 而棧是先進(jìn)后出，所以一定要先把右邊壓入棧中 再壓入左面，

            // 如果此節(jié)點(diǎn)左右節(jié)點(diǎn)不為null，將此節(jié)點(diǎn)的左右節(jié)點(diǎn)壓入棧中

            if (null != node.rightChild) {

                stack.push(node.rightChild);
            }

            if (null != node.leftChild) {

                stack.push(node.leftChild);
            }
        }
    }

    /**
     * 循環(huán)方式實(shí)現(xiàn)中序遍歷 借用棧實(shí)現(xiàn)
     */
    public void loopMidEgodic(Node node) {

        if (null == node) {
            return;
        }

        // 借用棧實(shí)現(xiàn)
        Stack<Node> stack = new Stack<Node>();

        while (!stack.isEmpty() || null != node) {

            // 先遍歷出所有左節(jié)點(diǎn)放入棧中,停止條件是node指針為null
            if (null != node) {

                stack.push(node);

                // node指針指向左節(jié)點(diǎn)
                node = node.leftChild;

            } else {

                // 此時(shí)取出棧中的數(shù)據(jù)
                node = stack.pop();

                System.out.println("數(shù)據(jù)：" + node.data);

                node = node.rightChild;
            }
        }
    }

    /**
     * 循環(huán)方式實(shí)現(xiàn)后序遍歷方法一 借用雙棧實(shí)現(xiàn)
     */
    public void loopPostEgodic_1(Node node) {

        if (null == node) {
            return;
        }

        // 借用雙棧實(shí)現(xiàn)
        Stack<Node> s1 = new Stack<Node>();
        Stack<Node> s2 = new Stack<Node>();

        s1.push(node);

        while (!s1.isEmpty()) {

            node = s1.pop();

            // 先不輸出，先將根節(jié)點(diǎn)壓入棧2，最后輸出
            s2.push(node);

            // 注意 以下代碼順序不能換
            // 放入棧1后 左在棧底 右 在棧頂，放入棧2后，左在棧頂，右在棧底 ，而根節(jié)點(diǎn)早就放在棧2底部了，
            if (null != node.leftChild) {

                s1.push(node.leftChild);
            }

            if (null != node.rightChild) {

                s1.push(node.rightChild);
            }
        }

        while (!s2.isEmpty()) {
            node = s2.pop();
            System.out.println("數(shù)據(jù):" + node.data);
        }
    }

    /**
     * 循環(huán)方式實(shí)現(xiàn)后序遍歷方法二
     */
    public void loopPostEgodic_2(Node node) {

        if (null == node) {

            return;
        }

        Stack<Node> stack = new Stack<Node>();

        stack.push(node);

        Node pre = null;

        while (!stack.isEmpty()) {

            pre = stack.peek();// 注意只取出不移除

            if (pre.leftChild != null && node != pre.leftChild && node != pre.rightChild) {

                stack.push(pre.leftChild);
            }

            else if (pre.rightChild != null && node != pre.rightChild) {

                stack.push(pre.rightChild);
            }

            else {
                node = stack.pop();
                System.out.println("數(shù)據(jù):" + node.data);
                node = pre;
            }
        }
    }

四丶完整代碼

public class WDBinaryTree {

    class Node {
        int index;
        String data;

        Node parent;
        Node leftChild;
        Node rightChild;

        public Node(int index, String data) {
            super();
            this.data = data;
            this.index = index;

            this.parent = null;
            this.leftChild = null;
            this.rightChild = null;
        }
    }

    Node root = null;

    /**
     * 
     *               A
     * 
     *          B           C
     * 
     *      D       E     #         F 
     * 
     *    #   #   #   #           #    #
     * 
     * 
     * A B D## E## C # F ## 利用前序遍歷快速反向創(chuàng)建二叉樹
     */
    public void createBinaryTreePre(ArrayList<String> data) {

        createBinaryTree(data);
    }

    private Node createBinaryTree(ArrayList<String> data) {

        if (0 == data.size()) {
            return null;
        }

        String d = data.get(0);

        if ("#".equals(d)) {
            data.remove(0);
            return null;
        }

        Node node = new Node(0, d);
        data.remove(0);

        if (null == root) {
            root = node;
        }

        node.leftChild = createBinaryTree(data);

        node.rightChild = createBinaryTree(data);

        return node;
    }

    /**
     * 獲取二叉樹的高度
     */
    public int getHeight(Node node) {

        if (null == node) {
            return 0;
        }

        int i = getHeight(node.leftChild);

        int j = getHeight(node.rightChild);

        return i > j ? (i + 1) : (j + 1);
    }

    /**
     * 獲取二叉樹的節(jié)點(diǎn)數(shù)
     */
    public int getNum(Node node) {

        if (null == node) {
            return 0;
        }

        return 1 + getNum(node.leftChild) + getNum(node.rightChild);
    }

    /**
     * 遞歸方式實(shí)現(xiàn)前序遍歷
     */
    public void recursionPrerEgodic(Node node) {

        if (null == node) {
            return;
        }

        // 先輸出根節(jié)點(diǎn)
        System.out.println("數(shù)據(jù)：" + node.data);

        // 輸出左邊節(jié)點(diǎn) 根節(jié)點(diǎn)左邊的可以看成是一個(gè)子樹，遞歸調(diào)用此方法即可
        recursionPrerEgodic(node.leftChild);

        // 輸出右邊節(jié)點(diǎn)
        recursionPrerEgodic(node.rightChild);
    }

    /**
     * 遞歸方式實(shí)現(xiàn)中序遍歷
     */
    public void recursionMidEgodic(Node node) {

        if (null == node) {
            return;
        }

        // 先遞歸輸出左邊的節(jié)點(diǎn)
        recursionMidEgodic(node.leftChild);

        // 先輸出根節(jié)點(diǎn)
        System.out.println("數(shù)據(jù)：" + node.data);

        // 最后輸出右邊節(jié)點(diǎn)
        recursionMidEgodic(node.rightChild);
    }

    /**
     * 遞歸方式實(shí)現(xiàn)后序遍歷
     */
    public void recursionPostEgodic(Node node) {

        if (null == node) {
            return;
        }

        // 先遞歸輸出左邊的節(jié)點(diǎn)
        recursionPostEgodic(node.leftChild);

        // 最后輸出右邊節(jié)點(diǎn)
        recursionPostEgodic(node.rightChild);

        // 先輸出根節(jié)點(diǎn)
        System.out.println("數(shù)據(jù)：" + node.data);
    }

    /**
     * 循環(huán)方式實(shí)現(xiàn)前序遍歷 借助棧實(shí)現(xiàn)
     */
    public void loopPreEgodic(Node node) {

        if (null == node) {
            return;
        }

        // 借用棧實(shí)現(xiàn)
        Stack<Node> stack = new Stack<Node>();

        stack.push(node);

        while (!stack.isEmpty()) {

            // 從棧中取出數(shù)據(jù)。
            node = stack.pop();

            // 取出數(shù)據(jù)
            System.out.println("數(shù)據(jù)：" + node.data);

            // 因?yàn)槭歉?左 右 而棧是先進(jìn)后出，所以一定要先把右邊壓入棧中 再壓入左面，

            // 如果此節(jié)點(diǎn)左右節(jié)點(diǎn)不為null，將此節(jié)點(diǎn)的左右節(jié)點(diǎn)壓入棧中

            if (null != node.rightChild) {

                stack.push(node.rightChild);
            }

            if (null != node.leftChild) {

                stack.push(node.leftChild);
            }
        }
    }

    /**
     * 循環(huán)方式實(shí)現(xiàn)中序遍歷 借用棧實(shí)現(xiàn)
     */
    public void loopMidEgodic(Node node) {

        if (null == node) {
            return;
        }

        // 借用棧實(shí)現(xiàn)
        Stack<Node> stack = new Stack<Node>();

        while (!stack.isEmpty() || null != node) {

            // 先遍歷出所有左節(jié)點(diǎn)放入棧中,停止條件是node指針為null
            if (null != node) {

                stack.push(node);

                // node指針指向左節(jié)點(diǎn)
                node = node.leftChild;

            } else {

                // 此時(shí)取出棧中的數(shù)據(jù)
                node = stack.pop();

                System.out.println("數(shù)據(jù)：" + node.data);

                node = node.rightChild;
            }
        }
    }

    /**
     * 循環(huán)方式實(shí)現(xiàn)后序遍歷方法一 借用雙棧實(shí)現(xiàn)
     */
    public void loopPostEgodic_1(Node node) {

        if (null == node) {
            return;
        }

        // 借用雙棧實(shí)現(xiàn)
        Stack<Node> s1 = new Stack<Node>();
        Stack<Node> s2 = new Stack<Node>();

        s1.push(node);

        while (!s1.isEmpty()) {

            node = s1.pop();

            // 先不輸出，先將根節(jié)點(diǎn)壓入棧2，最后輸出
            s2.push(node);

            // 注意 以下代碼順序不能換
            // 放入棧1后 左在棧底 右 在棧頂，放入棧2后，左在棧頂，右在棧底 ，而根節(jié)點(diǎn)早就放在棧2底部了，
            if (null != node.leftChild) {

                s1.push(node.leftChild);
            }

            if (null != node.rightChild) {

                s1.push(node.rightChild);
            }
        }

        while (!s2.isEmpty()) {
            node = s2.pop();
            System.out.println("數(shù)據(jù):" + node.data);
        }
    }

    /**
     * 循環(huán)方式實(shí)現(xiàn)后序遍歷方法二
     */
    public void loopPostEgodic_2(Node node) {

        if (null == node) {

            return;
        }

        Stack<Node> stack = new Stack<Node>();

        stack.push(node);

        Node pre = null;

        while (!stack.isEmpty()) {

            pre = stack.peek();// 注意只取出不移除

            if (pre.leftChild != null && node != pre.leftChild && node != pre.rightChild) {

                stack.push(pre.leftChild);
            }

            else if (pre.rightChild != null && node != pre.rightChild) {

                stack.push(pre.rightChild);
            }

            else {
                node = stack.pop();
                System.out.println("數(shù)據(jù):" + node.data);
                node = pre;
            }
        }
    }

    /**
     * 層序 利用隊(duì)列實(shí)現(xiàn)
     */
    public void levelEgodic(Node node) {

        if (null == node) {
            return;
        }

        Queue<Node> q = new LinkedList<Node>();
        q.add(node);

        while (!q.isEmpty()) {

            //源碼： Retrieves and removes the head of this queue,
            node = q.poll();// 取出并移除

            System.out.println("數(shù)據(jù)：" + node.data);

            if (null != node.leftChild) {
                q.add(node.leftChild);
            }
            if (null != node.rightChild) {
                q.add(node.rightChild);
            }
        }
    }

    public static void main(String[] args) {

        //二叉樹的前序遍歷順序，#代表空結(jié)點(diǎn)
        String[] data = { "A", "B", "D", "#", "#", "E", "#", "#", "C", "#", "F", "#", "#" };

        ArrayList<String> dataList = new ArrayList<String>();

        for (String s : data) {
            dataList.add(s);
        }

        //構(gòu)造二叉樹
        WDBinaryTree tree = new WDBinaryTree();
        tree.createBinaryTreePre(dataList);

        int i = tree.getHeight(tree.root);
        int num = tree.getNum(tree.root);

        System.out.println("二叉樹的高度為：" + i);
        System.out.println("二叉樹的節(jié)點(diǎn)數(shù)為：" + num);

        System.out.println("遞歸實(shí)現(xiàn)--");

        System.out.println("前序:");
        tree.recursionPrerEgodic(tree.root);

        System.out.println("中序:");
        tree.recursionMidEgodic(tree.root);

        System.out.println("后序:");
        tree.recursionPostEgodic(tree.root);

        // 遞歸調(diào)用一個(gè)方法，相當(dāng)于將數(shù)據(jù)加入一個(gè)棧中，先進(jìn)后出

        System.out.println("循環(huán)實(shí)現(xiàn)--");

        System.out.println("前序:");
        tree.loopPreEgodic(tree.root);

        System.out.println("中序:");
        tree.loopMidEgodic(tree.root);

        System.out.println("后序1:");
        tree.loopPostEgodic_1(tree.root);

        System.out.println("后序2:");
        tree.loopPostEgodic_2(tree.root);

        System.out.println("層序:");
        tree.levelEgodic(tree.root);
    }
}

五丶測試結(jié)果

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

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

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