6.39.c

数据结构习题及答案

6.39④ 假设在二叉链表的结点中增设两个域：双亲
域(parent)以指示其双亲结点；标志域(mark取值0，
1或2)以区分在遍历过程中到达该结点时应继续向左
或向右或访问该结点。 试以此存储结构编写不用栈
进行后序遍历的递推形式的算法。

要求实现以下函数：
void PostOrder(BiPTree bt, void (*visit)(TElemType))
/* 不使用栈，非递归后序遍历二叉树bt，  */
/* 对每个结点的元素域data调用函数visit */

带双亲指针和标志域的二叉链表类型定义：
typedef struct BiPTNode {
  TElemType data;
  BiTNode  *lchild, *rchild, *parent;
  int       mark;
} BiPTNode, *BiPTree;
void PostOrder(BiPTree bt, void (*visit)(TElemType))
/* 不使用栈，非递归后序遍历二叉树bt，  */
/* 对每个结点的元素域data调用函数visit */
{ BiPTNode *p;  
  p=bt;
  while(p)
    switch(p->mark)
      {
      case 0:
        p->mark=1;
        if(p->lchild) p=p->lchild; //访问左子树
        break;
      case 1:
        p->mark=2;
        if(p->rchild) p=p->rchild; //访问右子树
        break;
      case 2:
        visit(p->data);
        p->mark=0;   //恢复mark值
        p=p->parent; //返回双亲结点
     }
}