用c++写一个拓展二叉树后序求前中序

在C++中，我们可以创建一个简单的二叉树结构，并提供后序遍历、先序遍历和获取中序遍历的结果。这里我们将实现一个`Node`类表示节点，然后定义后序遍历（`postorderTraversal`）、先序遍历（`inorderTraversal`）和用于计算中序遍历结果的辅助函数（`buildInOrder`）。以下是完整的示例：

#include <iostream>
using namespace std;

// 定义二叉树节点
class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

// 后序遍历函数
void postorderTraversal(Node* root) {
    if (root == nullptr) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->data << " ";
}

// 先序遍历函数
void inorderTraversal(Node* root) {
    if (root == nullptr) return;
    inorderTraversal(root->left);
    cout << root->data << " ";
    inorderTraversal(root->right);
}

// 辅助函数，用于构建中序遍历序列
vector<int> buildInOrder(Node* root) {
    vector<int> inOrder;
    stack<Node*> s;
    Node* current = root;

    while (current != nullptr || !s.empty()) {
        // 添加左子树到栈，直到遇到空节点
        while (current != nullptr) {
            s.push(current);
            current = current->left;
        }

        current = s.top();
        s.pop();

        // 输出当前节点
        inOrder.push_back(current->data);

        // 跳转到右子节点
        current = current->right;
    }
    return inOrder;
}

int main() {
    // 创建一个示例二叉树
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    cout << "Postorder traversal: ";
    postorderTraversal(root); // 输出：5 4 2 3 1

    cout << "\nInorder traversal: ";
    inorderTraversal(root); // 输出：4 2 5 1 3

    vector<int> inOrderSeq = buildInOrder(root);
    for (int i : inOrderSeq) {
        cout << i << " ";
    } // 输出：4 2 5 1 3

    return 0;
}

在这个示例中，我们首先实现了后序和先序遍历，接着通过递归和栈来实现中序遍历。在`main()`函数中，我们创建了一个简单的二叉树并展示了三种遍历方式。