C++前序遍历非递归算法

下面是一个用于实现C++前序遍历的非递归算法：

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

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

// 非递归前序遍历算法
void preorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    
    stack<TreeNode*> nodeStack;
    nodeStack.push(root);
    
    while (!nodeStack.empty()) {
        TreeNode* node = nodeStack.top();
        nodeStack.pop();
        
        cout << node->val << " ";  // 处理节点
        
        // 注意：由于栈是后进先出的数据结构，所以先将右子节点入栈，再将左子节点入栈
        if (node->right) {
            nodeStack.push(node->right);
        }
        if (node->left) {
            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 << "前序遍历结果：";
    preorderTraversal(root);
    
    return 0;
}

在上面的代码中，我们使用了一个栈来模拟递归调用的过程。首先将根节点入栈，然后循环进行以下步骤：

1. 从栈中取出一个节点，并输出节点的值。

2. 若节点有右子节点，将右子节点入栈。

3. 若节点有左子节点，将左子节点入栈。

重复上述步骤，直到栈为空。

这个算法的时间复杂度为O(n)，其中n是二叉树的节点数。