详解Postorder：从遍历到求值

一、postorder函数

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

postorder函数是二叉树遍历的一种方式。它遍历整棵树，先访问左子树，然后访问右子树，最后访问根节点。对于一棵二叉树，不同的遍历方式得到的序列是不一样的。postorder的特点是在访问根节点之前，先将左右子树遍历完。一个节点的遍历顺序为：首先访问左子树，然后访问右子树，最后访问根节点。

接下来是一个示例，我们创建一个二叉树并用postorder遍历它：

// 创建二叉树 
node* createNode(int data) 
{ 
    node* newNode = new node(); 
    if (!newNode) { 
        cout << "无法分配内存空间" << endl; 
        return NULL; 
    } 
    newNode->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 << temp->data << " "; 
    } 
} 

  

这里我们使用了两个栈来辅助进行遍历。首先将根节点压入第一个栈s1中，然后在s1不为空的情况下，进行以下操作：每次取出s1栈顶元素temp，将其压入第二个栈s2中，然后先将左子树压入s1，再将右子树压入s1。这样可以保证最后从s2中输出的顺序是postorder。

三、postordereval

除了遍历外，postorder还可以用来求解一些问题，例如表达式树的求值。下面是一个表达式树的例子：

// 创建表达式树 
node* createExpressionTree(string postfix) 
{ 
    stack s; 
    for (int i = 0; i < postfix.length(); i++) { 
        if (isdigit(postfix[i])) { 
            node* temp = createNode(postfix[i] - '0'); 
            s.push(temp); 
        } 
        else { 
            node* temp = createNode(postfix[i]); 
            temp->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 << root->data << " "; 
} 

// 主函数 
int main() 
{ 
    // 创建根节点 
    node* root = new node; 
    root->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的基本用法并能根据自己的需求灵活运用。希望读者能够继续深入二叉树的学习，进一步探索其更为广泛的应用领域。