二叉树后序遍历

关于书中bug

近日在看书过程中，发现书中的伪代码或是源码有些错误，不禁告诫自己牢记以下几点：

1、思想很重要，行动更重要，把想法变成程序，加几个测试用例跑一跑，有结果才有发言权

2、程序框架很重要，细节更重要。

总之呢，不能懒，自己敲了验证了，变成自己的才最重要。

不扯皮了，进入正题：

二叉树后序遍历的非递归实现

这是清华出版社王红梅老师数据结构(C++版)里的一段伪码： 节点的结构为：

struct BiNode
{
        int data;
        BiNode *lchild, *child;
};
           

后序遍历为

void PostOrder(BiNode *root)
{
        top=-1;
        while(root!=NULL || top !=-1)
        {
                while(root !=NULL)
                {
                        top++;
                        s[top].ptr=root;
                        s[top].flag=1;
                        root=rot->lchild;
                }
                while(top !=-1 && s[top].flag==2)
                {
                         root=s[top--].ptr;
                         cout<<root->data;
                }
                if(top!=-1)
                {
                         s[top].flag=2;
                         root=s[top].ptr->rchild;
                }
        }
}
           

其中s是这样的类型的一个数组：

struct element
{
        BiNode *ptr;
        int flag;
}
           

ptr存储节点，flag标志节点的右子节点是否已遍历(1--否，2--是); 我们看下上述的后序遍历算法，显然用s模拟栈的存储结构，top指示栈顶。当节点为空并且栈为空时，说明树是空的或者已经遍历完。否则我们执行遍历操作，当前节点非空，将其入栈并遍历其左子节点，直到左子结点为空，注意此时尚未遍历其右子节点，故flag置为1.然后while循环判断是否已经遍历过右子节点，若已遍历,根据后序遍历特点，此时节点可以出栈了，然后将当前栈顶节点flag置为2，并开始遍历其右子节点,,,,,,,,         这样一个个遍历后，最终栈中将只剩下根节点，我们将进入while循环，并将其弹出，那么后序遍历就完成了，然而不幸的是，我们将弹出的根节点赋值给了root，然后呢，在第一个while循环判断时，因为root !=NULL,好吧，我们只能一遍又一遍的重复上述过程........... 其实呢错就错在弹出操作哪里，我们可以改为：

cout<<s[top--].ptr->data;
           

OK啦~