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 preorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

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

    while (!nodeStack.empty()) {
        TreeNode* node = nodeStack.top();
        nodeStack.pop();
        cout << node->val << ' '; // 将双引号改为单引号

        if (node->right != nullptr) {
            nodeStack.push(node->right);
        }

        if (node->left != nullptr) {
            nodeStack.push(node->left);
        }
    }
}

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);

    // 非递归前序遍历
    cout << "Preorder traversal: "; // 将双引号改为单引号
    preorderTraversal(root);
    cout << endl;

    return 0;
}

上述代码中，首先定义了一个二叉树节点的结构TreeNode，包含节点值val以及左右子节点left和right。接下来，实现了一个名为preorderTraversal的函数，用于执行二叉树的前序遍历。

在preorderTraversal函数中，我们使用一个栈nodeStack来辅助遍历。我们首先将根节点压入栈中，然后进入循环。在循环中，我们从栈顶取出一个节点，并输出其值。然后，如果该节点的右子节点不为空，将其右子节点压入栈中；如果该节点的左子节点不为空，将其左子节点压入栈中。这样，我们保证了右子节点先于左子节点被访问，符合前序遍历的顺序。

在主函数中，我们创建了一个二叉树，并调用preorderTraversal函数进行前序遍历，输出遍历结果。

注意：在实际应用中，为了释放内存，需要在遍历结束后释放二叉树中的节点。以上示例未包含释放内存的过程。