2、 利用c++实现二叉树层次遍历、非递归先序遍历、非递归中序遍历、递归后序遍历。

在 C++ 中，我们可以使用队列来实现非递归层次遍历，因为层次遍历的特点是按层次顺序访问节点。对于其他遍历方法，这里给出非递归版本的先序遍历和中序遍历以及递归版本的后序遍历。

**1. 层次遍历（广度优先搜索，BFS）**

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

void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode* node = q.front();
        cout << node->val << " ";
        q.pop();

        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

**2. 非递归先序遍历（前序遍历，Preorder）**

void nonRecursivePreOrder(TreeNode* root) {
    stack<TreeNode*> s;
    if (root != nullptr) s.push(root);

    while (!s.empty()) {
        TreeNode* node = s.top();
        cout << node->val << " ";
        s.pop();

        if (node->right) s.push(node->right);  // 访问右子树
        if (node->left) s.push(node->left);   // 访问左子树
    }
}

**3. 非递归中序遍历（中序遍历，Inorder）**

void nonRecursiveInOrder(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* curNode = root;

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

**4. 递归后序遍历（后序遍历，Postorder）**

void recursivePostOrder(TreeNode* root) {
    if (root == nullptr) return;

    recursivePostOrder(root->left);
    recursivePostOrder(root->right);
    cout << root->val << " ";  // 最后输出当前节点值
}

每个函数的输入都是一个指向二叉树根节点的指针 `TreeNode* root`。注意，上述代码假设了 `TreeNode` 结构体包含一个整数值 `val` 和两个指向左右子节点的指针 `left` 和 `right`。在实际应用中，你需要根据自己的数据结构进行相应的修改。