erchalianbiao.txt

若在二叉链表的结点中只增设一个双亲域 以指示其双亲结点

若在二叉链表的结点中只增设一个双亲域
以指示其双亲结点，则在遍历过程中能否不设栈？
试以此存储结构编写不设栈进行中序遍历的递推形
式的算法。
要求实现以下函数：
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 */
{
    int tagback=1,tag=1;                
    while(PT!=NULL)
    {
        if(tag)                     //探索
        {
            if(PT->lchild!=NULL)PT=PT->lchild;
            else 
            {
                visit(PT->data);
                if(PT->rchild!=NULL)PT=PT->rchild;
                else 
                {
                    if(PT==PT->parent->rchild)tagback=0;
                    else tagback=1;
                    PT=PT->parent;
                    tag=0;
                }    
            }
        }
        else                        //退回
        {        
            if(tagback)            //左边退回
            {
                visit(PT->data);
                if(PT->rchild!=NULL)
                {
                    PT=PT->rchild;
                    tag=1;
                }
                else
                {
                    if(PT==PT->parent->rchild)tagback=0;
                    else tagback=1;
                    PT=PT->parent;
                }
            }
            else                      //右边退回
            {
                if(PT==PT->parent->rchild)tagback=0;
                else tagback=1;
                PT=PT->parent;            
            }
        }    
    }
}