c++数据结构树的二叉树的前序中序后序遍历的递归与非递归代码包括输入与输出

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

假设二叉树的节点定义如下：

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

前序遍历：

递归版本：

void preorderTraversal(Node* root) {
    if (!root) return;
    cout << root->val << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

非递归版本：

void preorderTraversal(Node* root) {
    stack<Node*> s;
    s.push(root);
    while (!s.empty()) {
        Node* node = s.top();
        s.pop();
        if (!node) continue;
        cout << node->val << " ";
        s.push(node->right);
        s.push(node->left);
    }
}

中序遍历：

递归版本：

void inorderTraversal(Node* root) {
    if (!root) return;
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

非递归版本：

void inorderTraversal(Node* root) {
    stack<Node*> s;
    Node* node = root;
    while (node || !s.empty()) {
        while (node) {
            s.push(node);
            node = node->left;
        }
        node = s.top();
        s.pop();
        cout << node->val << " ";
        node = node->right;
    }
}

后序遍历：

递归版本：

void postorderTraversal(Node* root) {
    if (!root) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->val << " ";
}

非递归版本：

void postorderTraversal(Node* root) {
    stack<Node*> s;
    Node* node = root;
    Node* last = NULL;
    while (node || !s.empty()) {
        while (node) {
            s.push(node);
            node = node->left;
        }
        node = s.top();
        if (!node->right || node->right == last) {
            cout << node->val << " ";
            s.pop();
            last = node;
            node = NULL;
        } else {
            node = node->right;
        }
    }
}

输入与输出：

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);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    cout << "前序遍历(递归): ";
    preorderTraversal(root);
    cout << endl;

    cout << "前序遍历(非递归): ";
    preorderTraversal(root);
    cout << endl;

    cout << "中序遍历(递归): ";
    inorderTraversal(root);
    cout << endl;

    cout << "中序遍历(非递归): ";
    inorderTraversal(root);
    cout << endl;

    cout << "后序遍历(递归): ";
    postorderTraversal(root);
    cout << endl;

    cout << "后序遍历(非递归): ";
    postorderTraversal(root);
    cout << endl;

    return 0;
}

输出结果：

前序遍历(递归): 1 2 4 5 3 6 7 
前序遍历(非递归): 1 2 4 5 3 6 7 
中序遍历(递归): 4 2 5 1 6 3 7 
中序遍历(非递归): 4 2 5 1 6 3 7 
后序遍历(递归): 4 5 2 6 7 3 1 
后序遍历(非递归): 4 5 2 6 7 3 1