一，前言

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

二，樹(shù)

①概念

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

有一個(gè)特殊的節(jié)點(diǎn)，稱(chēng)為根節(jié)點(diǎn)，根節(jié)點(diǎn)沒(méi)有前驅(qū)節(jié)點(diǎn)

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

樹(shù)是遞歸定義的。

②樹(shù)的基礎(chǔ)概念

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

樹(shù)的度：一棵樹(shù)中，最大的節(jié)點(diǎn)的度稱(chēng)為樹(shù)的度

葉子節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)稱(chēng)為葉節(jié)點(diǎn)

雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱(chēng)為其子節(jié)點(diǎn)的父節(jié)點(diǎn)

孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹(shù)的根節(jié)點(diǎn)稱(chēng)為該節(jié)點(diǎn)的子節(jié)點(diǎn)

根結(jié)點(diǎn)：一棵樹(shù)中，沒(méi)有雙親結(jié)點(diǎn)的結(jié)點(diǎn)

節(jié)點(diǎn)的層次：從根開(kāi)始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類(lèi)推

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

三，二叉樹(shù)

①概念

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

二叉樹(shù)的特點(diǎn)：

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

2. 二叉樹(shù)的子樹(shù)有左右之分，其子樹(shù)的次序不能顛倒，因此二叉樹(shù)是有序樹(shù)。

②兩種特殊的二叉樹(shù)

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

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

③二叉樹(shù)的性質(zhì)

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

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

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

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

四，二叉樹(shù)遍歷

二叉樹(shù)是有四種遍歷，層序遍歷這里不講。

①二叉樹(shù)的遍歷

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

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

1. NLR：前序遍歷(Preorder Traversal 亦稱(chēng)先序遍歷)——訪問(wèn)根結(jié)點(diǎn)--->根的左子樹(shù)--->根的右子樹(shù)。

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

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

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

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

以下面這個(gè)二叉樹(shù)為例，接下來(lái)就是詳解

②前序遍歷

圖解

?代碼分析

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

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)最清晰圖解二叉樹(shù)前 中 后序遍歷的文章就介紹到這了,更多相關(guān)Java 二叉樹(shù)遍歷內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論