用C++输出二叉树的中序遍历，包括递归算法和非递归算法

在C++中，输出二叉树的中序遍历可以使用递归和非递归两种方法。

**递归算法**：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void inorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    inorderTraversal(root->left);
    cout << root->val << " ";  // 中序访问节点值
    inorderTraversal(root->right);
}

在这个递归函数中，我们首先检查根节点是否为空，然后对左子树进行递归遍历，接着访问根节点的值，最后遍历右子树。

**非递归算法**（也称为迭代法）：

void inorderTraversal(TreeNode* root, vector<int>& output) {
    stack<TreeNode*> s;
    TreeNode* curr = root;

    while (curr != nullptr || !s.empty()) {
        while (curr != nullptr) {
            s.push(curr);
            curr = curr->left;
        }
        
        curr = s.top();
        s.pop();
        cout << curr->val << " ";
        curr = curr->right;
    }

    output.clear();  // 如果需要返回结果，这里将输出存储到vector或其他容器中
}

这个非递归版本使用了栈数据结构，依次压入未访问的左子节点，直到到达最左边。然后从栈顶取出并访问节点，再进入其右侧，形成典型的中序遍历顺序。