二叉树的后序遍历

如下图表示一颗二叉树，对它进行先序遍历操作，采用两种方法，递归和非递归操作。。

遍历结果为：4526731。。

1、递归操作：

思想：若二叉树为空，返回。否则

1）后序遍历右子树；2）后序遍历左子树；3）遍历根节点

代码：

void PostOrder(BiTree root)  {      if(root==NULL)          return ;      PostOrder(root->lchild);      //递归调用，后序遍历左子树      PostOrder(root->rchild);      //递归调用，后序遍历右子树      printf("%c ", root->data);    //输出数据    }  

2、非递归操作

代码：

void PostOrder_Nonrecursive(BiTree  T)  // 后序遍历的非递归    {        stack<BiTree> S;        BiTree curr = T ;           // 指向当前要检查的节点      BiTree previsited = NULL;    // 指向前一个被访问的节点      while(curr != NULL || !S.empty())  // 栈空时结束        {            while(curr != NULL)            // 一直向左走直到为空          {                S.push(curr);                curr = curr->lchild;            }            curr = S.top();          // 当前节点的右孩子如果为空或者已经被访问，则访问当前节点          if(curr->rchild == NULL || curr->rchild == previsited)            {                cout<<curr->data<<"  ";                previsited = curr;                S.pop();                curr = NULL;            }            else              curr = curr->rchild;      // 否则访问右孩子      }    }   

或者采用双栈操作，代码：

void PostOrder_Nonrecursive1(BiTree  T)  // 后序遍历的非递归 --双栈法  {        stack<BiTree> s1 , s2;        BiTree curr ;           // 指向当前要检查的节点      s1.push(T);      while(!s1.empty())  // 栈空时结束        {          curr = s1.top();          s1.pop();          s2.push(curr);          if(curr->lchild)              s1.push(curr->lchild);          if(curr->rchild)              s1.push(curr->rchild);      }      while(!s2.empty())      {          printf("%c ", s2.top()->data);          s2.pop();      }  }