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

在C++中，我们可以分别使用栈、递归和迭代的方式来实现二叉树的遍历。以下是四种遍历方式的示例代码及测试输出。

首先，我们需要定义一个简单的二叉树结构：

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

### 层次遍历（非递归）
使用`std::queue`辅助：

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

    std::queue<TreeNode*> q({root});
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " "; // 输出当前节点值
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

### 非递归先序遍历（中根遍历）

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

    stack<TreeNode*> s;
    s.push(root);

    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        cout << node->val << " "; // 输出当前节点值
        if (node->right) s.push(node->right);
        if (node->left) s.push(node->left);
    }
}

### 非递归中序遍历（左根右遍历）

void inOrderNonRecursive(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* curr = root;

    while (curr || !s.empty()) {
        while (curr) {
            s.push(curr);
            curr = curr->left;
        }
        curr = s.top();
        s.pop();
        cout << curr->val << " "; // 输出当前节点值
        curr = curr->right;
    }
}

### 递归后序遍历（左中右）

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

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

在`main()`函数中测试以上函数：

int main() {
    // 创建一棵二叉树，然后调用上述函数进行遍历，并在合适的位置添加节点值的输出
    // ...

    // 调用层次遍历
    levelOrder(root);

    // 调用非递归先序遍历
    cout << "\nNon-recursive Pre-order: ";
    preOrderNonRecursive(root);

    // 调用非递归中序遍历
    cout << "\nNon-recursive In-order: ";
    inOrderNonRecursive(root);

    // 调用递归后序遍历
    cout << "\nRecursive Post-order: ";
    postOrderRecursively(root);

    return 0;
}

记得在`main`中创建并初始化你的二叉树实例。运行这个程序，它将按照对应的遍历顺序依次输出每个节点的值。