C++算法之二叉樹深度遍歷

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

void preorder_traverse(TREE_NODE* pTreeNode)

{

    if(pTreeNode){

        printf("%d", pTreeNode->data);

        preorder_traverse(pTreeNode->left);

        preorder_traverse(pTreeNode->right);

    }

}

</pre>    2）中序遍歷
void inorder_traverse(TREE_NODE* pTreeNode)

{

    if(pTreeNode){

        inorder_traverse(pTreeNode->left);

        printf("%d", pTreeNode->data);

        inorder_traverse(pTreeNode->right);

    }

}

</pre>   3）后序遍歷
void afterorder_traverse(TREE_NODE* pTreeNode)

{

    if(pTreeNode){

        afterorder_traverse(pTreeNode->left);

        afterorder_traverse(pTreeNode->right);

        printf("%d", pTreeNode->data);

    }

}

</pre> 

     4）后序遍歷的一個應用

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

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

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

     現在，我們對上面的表達式進行后序遍歷，結果應該是這樣的： m、1、2、5、、4、2、\、-、+、=。那么這個輸出的表達式，我們應該怎么計算呢？其實不復雜，我們只要發現連續兩個數字和一個相連的符號就可以計算了，上面的表達式計算順序應該是這樣的：


/*


= 
/     \ 
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


</pre> 建議：

     上面的算法雖然比較簡單，也比較基礎，但是還是建議朋友們應該多加練習和鍛煉。