非递归算法实现二叉树的先序、中序和后序遍历

二叉树的遍历有三种方式：先序遍历、中序遍历和后序遍历。非递归算法实现二叉树的遍历需要借助栈来实现。

以先序遍历为例，具体实现步骤如下：

1. 创建一个栈，将根节点入栈。
2. 当栈不为空时，取出栈顶元素并访问它。
3. 如果该节点有右子树，则将右子树入栈。
4. 如果该节点有左子树，则将左子树入栈。
5. 重复步骤2-4，直到栈为空。

中序遍历和后序遍历的实现方式类似，只需要在访问节点的时机上稍作调整即可。

下面是先序遍历、中序遍历和后序遍历的非递归算法实现代码：

// 先序遍历
void preOrder(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        visit(node);
        if (node->right != nullptr) s.push(node->right);
        if (node->left != nullptr) s.push(node->left);
    }
}

// 中序遍历
void inOrder(TreeNode* root) {
    if (root == nullptr) return;    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();
        visit(node);
        node = node->right;
    }
}

// 后序遍历
void postOrder(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> s;
    TreeNode* node = root;
    TreeNode* lastVisited = nullptr;
    while (node != nullptr || !s.empty()) {
        while (node != nullptr) {
            s.push(node);
            node = node->left;
        }
        node = s.top();
        if (node->right == nullptr || node->right == lastVisited) {
            visit(node);
            s.pop();
            lastVisited = node;
            node = nullptr;
        } else {
            node = node->right;
        }
    }
}