2、 利用c++实现二叉树层次遍历、非递归先序遍历、非递归中序遍历、递归后序遍历并在主函数测试输出

在C++中，我们可以分别使用队列和栈以及递归来实现二叉树的不同遍历方式。这里是一个简单的例子，展示了如何使用非递归方法进行层次遍历、先序遍历、中序遍历和后序遍历：

#include <iostream>
#include <stack>
#include <queue>

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

// 层次遍历（非递归）
void levelOrder(TreeNode* root) {
    if (root == nullptr) return;
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        std::cout << node->val << " ";
        
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    std::cout << std::endl;
}

// 先序遍历（非递归）
void preorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> s;
    s.push(root);
    
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        std::cout << node->val << " ";
        
        if (node->right) s.push(node->right);
        if (node->left) s.push(node->left);
    }
    std::cout << std::endl;
}

// 中序遍历（非递归）
void inorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> s;
    TreeNode* prev = nullptr;

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

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

        if (prev != root->right) { // 如果不是右子节点，则已经访问完左子树，可以输出当前节点
            std::cout << root->val << " ";
            prev = root;
            root = root->right;
        } else {
            root = nullptr; // 已经访问完根节点及其所有左子节点，继续寻找下一个根节点
        }
    }
    std::cout << std::endl;
}

// 后序遍历（递归）
void postorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    std::cout << root->val << " ";
}

int main() {
    // 测试数据
    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);

    std::cout << "层次遍历: ";
    levelOrder(root);

    std::cout << "先序遍历: ";
    preorderTraversal(root);

    std::cout << "中序遍历: ";
    inorderTraversal(root);

    std::cout << "后序遍历: ";
    postorderTraversal(root);

    return 0;
}

在这个示例中，我们首先创建了一个简单的二叉树结构，然后分别调用了上述四个遍历方法并打印结果。注意，这里的后序遍历使用了递归方法，因为非递归版本相对复杂一些。