三叉链表的遍历算法

1. 不借助栈的非递归中序遍历算法

【题目】二叉树采用三叉链表的存储结构，试编写不借助栈的非递归中序遍历算法。

三叉链表类型定义：
typedef struct TriTNode {
  TElemType data;
  struct TriTNode  *parent, *lchild, *rchild;
} TriTNode, *TriTree;

void InOrder(TriTree PT, void (*visit)(TElemType))
/* 不使用栈，非递归中序遍历二叉树PT， 对每个结点的元素域data调用函数visit */
{
   TriTree p,pr;
   if(PT !=NULL){
        p=PT;
        while(p!=NULL){
            while(p->lchild!=NULL) p=p->lchild;
            visit(p->data); //访问最左孩子
            
            if(p->rchild!=NULL){
              p=p->rchild;
              continue; //如果最左孩子存在有孩子,返回第一步操作:找右孩子的最左孩子
            }
            
            //访问完左孩子,及左孩子的子孩子。应该访问根结点
            while(p->parent){
                  pr=p->parent; 
                  if(pr->rchild){ //双亲存在右孩子时
                        if(pr->rchild==p){ //当双亲只有右孩子时
                            p=pr;
                            continue;
                        }else{ //当是由左孩子指向双亲,又存在右孩子时
                            visit(pr->data);//先访问根节点
                            p=pr->rchild; //再访问右孩子,重新当成一颗树;回到第一步:break的原因
                            break;
                        }
                  }else{ //不存在右孩子时,直接访问该根结点,p指向上一层;继续循环
                    visit(pr->data);
                    p=pr;
                  }
            }//while end
            if(!p->parent) break;
                   
        }        
   }
}

2. 不借助栈的非递归后序遍历算法

【题目】假设在三叉链表的结点中增设一个标志域(mark取值0,1或2)以区分在遍历过程中到达该结点时应继续向左或向右或访问该结点。
试以此存储结构编写不用栈辅助的二叉树非递归后序遍历算法。

带标志域的三叉链表类型定义：
typedef struct TriTNode {
  TElemType  data;
  struct TriTNode  *lchild, *rchild, *parent;
  int       mark;  // 标志域
} TriTNode, *TriTree;

void PostOrder(TriTree T, void (*visit)(TElemType))
/* 不使用栈，非递归后序遍历二叉树T，   */
/* 对每个结点的元素域data调用函数visit */
{
    if(T==NULL) return;
    int fp=0;//from parent:遍历到时的来源,第一次遍历到时都是来自上一层
    int fl=1;//from left
    int fr=2;//from right
    TriTree p,pr;    
    p=T;
    while(p){
        switch(p->mark){
            case fp:
            {
                p->mark=fl;//第一次遍历到时,把来源置为左端
                if(p->lchild) p=p->lchild;
            }
            break;
            
            case fl:
            {
                p->mark=fr;//当遍历时的来源是左孩子时,把来源置为右端
                if(p->rchild) p=p->rchild;                
            }
            break;
            
            case fr:
            {
               visit(p->data);
               p->mark=fp;
               p=p->parent;
            }
            break;
        }
    }
}