詳解Postorder：從遍歷到求值

一、postorder函數

void postorder(node* root) 
{ 
    if (root == NULL) 
        return; 
    postorder(root->left); 
    postorder(root->right); 
    cout <data << " "; 
} 

postorder函數是二叉樹遍歷的一種方式。它遍歷整棵樹，先訪問左子樹，然後訪問右子樹，最後訪問根節點。對於一棵二叉樹，不同的遍歷方式得到的序列是不一樣的。postorder的特點是在訪問根節點之前，先將左右子樹遍歷完。一個節點的遍歷順序為：首先訪問左子樹，然後訪問右子樹，最後訪問根節點。

接下來是一個示例，我們創建一個二叉樹並用postorder遍歷它：

// 創建二叉樹 
node* createNode(int data) 
{ 
    node* newNode = new node(); 
    if (!newNode) { 
        cout << "無法分配內存空間" <data = data; 
    newNode->left = newNode->right = NULL; 
    return newNode; 
} 

node* createTree() 
{ 
    node* root = createNode(1); 
    root->left = createNode(2); 
    root->right = createNode(3); 
    root->left->left = createNode(4); 
    root->left->right = createNode(5); 
    root->right->left = createNode(6); 
    root->right->right = createNode(7); 
    return root; 
} 

int main() 
{ 
    node* root = createTree(); 
    cout << "postorder序列: "; 
    postorder(root); 
    return 0; 
} 

輸出結果為：4 5 2 6 7 3 1。這是因為我們遍歷了對應的二叉樹，先訪問了左子樹4和5，再訪問2，然後訪問右子樹，先訪問6和7，最後訪問1。

二、postorder遍歷二叉樹

我們剛才已經對postorder的遍歷過程進行了詳細的探討，現在我們來看一個更加實際的例子，如何使用postorder遍歷二叉樹。

// 使用postorder遍歷二叉樹 
void postorderTraversal(node* root) 
{ 
    stack s1, s2; 
    s1.push(root); 
    while (!s1.empty()) { 
        node* temp = s1.top(); 
        s1.pop(); 
        s2.push(temp); 
        if (temp->left) 
            s1.push(temp->left); 
        if (temp->right) 
            s1.push(temp->right); 
    } 
    while (!s2.empty()) { 
        node* temp = s2.top(); 
        s2.pop(); 
        cout <data << " "; 
    } 
} 

這裡我們使用了兩個棧來輔助進行遍歷。首先將根節點壓入第一個棧s1中，然後在s1不為空的情況下，進行以下操作：每次取出s1棧頂元素temp，將其壓入第二個棧s2中，然後先將左子樹壓入s1，再將右子樹壓入s1。這樣可以保證最後從s2中輸出的順序是postorder。

三、postordereval

除了遍歷外，postorder還可以用來求解一些問題，例如表達式樹的求值。下面是一個表達式樹的例子：

// 創建表達式樹 
node* createExpressionTree(string postfix) 
{ 
    stack s; 
    for (int i = 0; i right = s.top(); 
            s.pop(); 
            temp->left = s.top(); 
            s.pop(); 
            s.push(temp); 
        } 
    } 
    return s.top(); 
} 

這裡我們是用postfix表達式來創建一個表達式樹，其表達式如下所示：

string postfix = "23*5+"; 

postorder提供了一種很自然的求值方式，求解表達式樹的值其實就是一棵樹的後序遍歷。

// 計算表達式樹的值 
int postordereval(node* root) 
{ 
    if (!root) 
        return 0; 
    int left = postordereval(root->left); 
    int right = postordereval(root->right); 

    if (!isdigit(root->data)) { 
        switch (root->data) { 
        case '+': 
            return left + right; 
        case '-': 
            return left - right; 
        case '*': 
            return left * right; 
        case '/': 
            return left / right; 
        } 
    } 
    return root->data; 
} 

這裡我們使用遞歸的方法，先計算左子樹和右子樹的值，然後利用根節點的符號進行計算，並返回結果。最終得到的結果就是表達式樹的值。

四、postorder怎麼傳二叉樹進去

我們在剛才的示例中已經展示了如何構建一個二叉樹，這裡我們進一步探討如何將一個二叉樹傳入postorder函數。

// 定義二叉樹節點 
struct node { 
    int data; 
    node* left; 
    node* right; 
}; 

// postorder遍歷二叉樹 
void postorder(node* root) 
{ 
    if (root == NULL) 
        return; 
    postorder(root->left); 
    postorder(root->right); 
    cout <data <data = 1; 

    // 創建左子樹 
    root->left = new node; 
    root->left->data = 2; 

    // 創建右子樹 
    root->right = new node; 
    root->right->data = 3; 

    // 創建左子樹的左子樹和右子樹 
    root->left->left = new node; 
    root->left->left->data = 4; 
    root->left->right = new node; 
    root->left->right->data = 5; 

    // 創建右子樹的左子樹和右子樹 
    root->right->left = new node; 
    root->right->left->data = 6; 
    root->right->right = new node; 
    root->right->right->data = 7; 

    // postorder遍歷二叉樹 
    cout << "postorder序列: "; 
    postorder(root); 

    return 0; 
} 

我們可以通過逐個創建節點並設定每個節點的值和指針，來創建一棵二叉樹，並將根節點root傳入postorder函數中。這裡可以根據自己的需求靈活設定節點值和指針，從而創建出不同形狀和內容的二叉樹。

五、postorder successor

postorder successor是指在postorder遍歷中，對於當前節點，其後繼節點是哪個節點。我們來看一個示例，如何求解一個二叉樹的postorder successor：

// 找到node節點的postorder successor 
node* postorderSuccessor(node* root, node* nodeToFind) 
{ 
    stack s1, s2; 
    s1.push(root); 

    // 找到節點 
    while (!s1.empty()) { 
        node* temp = s1.top(); 
        s1.pop(); 

        if (temp->left) 
            s1.push(temp->left); 
        if (temp->right) 
            s1.push(temp->right); 

        if (temp == nodeToFind) 
            break; 
    } 

    // 找到後繼節點 
    while (!s1.empty()) { 
        node* temp = s1.top(); 
        s1.pop(); 
        s2.push(temp); 
        if (!s1.empty() && s1.top()->right == temp) { 
            while (!s1.empty() && s1.top()->right == temp) { 
                temp = s1.top(); 
                s1.pop(); 
                s2.push(temp); 
            } 
        } 
    } 

    return s2.top(); 
} 

這裡我們採用的方法是先遍歷二叉樹找到給定的節點nodeToFind，在棧s1中存儲遍歷過程中的節點。然後從棧s1中彈出節點，將其壓入s2中，並判斷是否存在後繼節點。如果當前節點是最後一個節點或者其右子節點是上一個壓入棧s1中的節點，說明當前節點的後繼節點是上一個彈出棧s1的節點。最終返回棧s2中的top節點作為當前節點的後繼節點。

結束語

Postorder作為二叉樹遍歷的一種方式，具有其特殊的特點和應用場景。通過對其定義、實現以及應用的探討，相信讀者已經掌握了postorder的基本用法並能根據自己的需求靈活運用。希望讀者能夠繼續深入二叉樹的學習，進一步探索其更為廣泛的應用領域。