C++ 非递归实现二叉树的前中后序遍历

对于C++非递归实现二叉树的前中后序遍历，可以分为以下步骤：

1. 前置知识

在进行二叉树的非递归遍历前，我们需要了解以下几个数据结构：

• 栈：用于存储遍历过程中需要回溯的节点。
• 二叉树节点的结构体：包括指向左右子树的指针以及节点的值。

2. 前序遍历

前序遍历的顺序是先遍历节点，再遍历左子树，最后遍历右子树。非递归实现的思路是：

1. 先将根节点压入栈中。
2. 循环进行以下操作：
3. 取出栈顶节点，并访问它。
4. 如果节点有右子树，将右子树压入栈中。
5. 如果节点有左子树，将左子树压入栈中。

下面是一个示例代码：

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res; // 存放结果的向量
    stack<TreeNode*> stk; // 存放遍历需要回溯的节点的栈
    if (root) stk.push(root); // 如果根节点不为空，则将根节点压入栈中
    while (!stk.empty()) {
        TreeNode* node = stk.top(); // 取出栈顶节点并访问
        res.push_back(node->val); 
        stk.pop(); 
        if (node->right) stk.push(node->right); // 若有右子树，将右子树压入栈中
        if (node->left) stk.push(node->left); // 若有左子树，将左子树压入栈中
    }
    return res; // 返回遍历的结果向量
}

3. 中序遍历

中序遍历的顺序是先遍历左子树，再遍历节点，最后遍历右子树。非递归实现的思路是：

1. 从根节点开始，将左子树压入栈中。
2. 循环进行以下操作：
3. 取出栈顶节点，并访问它。
4. 如果该节点有右子树，将右子树压入栈中。

下面是一个示例代码：

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res; // 存放结果的向量
    stack<TreeNode*> stk; // 存放遍历需要回溯的节点的栈
    TreeNode* cur = root; // 从根节点开始
    while (cur || !stk.empty()) { 
        // 若当前节点不为空或栈不为空，进入循环
        while (cur) { 
            stk.push(cur); // 将当前节点压入栈中
            cur = cur->left; // 继续访问当前节点的左子树
        }
        cur = stk.top(); 
        stk.pop(); 
        res.push_back(cur->val); 
        cur = cur->right; // 访问右子树
    }
    return res; // 返回遍历的结果向量
}

4. 后序遍历

后序遍历的顺序是先遍历左子树，再遍历右子树，最后遍历节点。非递归实现的思路是：

1. 执行类似前序遍历的操作，但是访问节点时不立即将节点的值输出，而是将它压入另一个栈中。
2. 在遍历完毕后，从该栈中依次取出节点，输出节点的值即可。

下面是一个示例代码：

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res; // 存放结果的向量
    stack<TreeNode*> stk; // 存放遍历需要回溯的节点的栈
    stack<int> output; // 存放输出节点值的栈
    if (root) stk.push(root); 
    while (!stk.empty()) {
        TreeNode* node = stk.top(); 
        stk.pop(); 
        output.push(node->val); 
        if (node->left) stk.push(node->left); 
        if (node->right) stk.push(node->right); 
    }
    while (!output.empty()) {
        res.push_back(output.top()); 
        output.pop(); 
    }
    return res; // 返回遍历的结果向量
}

希望以上的解释能够帮到您，如果还有任何问题或疑问，欢迎继续咨询。