二叉树之后序遍历

一、结点结构
        在二叉树的链接存储中，通常采用的方法是：每个结点中设置三个域，即值域、左指针域和右指针域，其结点结构如下：

图1 二叉树结点结构

        其中，data表示值域，用于存储放入结点的数据元素，left和right分别表示左指针域和右指针域，用于分别存储左孩子和右孩子结点（即左右子树的根结点）的存储位置（即指针）。
        链接存储的指针类型和结点定义如下：
        typedef struct bnode
        {
            ElemType data;
            struct bnode *left, *right;
        }btree;
        其中，ElemType可以是任意数据类型如int、float或者char等，在算法中，规定其默认为int类型。

二、递归遍历
        后序遍历原理：按照先访问左子树，再访问右子树，最后访问根节点的次序访问二叉树中所有结点，且每个结点仅访问一次。其递归算法如下：
        void postorder(btree *p)
        {
            if (NULL != p)
            {
                postorder(p->left);
                postorder(p->right);
                printf("%d ", p->data);
            }
        }

三、非递归遍历
        非递归后序遍历原理：根据后序遍历二叉树的递归定义，转换成非递归函数时采用一个栈保存返回的结点，先扫描根结点的所有左结点并入栈，出栈一个结点，然后扫描该结点的右结点并入栈，再扫描该右结点的所有左结点并入栈，当一个结点的左右子树均访问后再访问该结点，如此这般，直到栈为空为止。在访问根结点的右子树后，当指针p指向右子树树根时，必须记下根结点的位置，以便在遍历右子树之后正确返回，这就产生了一个问题：在退栈回到根结点时如何区别是从左子树返回还是从右子树返回。这里采用两个栈stack和tag，并用一个共同的栈顶指针，一个存放指针值，一个存放左右子树标志（0为左子树，1为右子树）。退栈时在退出结点指针的同时区别是遍历左子树返回的还是遍历右子树返回的，以决定下一步是继续遍历右子树还是访问根结点。其非递归算法如下：     
        void postorder(btree *b)
        {
            btree *stack[MAX_SIZE], *p;
            int tag[MAX_SIZE];
            int top = 0;
            p = b;
            do
            {
                while (NULL != p)                   // 扫描左结点，入栈
                {
                    top++;
                    stack[top] = p;              
                    tag[top] = 0;
                    p = p->left;
                }
                if (top > 0)
                {
                    if (1 == tag[top])            // 左右结点均已访问过了，则访问该结点
                    {
                        printf("%d ", stack[top]->data);
                        top--;
                    }
                    else
                    {
                        p = stack[top];               
                        if (top > 0)
                        {
                            p = p->right;           // 扫描右结点
                            tag[top] = 1;          // 表示当前结点的右子树已访问过了
                        }
                    }
                }
            } while ((NULL != p) || (0 != top))
      }