c++数据结构树的二叉树前序中序后序的递归与非递归代码含输入和输出

好的，以下是C++数据结构树的二叉树前序、中序、后序的递归与非递归代码，包含输入和输出：

#include <iostream>
#include <stack>
using namespace std;

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

// 二叉树前序遍历的递归实现
void preOrderRecursion(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->val << " ";
    preOrderRecursion(root->left);
    preOrderRecursion(root->right);
}

// 二叉树前序遍历的非递归实现
void preOrderNonRecursion(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* curr = s.top();
        s.pop();
        cout << curr->val << " ";
        if (curr->right != nullptr) {
            s.push(curr->right);
        }
        if (curr->left != nullptr) {
            s.push(curr->left);
        }
    }
}

// 二叉树中序遍历的递归实现
void inOrderRecursion(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    inOrderRecursion(root->left);
    cout << root->val << " ";
    inOrderRecursion(root->right);
}

// 二叉树中序遍历的非递归实现
void inOrderNonRecursion(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    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;
    }
}

// 二叉树后序遍历的递归实现
void postOrderRecursion(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    postOrderRecursion(root->left);
    postOrderRecursion(root->right);
    cout << root->val << " ";
}

// 二叉树后序遍历的非递归实现
void postOrderNonRecursion(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    stack<TreeNode*> s;
    TreeNode* curr = root;
    TreeNode* lastVisited = nullptr;
    while (curr != nullptr || !s.empty()) {
        while (curr != nullptr) {
            s.push(curr);
            curr = curr->left;
        }
        curr = s.top();
        if (curr->right == nullptr || curr->right == lastVisited) {
            cout << curr->val << " ";
            s.pop();
            lastVisited = curr;
            curr = nullptr;
        } else {
            curr = curr->right;
        }
    }
}

// 测试代码
int main() {
    // 示例二叉树
    /*
        1
       / \
      2   3
     / \   \
    4   5   6
    */
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);

    // 前序遍历
    cout << "前序遍历（递归）：";
    preOrderRecursion(root);
    cout << endl;
    cout << "前序遍历（非递归）：";
    preOrderNonRecursion(root);
    cout << endl;

    // 中序遍历
    cout << "中序遍历（递归）：";
    inOrderRecursion(root);
    cout << endl;
    cout << "中序遍历（非递归）：";
    inOrderNonRecursion(root);
    cout << endl;

    // 后序遍历
    cout << "后序遍历（递归）：";
    postOrderRecursion(root);
    cout << endl;
    cout << "后序遍历（非递归）：";
    postOrderNonRecursion(root);
    cout << endl;

    return 0;
}

以上代码中，`preOrderRecursion`、`inOrderRecursion`、`postOrderRecursion` 分别表示二叉树的递归前序、中序、后序遍历，`preOrderNonRecursion`、`inOrderNonRecursion`、`postOrderNonRecursion` 分别表示二叉树的非递归前序、中序、后序遍历。在测试代码中，我们创建了一个示例二叉树，并对其进行了递归与非递归遍历的测试。