c++從後綴表達式建立表達式樹

在一個公司呆久了，不出去看看，你永遠不知道你的水平如何，你值多少錢。也就是說，作為一個技術人員，應該每隔4、5個月，出去參加幾次面試，看看自己的技術水平有沒有和IT圈脫節。但更多的是在尋找更好的機會，找一份更適合自己，待遇更高的工作。 好了，從今天起，每天都總結一個小的數據結構與算法知識，一來擴充自己的知識；二來你懂的。

二叉樹的遍歷

對於二叉樹無非就三種遍歷方式：

• 前序遍歷；
• 中序遍歷；
• 後序遍歷；

對於這三種遍歷方式，我通過下面這張圖來詳細的介紹一下我的方法。 

• 前序遍歷：訪問根節點->遍歷左子樹->遍歷右子樹
• 中序遍歷：遍歷左子樹->訪問根節點->遍歷右子樹
• 後序遍歷：遍歷左子樹->遍歷右子樹->訪問根節點

對於上圖中的二叉樹，分別使用三種遍歷得到的結果分別是：

• 前序遍歷：A->C->D->G->H->S
• 中序遍歷：D->C->G->A->H->S
• 後序遍歷：D->G->C->S->H->A

二叉樹的主要用處之一是在編譯器設計領域，如下圖所示的二叉樹： 

這是一個顆表達式樹，對這個二叉樹進行後續遍歷，得到的結果是：
a b + c d e + d * *
而這種表達式也叫做後綴表達式，很多時候，我們需要根據後綴表達式重新建立一顆二叉樹。下面就使用代碼實現這種需求。

從後綴表達式建立表達式樹

比如現在有以下一個後綴表達式：
a b + c d e + * *
根據這個後綴表達式建立二叉表達式樹，算法如下：
1. 依次讀取表達式；
2. 如果是操作數，則將該操作數壓入棧中；
3. 如果是操作符，則彈出棧中的兩個操作數，第一個彈出的操作數作為右孩子，第二個彈出的操作數作為左孩子；然後再將該操作符壓入棧中。

這樣下去，就可以建立一顆完整的表達式樹。

代碼簡單實現

下面就使用C++代碼進行了簡單的實現。

定義樹節點信息。

typedef struct BinaryNode{
    char data;
    BinaryNode *left;
    BinaryNode *right;}TreeNode;

創建一個新的節點。

TreeNode* CreateTreeNode(char ch){
    TreeNode *pNode = new TreeNode;
    pNode->data = ch;
    pNode->left = NULL;
    pNode->right = NULL;
    return pNode;}

讀取表達式，創建表達式樹。

stack<TreeNode *> nodeStack;char ch;while ((ch = getchar()) != '\n'){
    TreeNode *pNode = CreateTreeNode(ch);
    if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
    {
        TreeNode *pRight = nodeStack.top();
        nodeStack.pop();
        TreeNode *pLeft = nodeStack.top();
        nodeStack.pop();

        pNode->right = pRight;
        pNode->left = pLeft;
        nodeStack.push(pNode);
    }
    else
    {
        nodeStack.push(pNode);
    }}

上面只是對算法的一個簡單的描述，如果要實現編譯器那種要求的，還有很多事要去完成。你說呢？