、以二叉链表作存储结构，编写非递归的前序、中序、后序遍历算法。可以考虑利用栈来实现，难点在于后序遍历的非递归算法的实现(何时入栈，如何标识何时出栈)。c++

在C++中，二叉链表作为存储结构，非递归地遍历二叉树通常会使用栈的数据结构来辅助操作。以下是前序、中序和后序遍历的非递归实现，重点在于后序遍历：

**前序遍历（Preorder Traversal）：**

void preOrder(Node* root) {
    stack<Node*> s;
    if (root != NULL) {
        s.push(root);
    }

    while (!s.empty()) {
        Node* current = s.top();
        cout << current->data << " "; // 访问节点
        if (current->right != NULL) s.push(current->right); // 先访问右子树
        if (current->left != NULL) s.push(current->left); // 后访问左子树
        s.pop(); // 出栈当前节点
    }
}

**中序遍历（Inorder Traversal）：**

void inOrder(Node* root) {
    stack<Node*> s;
    Node* temp = root;

    while (temp || !s.empty()) {
        while (temp) {
            s.push(temp);
            temp = temp->left;
        }
        temp = s.top();
        s.pop();
        cout << temp->data << " "; // 访问节点
        temp = temp->right;
    }
}

**后序遍历（Postorder Traversal）：**

void postOrder(Node* root) {
    stack<Node*> s1, s2; // 两个栈，一个用于保存节点，另一个用于保存最后一个访问的节点
    if (root != NULL) {
        s1.push(root);
        s2.push(NULL);
    }

    while (!s1.empty()) {
        Node* current = s1.top();
        s1.pop();

        // 当访问的节点的左子树或右子树为空时，将节点压回s2，表示该节点已处理完毕
        if (current->right == NULL && current->left == NULL) {
            while (s2.top() != current) { // 从s2弹出直到找到当前节点
                cout << s2.top()->data << " "; // 已访问过的节点按照后序顺序输出
                s2.pop();
            }
            cout << current->data << " "; // 当前节点输出
            s2.push(current); // 保存当前节点，以便后续处理
        } else if (current->right != NULL) {
            s1.push(current->right);
        } else {
            s1.push(current->left);
        }
    }
}