深度遍歷是軟件開發(fā)中經(jīng)常遇到的遍歷方法。常用的遍歷方法主要有下面三種：（1）前序遍歷；（2）中序遍歷；（3）后序遍歷。按照遞歸的方法，這三種遍歷的方法其實(shí)都不困難，前序遍歷就是根-左-右，中序遍歷就是左-根-右，后續(xù)遍歷就是左-右-根。代碼實(shí)現(xiàn)起來也不復(fù)雜。

1）前序遍歷

void preorder_traverse(TREE_NODE* pTreeNode)
{
    if(pTreeNode){
        printf("%d", pTreeNode->data);
        preorder_traverse(pTreeNode->left);
        preorder_traverse(pTreeNode->right);
    }
}

2）中序遍歷

void inorder_traverse(TREE_NODE* pTreeNode)
{
    if(pTreeNode){
        inorder_traverse(pTreeNode->left);
        printf("%d", pTreeNode->data);
        inorder_traverse(pTreeNode->right);
    }
}

3）后序遍歷

void afterorder_traverse(TREE_NODE* pTreeNode)
{
    if(pTreeNode){
        afterorder_traverse(pTreeNode->left);
        afterorder_traverse(pTreeNode->right);
        printf("%d", pTreeNode->data);
    }
}

4）后序遍歷的一個(gè)應(yīng)用

上面的遍歷方法看上去都比較簡(jiǎn)單，那他們的應(yīng)用是什么呢？我們可以拿編程語言中語法樹舉一個(gè)例子。比如說，現(xiàn)在我們需要計(jì)算這樣一個(gè)簡(jiǎn)單的表達(dá)式：

 int m =  1 +  2  * 5  -4 / 2;

那么這個(gè)表達(dá)式的語法樹可能是這樣的，其中末尾的分號(hào)已經(jīng)刪除。

現(xiàn)在，我們對(duì)上面的表達(dá)式進(jìn)行后序遍歷，結(jié)果應(yīng)該是這樣的： m、1、2、5、*、+、4、2、/、-、=。那么這個(gè)輸出的表達(dá)式，我們應(yīng)該怎么計(jì)算呢？其實(shí)不復(fù)雜，我們只要發(fā)現(xiàn)連續(xù)兩個(gè)數(shù)字和一個(gè)相連的符號(hào)就可以計(jì)算了，上面的表達(dá)式計(jì)算順序應(yīng)該是這樣的：

/*
*        =
*     /
*   m         -
*          /
*          +      /
*        /      /
*       1    *  4    2
*           /
*          2    5
*/

a）m、1、2、5、*、+、4、2、/、-、=  
b）m、1、10、+、4、2、/、-、=

c）m、11、4、2、/、-、=

d）m、11、2、-、=

e）m、9、=

f）m

建議：

上面的算法雖然比較簡(jiǎn)單，也比較基礎(chǔ)，但是還是建議朋友們應(yīng)該多加練習(xí)和鍛煉。