国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

Java 數(shù)據(jù)結(jié)構(gòu)篇-二叉樹的深度優(yōu)先遍歷（實(shí)現(xiàn)：遞歸方式、非遞歸方式）

2年前作者：小扳分類：Toy博客閱讀(24)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了Java 數(shù)據(jù)結(jié)構(gòu)篇-二叉樹的深度優(yōu)先遍歷（實(shí)現(xiàn)：遞歸方式、非遞歸方式）。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

??博客主頁：?【小扳_-CSDN博客】
?感謝大家點(diǎn)贊??收藏?評(píng)論???

Java 數(shù)據(jù)結(jié)構(gòu)篇-二叉樹的深度優(yōu)先遍歷（實(shí)現(xiàn)：遞歸方式、非遞歸方式）,Java 數(shù)據(jù)結(jié)構(gòu)與算法篇,數(shù)據(jù)結(jié)構(gòu),深度優(yōu)先,算法,java

Java 數(shù)據(jù)結(jié)構(gòu)篇-二叉樹的深度優(yōu)先遍歷（實(shí)現(xiàn)：遞歸方式、非遞歸方式）,Java 數(shù)據(jù)結(jié)構(gòu)與算法篇,數(shù)據(jù)結(jié)構(gòu),深度優(yōu)先,算法,java

文章目錄

? ? ? ? 1.0 二叉樹的說明

? ? ? ? 1.1 二叉樹的實(shí)現(xiàn)

? ? ? ? 2.0 二叉樹的優(yōu)先遍歷說明

? ? ? ? 3.0 用遞歸方式實(shí)現(xiàn)二叉樹遍歷

? ? ? ? 3.1 用遞歸方式實(shí)現(xiàn)遍歷 - 前序遍歷

? ? ? ? 3.2?用遞歸方式實(shí)現(xiàn)遍歷 - 中序遍歷

????????3.3?用遞歸方式實(shí)現(xiàn)遍歷 - 后序遍歷

? ? ? ? 4.0 用非遞歸方式實(shí)現(xiàn)二叉樹遍歷

????????4.1 用非遞歸方式實(shí)現(xiàn)遍歷 - 前序遍歷

????????4.2?用非遞歸方式實(shí)現(xiàn)遍歷 - 中序遍歷

? ? ? ? 4.3?用非遞歸方式實(shí)現(xiàn)遍歷 - 后序遍歷

? ? ? ? 5.0 深度遍歷的完整代碼

? ? ? ? 1.0 二叉樹的說明

????????二叉樹是一種樹形數(shù)據(jù)結(jié)構(gòu)，其中每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，分別稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。二叉樹可以為空，或者包含一個(gè)根節(jié)點(diǎn)和兩個(gè)指向左子樹和右子樹的指針。

? ? ? ? 1.1 二叉樹的實(shí)現(xiàn)

二叉樹可以是空的，也可以是具有以下特點(diǎn)的非空樹：

? ? ? ? ?- 每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，分別稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。

? ? ? ? ?- 左子樹和右子樹都是二叉樹。

代碼實(shí)現(xiàn)如下：

public class MyBinaryTree {

    //指向左子樹
    private MyBinaryTree left;
    //當(dāng)前節(jié)點(diǎn)的值
    private int val;
    //指向右子樹
    private MyBinaryTree right;

    //構(gòu)造方法一:帶一個(gè)值的參數(shù)
    public MyBinaryTree(int val) {
        this.val = val;
    }

    //構(gòu)造方法二:帶三個(gè)參數(shù)
    public MyBinaryTree(MyBinaryTree left, int val, MyBinaryTree right) {
        this.left = left;
        this.val = val;
        this.right = right;
    }

}

? ? ? ? 實(shí)現(xiàn)兩個(gè)構(gòu)造方法是為了創(chuàng)建二叉樹的時(shí)候會(huì)比較方便一些。

二叉樹的創(chuàng)建如下：

MyBinaryTree myBinaryTree = new MyBinaryTree(new MyBinaryTree(new MyBinaryTree(4),2,null),
                                                        1,
                                             new MyBinaryTree(new MyBinaryTree(5),3,new MyBinaryTree(6)));

該二叉樹的圖片：

Java 數(shù)據(jù)結(jié)構(gòu)篇-二叉樹的深度優(yōu)先遍歷（實(shí)現(xiàn)：遞歸方式、非遞歸方式）,Java 數(shù)據(jù)結(jié)構(gòu)與算法篇,數(shù)據(jù)結(jié)構(gòu),深度優(yōu)先,算法,java

? ? ? ? 2.0 二叉樹的優(yōu)先遍歷說明

????????二叉樹的優(yōu)先遍歷是指按照一定順序訪問二叉樹中的所有節(jié)點(diǎn)。常見的三種優(yōu)先遍歷方式包括：前序遍歷、中序遍歷和后序遍歷。可以使用遞歸實(shí)現(xiàn)、非遞歸實(shí)現(xiàn)這三種遍歷方式。

? ? ? ? ? ? ? ?

? ? ? ? 3.0 用遞歸方式實(shí)現(xiàn)二叉樹遍歷

? ? ? ? 遞歸實(shí)現(xiàn)前序遍歷、中序遍歷、后續(xù)遍歷。用遞歸實(shí)現(xiàn)這三種遍歷方式的區(qū)別就是對(duì)于數(shù)據(jù)什么時(shí)候處理，如打印。

? ? ? ? ? ? ? ? -?前序遍歷（Preorder Traversal）：首先訪問根節(jié)點(diǎn)，然后遞歸地遍歷左子樹，最后遞歸地遍歷右子樹。在前序遍歷中，節(jié)點(diǎn)的訪問順序是“根-左-右”。

? ? ? ? ? ? ? ? -?中序遍歷（Inorder Traversal）：首先遞歸地遍歷左子樹，然后訪問根節(jié)點(diǎn)，最后遞歸地遍歷右子樹。在中序遍歷中，節(jié)點(diǎn)的訪問順序是“左-根-右”。

? ? ? ? ? ? ? ? -?后序遍歷（Postorder Traversal）：首先遞歸地遍歷左子樹，然后遞歸地遍歷右子樹，最后訪問根節(jié)點(diǎn)。在后序遍歷中，節(jié)點(diǎn)的訪問順序是“左-右-根”。

? ? ? ? 3.1 用遞歸方式實(shí)現(xiàn)遍歷 - 前序遍歷

? ? ? ? 具體思路為：在遞出之前需要對(duì)當(dāng)前節(jié)點(diǎn)的值訪問，然后再接著向左子樹遞出，一直下去，每一次都需要先對(duì)當(dāng)前節(jié)點(diǎn)的值訪問，直到 node == null 時(shí)，左子樹結(jié)束遞出。當(dāng)右子樹此時(shí)也為? node == null 時(shí)，從葉子節(jié)點(diǎn)開始回歸，回歸到上一個(gè)節(jié)點(diǎn)的右子樹。

代碼實(shí)現(xiàn)如下：

假設(shè)該二叉樹的圖：

Java 數(shù)據(jù)結(jié)構(gòu)篇-二叉樹的深度優(yōu)先遍歷（實(shí)現(xiàn)：遞歸方式、非遞歸方式）,Java 數(shù)據(jù)結(jié)構(gòu)與算法篇,數(shù)據(jù)結(jié)構(gòu),深度優(yōu)先,算法,java

那么前序遍歷打印的順序?yàn)椋?24356

    //使用遞歸實(shí)現(xiàn)前序遍歷
    public void preTraversalRecursion(MyBinaryTree node) {
        if (node == null) {
            return;
        }
        System.out.print(node.val + " ");
        preTraversalRecursion(node.left);
        preTraversalRecursion(node.right);
    }

????????

? ? ? ? 3.2?用遞歸方式實(shí)現(xiàn)遍歷 - 中序遍歷

????????具體思路為：向左子樹遞出，一直下去，直到 node == null 時(shí)，左子樹結(jié)束遞出。再來對(duì)當(dāng)前節(jié)點(diǎn)的值進(jìn)行訪問，接著繼續(xù)向著右子樹遞出，當(dāng)右子樹此時(shí)也為?node == null 時(shí)，從葉子節(jié)點(diǎn)開始回歸，回歸到上一個(gè)節(jié)點(diǎn)的右子樹前先對(duì)當(dāng)前節(jié)點(diǎn)的值進(jìn)行訪問。

代碼實(shí)現(xiàn)如下：

假設(shè)該二叉樹的圖：

Java 數(shù)據(jù)結(jié)構(gòu)篇-二叉樹的深度優(yōu)先遍歷（實(shí)現(xiàn)：遞歸方式、非遞歸方式）,Java 數(shù)據(jù)結(jié)構(gòu)與算法篇,數(shù)據(jù)結(jié)構(gòu),深度優(yōu)先,算法,java

中序遍歷打印的順序?yàn)椋?21563

    //使用遞歸實(shí)現(xiàn)中序遍歷
    public void middleTraversalRecursion(MyBinaryTree node) {

        if (node == null) {
            return;
        }

        middleTraversalRecursion(node.left);
        System.out.print(node.val + " ");
        middleTraversalRecursion(node.right);

    }

? ? ? ? 相對(duì)于前序遍歷，中序遍歷就是將對(duì)節(jié)點(diǎn)的值的訪問進(jìn)行換了一下位置。先進(jìn)行左子樹遞歸，再來訪問值，最后再右子樹遞歸。

????????3.3?用遞歸方式實(shí)現(xiàn)遍歷 - 后序遍歷

????????具體思路為：向左子樹遞出，一直下去，直到 node == null 時(shí)，左子樹結(jié)束遞出。再接著繼續(xù)向著右子樹遞出，再來對(duì)當(dāng)前節(jié)點(diǎn)的值進(jìn)行訪問，當(dāng)右子樹此時(shí)也為?node == null 時(shí)，從葉子節(jié)點(diǎn)開始回歸，回歸到對(duì)當(dāng)前節(jié)點(diǎn)的值進(jìn)行訪問。

代碼實(shí)現(xiàn)如下：

假設(shè)該二叉樹的圖：

Java 數(shù)據(jù)結(jié)構(gòu)篇-二叉樹的深度優(yōu)先遍歷（實(shí)現(xiàn)：遞歸方式、非遞歸方式）,Java 數(shù)據(jù)結(jié)構(gòu)與算法篇,數(shù)據(jù)結(jié)構(gòu),深度優(yōu)先,算法,java

后續(xù)遍歷打印順序?yàn)椋?25631

    //使用遞歸實(shí)現(xiàn)后續(xù)遍歷
    public void postTraversalRecursion(MyBinaryTree node) {
        if (node == null) {
            return;
        }
        postTraversalRecursion(node.left);
        postTraversalRecursion(node.right);
        System.out.print(node.val + " ");
    }

? ? ? ? 4.0 用非遞歸方式實(shí)現(xiàn)二叉樹遍歷

? ? ? ? 非遞歸實(shí)現(xiàn)前序遍歷、中序遍歷、后續(xù)遍歷。用非遞歸實(shí)現(xiàn)這三種遍歷方式的區(qū)別是訪問的順序不同，而前中后序它們所走的路線是一致的。

假設(shè)該樹的圖片：

Java 數(shù)據(jù)結(jié)構(gòu)篇-二叉樹的深度優(yōu)先遍歷（實(shí)現(xiàn)：遞歸方式、非遞歸方式）,Java 數(shù)據(jù)結(jié)構(gòu)與算法篇,數(shù)據(jù)結(jié)構(gòu),深度優(yōu)先,算法,java

? ? ? ? 具體思路為：先定義一個(gè)當(dāng)前節(jié)點(diǎn) curr 一開始指向根節(jié)點(diǎn)，還需要有一個(gè)棧的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)數(shù)據(jù)。從根節(jié)點(diǎn)開始往后先左子樹一直遍歷下去 curr = curr.left ，每次都需要存儲(chǔ)當(dāng)前節(jié)點(diǎn)到棧中，直到 curr == null 時(shí)，說明了左子樹已經(jīng)遍歷完畢了。此時(shí)需要棧彈出節(jié)點(diǎn)，來尋找 “來時(shí)的路”，彈出來的節(jié)點(diǎn)就是離當(dāng)前節(jié)點(diǎn)最近的節(jié)點(diǎn)，在原路返回的時(shí)候，還要判斷當(dāng)前節(jié)點(diǎn)是否還有右子樹，將彈出棧的節(jié)點(diǎn)的右子樹賦值給 curr = tp.right 。如果右子樹不為 null ，就會(huì)繼續(xù)對(duì)當(dāng)前節(jié)點(diǎn)的左子樹遍歷，且把當(dāng)前節(jié)點(diǎn)壓入棧中，方便記住 “來時(shí)的路”，；如果右子樹不為 null ，繼續(xù)把棧中的節(jié)點(diǎn)彈出，直到棧中沒有了節(jié)點(diǎn)且 curr == null 時(shí)，因此整個(gè)二叉樹就遍歷結(jié)束了。

????????4.1 用非遞歸方式實(shí)現(xiàn)遍歷 - 前序遍歷

????????對(duì)于前序遍歷來說，就是在來到下一個(gè)節(jié)點(diǎn)之前對(duì)當(dāng)前節(jié)點(diǎn)的值先訪問了。

代碼如下：

    //非遞歸實(shí)現(xiàn)前序遍歷
    public void preTraversal(MyBinaryTree node) {
        MyBinaryTree curr = node;
        LinkedList<MyBinaryTree> stack = new LinkedList<>();

        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                System.out.print(curr.val + " ");
                stack.push(curr);
                curr = curr.left;
            }else {
                MyBinaryTree tp = stack.pop();
                curr = tp.right;
            }
        }
        System.out.println();

    }

????????4.2?用非遞歸方式實(shí)現(xiàn)遍歷 - 中序遍歷

? ? ? ? 對(duì)于中序遍歷來說，在棧彈出節(jié)點(diǎn)后，對(duì)彈出的節(jié)點(diǎn)進(jìn)行訪問。

代碼如下：

    //非遞歸實(shí)現(xiàn)中序遍歷
    public void middleTraversal(MyBinaryTree node) {
        MyBinaryTree curr = node;
        LinkedList<MyBinaryTree> stack = new LinkedList<>();
        while ( curr != null || !stack.isEmpty()) {

            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }else  {
                MyBinaryTree tp = stack.pop();
                System.out.print(tp.val + " ");
                curr = tp.right;
            }
        }
        System.out.println();

    }

? ? ? ? 4.3?用非遞歸方式實(shí)現(xiàn)遍歷 - 后序遍歷

? ? ? ? 相比前面兩種前中后序遍歷，后序遍歷會(huì)多了一個(gè)判斷，由于先訪問完當(dāng)前節(jié)點(diǎn)的左子樹和右子樹后，才能對(duì)當(dāng)前節(jié)點(diǎn)的值進(jìn)行訪問，所以不能訪問完左子樹后，立馬將當(dāng)前節(jié)點(diǎn)彈出棧，還需要保留該節(jié)點(diǎn)，先對(duì)該節(jié)點(diǎn)的右節(jié)點(diǎn)進(jìn)行訪問完畢之后，再來訪問該節(jié)點(diǎn)的值，最后就可以彈出棧了。需要先判斷，當(dāng)前節(jié)點(diǎn)的右子樹為 null 時(shí)，可以彈出當(dāng)前節(jié)點(diǎn)或者已經(jīng)對(duì)當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)訪問完畢之后，也可以將當(dāng)前節(jié)點(diǎn)彈出。

????????那么如何來判斷是否訪問完畢當(dāng)前節(jié)點(diǎn)的右子樹了？

? ? ? ? 可以用一個(gè)變量來標(biāo)記，只需要判斷最近彈出棧的節(jié)點(diǎn)是否為當(dāng)前節(jié)點(diǎn)的右子樹節(jié)點(diǎn)即可。

代碼如下：

    //非遞歸實(shí)現(xiàn)后序遍歷
    public void postTraversal(MyBinaryTree node) {
        MyBinaryTree crr = node;
        LinkedList<MyBinaryTree> stack = new LinkedList<>();
        MyBinaryTree pop = null;//最后一次彈棧元素
        while ( crr != null || !stack.isEmpty()) {
            if (crr != null) {
                stack.push(crr);
                crr = crr.left;
            }else {
                MyBinaryTree tp = stack.peek();
                if ( tp.right == null || tp.right == pop ) {
                    pop = stack.pop();
                    System.out.print(pop.val + " ");
                }else {
                    crr = tp.right;
                }

            }
        }
    }

? ? ? ? 5.0 深度遍歷的完整代碼

import java.util.LinkedList;

public class MyBinaryTree {

    //指向左子樹
    private MyBinaryTree left;
    //當(dāng)前節(jié)點(diǎn)的值
    private int val;
    //指向右子樹
    private MyBinaryTree right;

    //構(gòu)造方法一:帶一個(gè)值的參數(shù)
    public MyBinaryTree(int val) {
        this.val = val;
    }

    //構(gòu)造方法二:帶三個(gè)參數(shù)
    public MyBinaryTree(MyBinaryTree left, int val, MyBinaryTree right) {
        this.left = left;
        this.val = val;
        this.right = right;
    }


    //使用遞歸實(shí)現(xiàn)前序遍歷
    public void preTraversalRecursion(MyBinaryTree node) {
        if (node == null) {
            return;
        }
        System.out.print(node.val + " ");
        preTraversalRecursion(node.left);
        preTraversalRecursion(node.right);
    }

    //使用遞歸實(shí)現(xiàn)中序遍歷
    public void middleTraversalRecursion(MyBinaryTree node) {

        if (node == null) {
            return;
        }

        middleTraversalRecursion(node.left);
        System.out.print(node.val + " ");
        middleTraversalRecursion(node.right);

    }

    //使用遞歸實(shí)現(xiàn)后續(xù)遍歷
    public void postTraversalRecursion(MyBinaryTree node) {
        if (node == null) {
            return;
        }
        postTraversalRecursion(node.left);
        postTraversalRecursion(node.right);
        System.out.print(node.val + " ");
    }


    //非遞歸實(shí)現(xiàn)前序遍歷
    public void preTraversal(MyBinaryTree node) {
        MyBinaryTree curr = node;
        LinkedList<MyBinaryTree> stack = new LinkedList<>();

        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                System.out.print(curr.val + " ");
                stack.push(curr);
                curr = curr.left;
            }else {
                MyBinaryTree tp = stack.pop();
                curr = tp.right;
            }
        }
        System.out.println();

    }

    //非遞歸實(shí)現(xiàn)中序遍歷
    public void middleTraversal(MyBinaryTree node) {
        MyBinaryTree curr = node;
        LinkedList<MyBinaryTree> stack = new LinkedList<>();
        while ( curr != null || !stack.isEmpty()) {

            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }else  {
                MyBinaryTree tp = stack.pop();
                System.out.print(tp.val + " ");
                curr = tp.right;
            }
        }
        System.out.println();

    }


    //非遞歸實(shí)現(xiàn)后序遍歷
    public void postTraversal(MyBinaryTree node) {
        MyBinaryTree crr = node;
        LinkedList<MyBinaryTree> stack = new LinkedList<>();
        MyBinaryTree pop = null;//最后一次彈棧元素
        while ( crr != null || !stack.isEmpty()) {
            if (crr != null) {
                stack.push(crr);
                crr = crr.left;
            }else {
                MyBinaryTree tp = stack.peek();
                if ( tp.right == null || tp.right == pop ) {
                    pop = stack.pop();
                    System.out.print(pop.val + " ");
                }else {
                    crr = tp.right;
                }

            }
        }
    }

}

Java 數(shù)據(jù)結(jié)構(gòu)篇-二叉樹的深度優(yōu)先遍歷（實(shí)現(xiàn)：遞歸方式、非遞歸方式）,Java 數(shù)據(jù)結(jié)構(gòu)與算法篇,數(shù)據(jù)結(jié)構(gòu),深度優(yōu)先,算法,java文章來源地址http://www.zghlxwxcb.cn/news/detail-752532.html

到了這里，關(guān)于Java 數(shù)據(jù)結(jié)構(gòu)篇-二叉樹的深度優(yōu)先遍歷（實(shí)現(xiàn)：遞歸方式、非遞歸方式）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場(chǎng)。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

相關(guān)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請(qǐng)作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包