遍写程序，非递归算法实现对二叉树的后序遍历。 按先序序列建立二叉树的二叉链表（用#补齐空结点），然后借助栈对二叉树进行非递归方式的后序遍历，并输出遍历结果。 提示： 1. 顺序栈和链栈均可，涉及到的操作：初始化栈、入栈、出栈、判断栈是否为空和获取栈顶元素； 2. 若定义二叉链表类型为BiTree，则栈的数据元素类型SElemType为BiTree类型。建议定义：typedef BiTree SElemType; 输入说明：按先序方式依次输入二叉树中各结点的值，注意：用#补齐空结点。 输出说明：输出对二叉树进行非递归方式的后序遍历序列。

C++语言实现）

要实现对二叉树的后序遍历，可以使用非递归算法，具体步骤如下：

1. 定义一个栈来存储遍历过程中的结点。

2. 定义两个指针 cur 和 pre，分别指向当前遍历的结点和上一个遍历的结点。初始时，cur 指向根结点。

3. 将 cur 入栈。

4. 如果 cur 的左子结点非空，将 cur 的左子结点赋值给 cur，并入栈。

5. 如果 cur 的左子结点为空且右子结点非空，将 cur 的右子结点赋值给 cur，并入栈。

6. 如果 cur 的左子结点和右子结点都为空，或者 pre 等于 cur 的右子结点，说明 cur 的左右子树都已遍历完毕，此时可以访问 cur，并将其从栈中弹出。然后将 pre 置为 cur，并将 cur 设为 NULL，使下次循环时跳过这个结点。

7. 如果 cur 的左右子树都没有遍历完，继续执行步骤 4 和步骤 5。

8. 栈为空时，遍历结束。

C++语言实现建立二叉树的二叉链表的代码如下：

#include<iostream>
using namespace std;
struct treeNode {
    char data;//节点上数据域的自定义类型，可根据需要修改
    treeNode *lchild, *rchild;//指向左右子树的指针
};

treeNode * create()
{
    treeNode *T;
    char ch;
    cin >> ch;
    if (ch == '#')
        T = NULL;
    else
    {
        T = new treeNode;
        T->data = ch;//将输入的字符放入data域中
        T->lchild = create();//递归建立左子树
        T->rchild = create();//递归建立右子树
    }
    return T;
}

void postOrder(treeNode* root)
{
    treeNode* cur = root;
    treeNode* pre = NULL;
    stack<treeNode*> s;
    while (cur != NULL || !s.empty())
    {
        if (cur != NULL)
        {
            s.push(cur);
            cur = cur->lchild;
        }
        else
        {
            cur = s.top();
            if (cur->rchild != NULL && pre != cur->rchild)//如果右子树还未遍历或者右子树已经遍历完毕
            {
                cur = cur->rchild;
                s.push(cur);
                cur = cur->lchild;
            }
            else
            {
                cur = s.top();//遍历到该节点，出栈
                s.pop();
                cout << cur->data << " ";//输出该节点
                pre = cur;//更新上一个遍历的节点
                cur = NULL;//避免重复遍历
            }
        }
    }
}

int main()//主函数用于生成树
{
    treeNode *root;
    cout << "按先序序列输入节点，#表示空节点" << endl;
    root = create();
    cout << "后序遍历的结果为：" << endl;
    postOrder(root);
    cout << endl;
    return 0;
}