c++ 二叉树的非递归遍历

C++中，二叉树的非递归遍历可以使用栈来实现。以下是三种遍历方式的代码实现：

1. 非递归先序遍历：

void preorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    if(root != nullptr) {
        s.push(root);
    }
    while(!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        cout << node->val << " ";
        if(node->right != nullptr) {
            s.push(node->right);
        }
        if(node->left != nullptr) {
            s.push(node->left);
        }
    }
}

2. 非递归中序遍历：

void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* node = root;
    while(node != nullptr || !s.empty()) {
        while(node != nullptr) {
            s.push(node);
            node = node->left;
        }
        node = s.top();
        s.pop();
        cout << node->val << " ";
        node = node->right;
    }
}

3. 非递归后序遍历：

void postorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* node = root, *lastNodeVisited = nullptr;
    while(node != nullptr || !s.empty()) {
        while(node != nullptr) {
            s.push(node);
            node = node->left;
        }
        node = s.top();
        if(node->right == nullptr || node->right == lastNodeVisited) {
            cout << node->val << " ";
            s.pop();
            lastNodeVisited = node;
            node = nullptr;
        } else {
            node = node->right;
        }
    }
}

以上代码中，TreeNode是二叉树节点的定义，val表示节点的值，left和right分别表示左子树和右子树。