1. 簡介

依舊是下面的這三句話：

先序遍歷：根左右

中序遍歷：左根右

后序遍歷：左右根

        在上文我們接觸到了先序遍歷，本文我們開始學(xué)習(xí)中序遍歷，中序遍歷采用左根右的遍歷方式，如圖，就一個(gè)最簡單的二叉樹遍歷而言，中序遍歷的遍歷訪問過程是先B再A再C。

        實(shí)際上的二叉樹并沒有這么簡單，其應(yīng)該是由多個(gè)結(jié)點(diǎn)構(gòu)成的，如圖所示，進(jìn)行第一次訪問的時(shí)候，我們?cè)贏BC中進(jìn)行遍歷，由左根右的順序，我們遍歷訪問到B，這時(shí)候先別急，B同時(shí)又作為BDG的根結(jié)點(diǎn)，因此需要繼續(xù)向下進(jìn)行遍歷，此時(shí)我們遍歷到DEF，這時(shí)E屬于這一組之中的左結(jié)點(diǎn)，因此我們根據(jù)根左右的先后順序得到了最先的遍歷效果，EDF，這EDF同時(shí)作為BDG中的左節(jié)點(diǎn)（把EDF看作一個(gè)整體）進(jìn)行回溯，此時(shí)的訪問的結(jié)點(diǎn)順序?yàn)镋DFBG同理, EDFBG作為ABC的左結(jié)點(diǎn)根據(jù)左根右的順序EDFBGAC，左半部分訪問完畢接著訪問右半部分，我們將^CH（^表示空）看作一組左中右，而C就是由EDFBGAC組合而成，因此最終的遍歷順序?yàn)椋篍DFBGACH

2. 代碼實(shí)現(xiàn)

        續(xù)上文的代碼，巧妙利用遞歸，與前文的代碼只有一個(gè)順序的區(qū)別：

//樹的中序遍歷 In-order traversal
void inorder(Node* node){
    if (node != NULL)
    {
        inorder(node->left);
        printf("%d ",node->data);
        inorder(node->right);
    }
}

3. 中綴表達(dá)式（常規(guī)算式）

中綴表達(dá)式是一個(gè)通用的算術(shù)或邏輯公式表示方法。中綴表達(dá)式就是我們最常用的表達(dá)式形式，也是人最容易理解的表達(dá)式形式。

如圖，為常規(guī)表達(dá)式：(a+b)*c

       其二叉樹的表現(xiàn)形式為：

        由前文可知波蘭式的表達(dá)方式就是 *+cab ，我們常規(guī)的表達(dá)式的計(jì)算是中序的，其表達(dá)式就是(a+b)*c，我們可以理解為將表達(dá)式利用二叉樹化，然后通過中序遍歷的方式進(jìn)行提取，如果需要發(fā)生組合時(shí)，需要我們借助括號(hào)的形式表示優(yōu)先級(jí)，這樣也有一個(gè)弊端，就是當(dāng)多個(gè)嵌套的時(shí)候需要的括號(hào)較多。

4. 相關(guān)問題

l  二叉樹的遍歷習(xí)題：1734題

請(qǐng)回答這一顆樹的中序遍歷是多少？

l  請(qǐng)回答這一顆二叉樹的中序遍歷是多少？

l  請(qǐng)回答（（a+b）+（c+d））*e作為中綴表達(dá)式的二叉樹如何，做圖表示。