二叉樹知識錦囊（二）-創(chuàng)新互聯(lián)

作者：愛塔居
成都創(chuàng)新互聯(lián)是一家專業(yè)提供壽寧企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站設(shè)計、網(wǎng)站制作、成都h5網(wǎng)站建設(shè)、小程序制作等業(yè)務(wù)。10年已為壽寧眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站設(shè)計公司優(yōu)惠進(jìn)行中。
專欄：數(shù)據(jù)結(jié)構(gòu)
作者簡介：大三學(xué)生，希望和大家一起進(jìn)步！

文章目錄

一、二叉樹的存儲

二、二叉樹的遍歷（重點(diǎn)）

2.1 前序遍歷

2.2 中序遍歷

2.3 后序遍歷

2.4 層序遍歷

2.5 小題實(shí)練

三、代碼實(shí)現(xiàn)

一、二叉樹的存儲

二叉樹的存儲結(jié)構(gòu)分為：順序存儲和類似于鏈表的鏈?zhǔn)酱鎯Α?/p>

二叉樹的鏈?zhǔn)酱鎯κ峭ㄟ^一個一個的節(jié)點(diǎn)引用起來的，常見的表示方式有二叉和三叉表示方法。

二、二叉樹的遍歷（重點(diǎn)）

遍歷是指沿著某條搜索路線，依次對樹中的每個節(jié)點(diǎn)，均做一次且僅做一次訪問。訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問題。

2.1 前序遍歷

前序遍歷：根結(jié)點(diǎn)》左子樹》右子樹

前序遍歷：

從A開始，打印A往左走，遍歷到B，打印B,再遍歷B的左子樹D，打印D，接著遍歷D的左子樹，發(fā)現(xiàn)為空，返回D，再遍歷D的右子樹G，打印G，遍歷G的左右子樹都為空，返回G,返回D，返回B，遍歷B的右子樹為空，返回B，返回A。 $A\rightarrow B\rightarrow D\rightarrow G$

再遍歷A的右子樹C，打印C，遍歷C的左子樹F，打印F，再遍歷F的左右子樹為空，返回F，返回C，再遍歷C的右子樹K，打印K,遍歷K的左右子樹為空，返回K，返回C，返回A。 $C\rightarrow F\rightarrow K$

所以這個二叉樹的前序遍歷為 $A\rightarrow B\rightarrow D\rightarrow G$ $\rightarrow C\rightarrow F\rightarrow K$

2.2 中序遍歷

中序遍歷：左子樹》根》右子樹

從A開始，到A的左子樹B，遍歷B的左子樹D，遍歷D的左子樹為空，返回D，打印D，遍歷D的右子樹G，遍歷G的左子樹為空，返回G，打印G，遍歷G的右子樹為空，返回G，返回D，返回B，打印B,遍歷B的右子樹為空，返回B，返回A，打印A。 $D\rightarrow G\rightarrow B\rightarrow A$

再遍歷A的右子樹C，遍歷C的左子樹F，遍歷F的左子樹為空，返回F，打印F，遍歷F的右子樹為空，返回F，返回C，打印C，遍歷C的右子樹K，遍歷K的左子樹為空，返回K，打印K，遍歷K的右子樹為空，返回K，返回C，返回A。 $F\rightarrow C\rightarrow K$

故該二叉樹的中序遍歷為 $D\rightarrow G\rightarrow B\rightarrow A\rightarrow$ $F\rightarrow C\rightarrow K$

2.3 后序遍歷

后序遍歷：左子樹》右子樹》根?

從A開始，遍歷A的左子樹B，遍歷B的左子樹D，遍歷D的左子樹為空，返回D，遍歷D的右子樹G，遍歷G的左右子樹為空，返回G，打印G,返回D，打印D，返回B，遍歷B的右子樹為空，返回B，打印B?，返回A。 $G\rightarrow D\rightarrow B$

遍歷A的右子樹C，遍歷C的左子樹F，遍歷F的左右子樹為空，返回F，打印F,返回C，遍歷C的右子樹K，遍歷K的左右子樹為空，返回K，打印K，返回C，打印C，返回A，打印A。 $F\rightarrow K\rightarrow C\rightarrow A$

故該二叉樹的后序遍歷為 $G\rightarrow D\rightarrow B$ $\rightarrow$ $F\rightarrow K\rightarrow C\rightarrow A$

2.4 層序遍歷

層序遍歷就是自上而下，自左至右訪問樹的結(jié)點(diǎn)的過程。

這個二叉樹的層序遍歷為 $A\rightarrow B\rightarrow C\rightarrow D\rightarrow F\rightarrow K\rightarrow G$

2.5 小題實(shí)練

1.某完全二叉樹按層次輸出（同一層從左到右）的序列為 ABCDEFGH 。該完全二叉樹的前序序列為()
A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA

因?yàn)槭峭耆鏄洌晕覀兏鶕?jù)層序遍歷的結(jié)果可以畫出二叉樹：
根據(jù)二叉樹，我們得出前序遍歷結(jié)果ABDHECFG

2.二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK;中序遍歷：HFIEJKG.則二叉樹根結(jié)點(diǎn)為()
A: E B: F C: G D: H

先序遍歷第一個結(jié)點(diǎn)就是根結(jié)點(diǎn)，故為A；
如果這道題要我們畫出這個二叉樹，我們也可以畫出：
因?yàn)橹行虮闅v順序，根結(jié)點(diǎn)的左邊結(jié)點(diǎn)都是在左邊，右邊的結(jié)點(diǎn)都是在右邊。

3.設(shè)一課二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹前序遍歷序列為()
A: adbce B: decab C: debac D: abcde

根據(jù)中序遍歷和后序遍歷結(jié)果畫出二叉樹圖為：
前序遍歷結(jié)果：abcde

4.某二叉樹的后序遍歷序列與中序遍歷序列相同，均為 ABCDEF ，則按層次輸出(同一層從左到右)的序列為()
A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF

層序遍歷結(jié)果：FEDCBA

🍓那如果知道前序遍歷序列和后序遍歷序列，我們可以畫出二叉樹嗎？

答案是不行。因?yàn)檫@樣，我們只能找到根結(jié)點(diǎn)，不能確定左子樹和右子樹的位置。

三、代碼實(shí)現(xiàn)

接下來，我們嘗試著創(chuàng)建一個二叉樹。

public  class TestBinaryTree {
static  class  TreeNode {
    public char val;//數(shù)據(jù)域
    public TreeNode left;//左孩子節(jié)點(diǎn)
    public TreeNode right;//右孩子節(jié)點(diǎn)
    public TreeNode(char val) {
        this.val = val;
    }
}
    public TreeNode createTree( ){
        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 void preOrder(TreeNode root){
        //當(dāng)二叉樹根結(jié)點(diǎn)為空
    if(root==null){
        return;
    }
    //不為空，打印樹的根結(jié)點(diǎn)的值
    System.out.print(root.val+" ");
    //這時對左子樹進(jìn)行先序遍歷，又是新的二叉樹
    preOrder(root.left);
    preOrder(root.right);
}

中序遍歷：

void inOrder(TreeNode root){
        if(root==null){
    return;
}
        inOrder(root.left);
    System.out.print(root.val+" ");
        inOrder(root.right);
}

后序遍歷：

void postOrder(TreeNode root){
    if(root==null){
        return;
    }
    inOrder(root.left);
    inOrder(root.right);
    System.out.print(root.val+" ");
}

完整代碼見鏈接：javacode: java的日常代碼---------------------- - Gitee.com?

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前名稱：二叉樹知識錦囊（二）-創(chuàng)新互聯(lián)
鏈接URL：http://www.rwnh.cn/article48/cciihp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供小程序開發(fā)、服務(wù)器托管、網(wǎng)站維護(hù)、手機(jī)網(wǎng)站建設(shè)、云服務(wù)器、App設(shè)計

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

中文字幕日韩精品一区二区免费_精品一区二区三区国产精品无卡在_国精品无码专区一区二区三区_国产αv三级中文在线

二叉樹知識錦囊（二）-創(chuàng)新互聯(lián)