欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java數(shù)據(jù)結(jié)構(gòu)最清晰圖解二叉樹前 中 后序遍歷

 更新時(shí)間:2022年01月28日 14:45:20   作者:/少司命  
樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu),直觀地看,它是數(shù)據(jù)元素(在樹中稱為結(jié)點(diǎn))按分支關(guān)系組織起來的結(jié)構(gòu),很象自然界中的樹那樣。樹結(jié)構(gòu)在客觀世界中廣泛存在,如人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)都可用樹形象表示

一,前言

二叉樹是數(shù)據(jù)結(jié)構(gòu)中重要的一部分,它的前中后序遍歷始終貫穿我們學(xué)習(xí)二叉樹的過程,所以掌握二叉樹三種遍歷是十分重要的。本篇主要是圖解+代碼Debug分析,概念的部分講非常少,重中之重是圖解和代碼Debug分析,我可以保證你看完此篇博客對于二叉樹的前中后序遍歷有一個(gè)新的認(rèn)識(shí)??!廢話不多說,讓我們學(xué)起來吧!!

二,樹

①概念

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu),它是由n(n>=0)個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做樹是因?yàn)樗?起來像一棵倒掛的樹,也就是說它是根朝上,而葉朝下的。它具有以下的特點(diǎn):

有一個(gè)特殊的節(jié)點(diǎn),稱為根節(jié)點(diǎn),根節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn)

除根節(jié)點(diǎn)外,其余節(jié)點(diǎn)被分成M(M > 0)個(gè)互不相交的集合T1、T2、......、Tm,其中每一個(gè)集合 Ti (1 <= i <= m) 又是一棵與樹類似的子樹。每棵子樹的根節(jié)點(diǎn)有且只有一個(gè)前驅(qū),可以有0個(gè)或多個(gè)后繼

樹是遞歸定義的。

②樹的基礎(chǔ)概念

節(jié)點(diǎn)的度:一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度

樹的度:一棵樹中,最大的節(jié)點(diǎn)的度稱為樹的度

葉子節(jié)點(diǎn)或終端節(jié)點(diǎn):度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)

雙親節(jié)點(diǎn)或父節(jié)點(diǎn):若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn),則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)

孩子節(jié)點(diǎn)或子節(jié)點(diǎn):一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)

根結(jié)點(diǎn):一棵樹中,沒有雙親結(jié)點(diǎn)的結(jié)點(diǎn)

節(jié)點(diǎn)的層次:從根開始定義起,根為第1層,根的子節(jié)點(diǎn)為第2層,以此類推

樹的高度或深度:樹中節(jié)點(diǎn)的最大層次

三,二叉樹

①概念

一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合,該集合或者為空,或者是由一個(gè)根節(jié)點(diǎn)加上兩棵別稱為左子樹和右子樹的二叉 樹組成。

二叉樹的特點(diǎn):

1. 每個(gè)結(jié)點(diǎn)最多有兩棵子樹,即二叉樹不存在度大于 2 的結(jié)點(diǎn)。

2. 二叉樹的子樹有左右之分,其子樹的次序不能顛倒,因此二叉樹是有序樹。

②兩種特殊的二叉樹

1. 滿二叉樹: 一個(gè)二叉樹,如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值,則這個(gè)二叉樹就是滿二叉樹。也就是說,如果 一個(gè)二叉樹的層數(shù)為K,且結(jié)點(diǎn)總數(shù)是 ,則它就是滿二叉樹。

2. 完全二叉樹: 完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu),完全二叉樹是由滿二叉樹而引出來的。對于深度為K的,有n 個(gè)結(jié)點(diǎn)的二叉樹,當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對應(yīng)時(shí)稱之為完全 二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。

③二叉樹的性質(zhì)

1. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1,則一棵非空二叉樹的第i層上最多有2^(i-1)?(i>0)個(gè)結(jié)點(diǎn)

2. 若規(guī)定只有根節(jié)點(diǎn)的二叉樹的深度為1,則深度為K的二叉樹的最大結(jié)點(diǎn)數(shù)是2^k-1 (k>=0)

3. 對任何一棵二叉樹, 如果其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為2的非葉結(jié)點(diǎn)個(gè)數(shù)為 n2,則有n0=n2+1

4. 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度k為log2(n+1)上取整

四,二叉樹遍歷

二叉樹是有四種遍歷,層序遍歷這里不講。

①二叉樹的遍歷

所謂遍歷(Traversal)是指沿著某條搜索路線,依次對樹中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問。訪問結(jié)點(diǎn)所做的操作 依賴于具體的應(yīng)用問題(比如:打印節(jié)點(diǎn)內(nèi)容、節(jié)點(diǎn)內(nèi)容加1)。 遍歷是二叉樹上最重要的操作之一,是二叉樹上進(jìn) 行其它運(yùn)算之基礎(chǔ)。

在遍歷二叉樹時(shí),如果沒有進(jìn)行某種約定,每個(gè)人都按照自己的方式遍歷,得出的結(jié)果就比較混亂,如果按照某種 規(guī)則進(jìn)行約定,則每個(gè)人對于同一棵樹的遍歷結(jié)果肯定是相同的。如果N代表根節(jié)點(diǎn),L代表根節(jié)點(diǎn)的左子樹,R代 表根節(jié)點(diǎn)的右子樹,則根據(jù)遍歷根節(jié)點(diǎn)的先后次序有以下遍歷方式:

1. NLR:前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點(diǎn)--->根的左子樹--->根的右子樹。

2. LNR:中序遍歷(Inorder Traversal)——根的左子樹--->根節(jié)點(diǎn)--->根的右子樹。

?3. LRN:后序遍歷(Postorder Traversal)——根的左子樹--->根的右子樹--->根節(jié)點(diǎn)。

?由于被訪問的結(jié)點(diǎn)必是某子樹的根,所以N(Node)、L(Left subtree)和R(Right subtree)又可解釋為根、根 的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。

注意:三種遍歷中只有訪問根節(jié)點(diǎn)打印,每一種遍歷當(dāng)訪問到每一個(gè)節(jié)點(diǎn)都要有對應(yīng)三種不同的遍歷方式,直到遍歷到null返回到該根節(jié)點(diǎn)繼續(xù)完成遍歷?。?!比如說前序遍歷,我每訪問一個(gè)節(jié)點(diǎn)都要執(zhí)行問根結(jié)點(diǎn)--->根的左子樹--->根的右子樹這三步,中序后序遍歷一樣。

以下面這個(gè)二叉樹為例,接下來就是詳解

②前序遍歷

圖解

?代碼分析

我們用枚舉法創(chuàng)建這個(gè)二叉樹

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;
    }
// 前序遍歷
    void preOrderTraversal(TreeNode root){
        if(root == null) {
            return;
        }
        System.out.print(root.val+" ");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }

DeBug分析

③中序遍歷

圖解

// 中序遍歷
    void inOrderTraversal(TreeNode root){
        if(root == null) {
            return;
        }
        inOrderTraversal(root.left);
        System.out.print(root.val+" ");
        inOrderTraversal(root.right);
    }

?DeBug分析

④后序遍歷

圖解

 // 后序遍歷
    void postOrderTraversal(TreeNode root){
        if(root == null) {
            return;
        }
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val+" ");
    }

?DeBug分析

五,完整代碼

class TreeNode{
    public char val;
    public TreeNode right;
    public TreeNode left;
    public TreeNode(char val){
        this.val = val;
    }
 
}
 
 
public class BinaryTree {
 
    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;
    }
 
    // 前序遍歷
    void preOrderTraversal(TreeNode root){
        if(root == null) {
            return;
        }
        System.out.print(root.val+" ");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }
 
 
    // 中序遍歷
    void inOrderTraversal(TreeNode root){
        if(root == null) {
            return;
        }
        inOrderTraversal(root.left);
        System.out.print(root.val+" ");
        inOrderTraversal(root.right);
    }
 
    // 后序遍歷
    void postOrderTraversal(TreeNode root){
        if(root == null) {
            return;
        }
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val+" ");
    }
 
    
}
public class TestDeno {
 
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = binaryTree.createTree();
 
        binaryTree.preOrderTraversal(root);
        System.out.println();
        binaryTree.inOrderTraversal(root);
        System.out.println();
        binaryTree.postOrderTraversal(root);
 
    }
}

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)最清晰圖解二叉樹前 中 后序遍歷的文章就介紹到這了,更多相關(guān)Java 二叉樹遍歷內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • Java中父類和子類之間的轉(zhuǎn)換操作示例

    Java中父類和子類之間的轉(zhuǎn)換操作示例

    這篇文章主要介紹了Java中父類和子類之間的轉(zhuǎn)換操作,結(jié)合實(shí)例形式分析了Java中父類和子類之間的轉(zhuǎn)換相關(guān)原理、操作技巧與使用注意事項(xiàng),需要的朋友可以參考下
    2020-05-05
  • 基于紅黑樹插入操作原理及java實(shí)現(xiàn)方法(分享)

    基于紅黑樹插入操作原理及java實(shí)現(xiàn)方法(分享)

    下面小編就為大家分享一篇基于紅黑樹插入操作原理及java實(shí)現(xiàn)方法,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2017-12-12
  • 一文詳解Java中的類加載機(jī)制

    一文詳解Java中的類加載機(jī)制

    Java虛擬機(jī)把描述類的數(shù)據(jù)從Class文件加載到內(nèi)存,并對數(shù)據(jù)進(jìn)行校驗(yàn)、轉(zhuǎn)換解析和初始化,最終形成可以被虛擬機(jī)直接使用的Java類型,這個(gè)過程被稱作虛擬機(jī)的類加載機(jī)制。本文將詳解Java的類加載機(jī)制,需要的可以參考一下
    2022-05-05
  • javafx tableview鼠標(biāo)觸發(fā)更新屬性詳解

    javafx tableview鼠標(biāo)觸發(fā)更新屬性詳解

    這篇文章主要為大家詳細(xì)介紹了javafx tableview鼠標(biāo)觸發(fā)更新屬性的相關(guān)資料,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2017-08-08
  • 解析SpringBoot項(xiàng)目開發(fā)之Gzip壓縮過程

    解析SpringBoot項(xiàng)目開發(fā)之Gzip壓縮過程

    這篇文章主要介紹了SpringBoot項(xiàng)目開發(fā)之Gzip壓縮過程,本文給大家分享幾種Gzip壓縮方式,通過實(shí)例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2020-07-07
  • SpringBoot集成Redis,并自定義對象序列化操作

    SpringBoot集成Redis,并自定義對象序列化操作

    這篇文章主要介紹了SpringBoot集成Redis,并自定義對象序列化操作,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2021-06-06
  • Java IO流和文件操作實(shí)現(xiàn)過程解析

    Java IO流和文件操作實(shí)現(xiàn)過程解析

    這篇文章主要介紹了Java IO流和文件操作實(shí)現(xiàn)過程解析,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2019-10-10
  • 自定義mybatis插件如何實(shí)現(xiàn)sql日志打印

    自定義mybatis插件如何實(shí)現(xiàn)sql日志打印

    這篇文章主要介紹了自定義mybatis插件如何實(shí)現(xiàn)sql日志打印問題,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2023-05-05
  • Java 中的字符串常量池詳解

    Java 中的字符串常量池詳解

    本文主要介紹Java中的字符串常量池的知識(shí),這里整理了相關(guān)資料及簡單示例代碼幫助大家學(xué)習(xí)理解此部分的知識(shí),有需要的小伙伴可以參考下
    2016-09-09
  • Java使用MulticastSocket實(shí)現(xiàn)群聊應(yīng)用程序

    Java使用MulticastSocket實(shí)現(xiàn)群聊應(yīng)用程序

    這篇文章主要為大家詳細(xì)介紹了Java使用MulticastSocket實(shí)現(xiàn)群聊應(yīng)用程序,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-05-05

最新評(píng)論