6.40.c

数据结构习题及答案

6.40③  若在二叉链表的结点中只增设一个双亲域
以指示其双亲结点，则在遍历过程中能否不设栈？
试以此存储结构编写不设栈进行中序遍历的递推形
式的算法。

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

带双亲指域的二叉链表类型定义：
typedef struct BiPTNode {
  TElemType data;
  BiTNode  *lchild, *rchild, *parent;
} BiPTNode, *BiPTree;
void InOrder(BiPTree PT, void (*visit)(TElemType))
/* 不使用栈，非递归中序遍历二叉树bt，  */
/* 对每个结点的元素域data调用函数visit */
{ BiPTree p;
  p=PT;
  while(p->lchild) p=p->lchild;                          //向左走到尽头
  while(p)
  {
    visit(p->data);
    if(p->rchild)                                        //寻找中序后继:当有右子树时
    {
      p=p->rchild;
      while(p->lchild) p=p->lchild;                      //后继就是在右子树中向左走到尽头
    }
    else if(p->parent->lchild==p) p=p->parent;           //当自己是双亲的左孩子时后继就是双亲
    else
    {
      while(p->parent&&p->parent->rchild==p) p=p->parent;
      p=p->parent;
    }  
  } 

}