编写二叉树中序遍历的非递归算法

非递归的二叉树中序遍历算法需要借助辅助栈来实现。具体步骤如下：

1. 初始化当前节点为根节点，辅助栈为空。
2. 如果当前节点不为空或者栈不为空，则继续遍历；否则结束遍历。
3. 如果当前节点不为空，则将当前节点入栈，当前节点移动到其左子节点。
4. 如果当前节点为空，则将栈顶节点出栈，并输出其值，当前节点移动到其右子节点。
5. 重复步骤2。

下面是二叉树中序遍历的非递归算法的代码实现：

def inorder_traversal(root):
    if not root:
        return []
    stack = []
    result = []
    curr = root
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        result.append(curr.val)
        curr = curr.right
    return result

其中，root 为二叉树的根节点，stack 为辅助栈，result 为遍历结果。curr 为当前节点，初始值为根节点。在算法的实现中，先将当前节点的左子节点全部入栈，再依次出栈并输出值，最后处理右子节点。

相关问题

编写C++程序，实现对二叉树中序遍历的非递归算法

在C++中，我们可以使用栈数据结构来实现二叉树的非递归中序遍历。非递归方法利用了迭代的方式，避免了函数调用带来的堆栈空间开销。以下是基本的步骤：

1. 定义一个辅助函数`pushNode()`用于将当前节点压入栈中，因为我们需要先处理左子树再访问根节点。
2. 定义主函数`inOrderNonRecursive(root)`，它接受根节点作为输入。初始化一个空栈和一个指向当前节点的指针。
3. 当栈不为空或者当前节点不为空时，继续循环：
- 如果当前节点不为空，将其压入栈，并设置当前节点为它的左子节点。
- 否则，弹出栈顶元素并访问它（即访问右子节点），然后设置当前节点为其右子节点，直到找到未访问的节点。
4. 访问节点的操作通常打印节点值或添加到结果数组中。

下面是一个简单的C++代码示例：

#include <iostream>
#include <stack>

struct Node {
    int data;
    Node* left, *right;
};

void pushNode(Node** root, stack<Node*>& s) {
    if (*root == nullptr)
        return;

    s.push(*root);
    pushNode(&((*root)->left), s);
}

void inOrderNonRecursive(Node* root) {
    stack<Node*> s;
    Node* curr = root;

    while (curr != nullptr || !s.empty()) {
        while (curr != nullptr) {
            s.push(curr);
            curr = curr->left;
        }

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

        std::cout << curr->data << " "; // 这里可以替换为其他操作，比如添加到容器或数组
        curr = curr->right;
    }
}

int main() {
    // 创建一个二叉树实例...
    Node* root = createYourBinaryTree(); // 假设createYourBinaryTree()是你自定义的函数

    inOrderNonRecursive(root);

    return 0;
}

有c++编写以下程序：编写一个程序prac3-2.cpp，实现二叉树的先序遍历、中序 遍历和后序遍历的递归算法，以及中序遍历的非递归算法。并对图1 所示的二叉树b给出求解结果.

在C++中，你可以使用递归和非递归的方式分别实现二叉树的三种遍历算法：先序遍历（Preorder Traversal）、中序遍历（Inorder Traversal）和后序遍历（Postorder Traversal）。这里是一个简单的例子，我们将使用结构体`TreeNode`表示二叉树节点：

#include <iostream>
using namespace std;

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 递归遍历函数
void preorderTraversal(TreeNode* root) {
    if (root != NULL) {
        cout << root->val << " "; // 先访问根节点
        preorderTraversal(root->left); // 然后左子树
        preorderTraversal(root->right); // 最后右子树
    }
}

void inorderTraversal(TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left); // 首先左子树
        cout << root->val << " "; // 然后访问根节点
        inorderTraversal(root->right); // 最后右子树
    }
}

void postorderTraversal(TreeNode* root) {
    if (root != NULL) {
        postorderTraversal(root->left); // 先左子树
        postorderTraversal(root->right); // 然后右子树
        cout << root->val << " "; // 最后访问根节点
    }
}

// 中序遍历非递归版本（使用栈）
void inorderTraversalNonRecursive(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* curr = root;
    
    while (curr != NULL || !s.empty()) {
        while (curr != NULL) {
            s.push(curr);
            curr = curr->left;
        }
        
        curr = s.top();
        s.pop();
        cout << curr->val << " ";
        
        curr = curr->right;
    }
}

int main() {
    // 构建示例二叉树 b
    // 图1的具体结构需要你自己定义，这里仅提供基础构造函数作为模板
    TreeNode* b = new TreeNode(1);
    b->left = new TreeNode(2);
    b->right = new TreeNode(3);
    b->left->left = new TreeNode(4);
    b->left->right = new TreeNode(5);

    cout << "Preorder traversal: ";
    preorderTraversal(b);
    cout << endl;

    cout << "Inorder traversal: ";
    inorderTraversal(b);
    cout << endl;

    cout << "Postorder traversal: ";
    postorderTraversal(b);
    cout << endl;

    cout << "Inorder traversal (non-recursive): ";
    inorderTraversalNonRecursive(b);
    cout << endl;

    return 0;
}

运行此程序后，会根据给定的二叉树结构打印出相应的遍历结果。注意，你需要自己补充图1所示的二叉树的具体结构。