深度遍歷是軟件開發(fā)中經(jīng)常遇到的遍歷方法。常用的遍歷方法主要有下面三種：（1）前序遍歷；（2）中序遍歷；（3）后序遍歷。按照遞歸的方法，這三種遍歷的方法其實都不困難，前序遍歷就是根-左-右，中序遍歷就是左-根-右，后續(xù)遍歷就是左-右-根。代碼實現(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）后序遍歷的一個應(yīng)用

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

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

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

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

建議：

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

上一篇：循環(huán)單向鏈表下一篇：洗牌算法

在线观看不卡亚洲电影_亚洲妓女99综合网_91青青青亚洲娱乐在线观看_日韩无码高清综合久久

二叉樹深度遍歷