【数据结构】线索二叉树之后序线索化

思路

后序线索化二叉树是一种将二叉树转化为一个线性结构的方法，通过给每个结点添加线索（指向前驱结点和后继结点的指针）来实现。后序线索化二叉树的思路如下：

1. 遍历到一个结点时，如果它有左孩子，就递归进入左子树。

2. 如果它有右孩子，就递归进入右子树。

3. 如果它没有左孩子，则将左指针线索化为前驱结点。

4. 如果它没有右孩子，则将右指针线索化为后继结点。

5. 最后一个遍历到的结点，将它的右指针线索化为后继结点（默认为空）。

具体实现时，可以用一个全局变量来保存前驱结点，每遍历一个结点时，将它的左指针指向前驱结点，并将前驱结点的右指针指向它。处理完左子树后，将前驱结点更新为当前结点，再递归进入右子树。处理完右子树后，将当前结点的右指针指向后继结点，再将后继结点更新为当前结点。最后遍历到的结点的右指针指向后继结点（默认为空）。

找第一个结点

从根结点开始，向左走到尽头，若无右子树，则该结点为所求，否则，后序序列第一个结点为右子树后序序列的第一个结点。

BiThrTree First(BiThrTree p)
{
  if(!p)
    return NULL;
  while(p->LTag==Link)
    p=p->lchild;
  if(p->RTag==Thread)
    return p;
  else
  {
    p=p->rchild;
    return First(p);
  }
}

怎么找后继

若P指向根，则无后继；

若*p为其双亲的右孩子，则后继为双亲；

若*p是其双亲的左孩子且双亲没有右子树，则其后继是其双亲；

若*p是其双亲的左孩子且双亲有右子树，则其后继是双亲右子树后序序列的第一个结点。

BiThrTree succ(BiThrTree T,BiThrTree p)
{
  BiThrTree f;
  if(p==T)
    return NULL;
  if(p->RTag==Thread)
    return p->rchild;
  f=parent(T,p);
  if(f->rchild==p)
    return f;
  if(f->lchild==p&&f->RTag==Thread)
    return f;
  if(f->lchild==p&&f->RTag==Link)
    return First(f->rchild);
}

怎么找前导

若p->LTag为Thread,则前导为p->lchild;

若p->LTag,表明p有左子树。因为后序遍历为左右根，若p没有右子树，则前导为左子树后序序列的最后一个结点，即左子树的根，即*p的左孩子。

若*p有右子树，则前导为右孩子。

代码实现

#include <stdio.h>
#include <stdlib.h> 


typedef char TElemType;
typedef enum PointerTag {Link,Thread} PointerTag;

typedef struct BiThrNode{
  TElemType data;
  struct BiThrNode *lchild,*rchild;
  PointerTag  LTag,RTag;
}BiThrNode,*BiThrTree;

BiThrTree pre;
void InThreading(BiThrTree);

Status CreateBiTree(BiThrTree *T){
  char ch;

  ch=getchar();
  if(ch=='#') *T=NULL;
  else{
    *T=(BiThrNode*) malloc (sizeof(BiThrNode));
    if(!*T) exit(OVERFLOW);
    (*T)->data=ch;
    (*T)->LTag=Link;
    (*T)->RTag=Link;
    CreateBiTree(&(*T)->lchild);
    CreateBiTree(&(*T)->rchild);
  }
  return OK;
}

Status PostOrderTraverse(BiThrTree T,Status (*visit)(TElemType e)){
  if(T){
    PostOrderTraverse(T->lchild,visit);
    PostOrderTraverse(T->rchild,visit);
    (*visit)(T->data);
  }
  else  return OK;
}


Status PrintElement(TElemType e){
  putchar(e);
  return OK;
}

Status PostThreading(BiThrTree *Thrt,BiThrTree T){
   if(!((*Thrt)=(BiThrTree) malloc(sizeof(BiThrNode))))  exit(OVERFLOW);
   (*Thrt)->LTag=Link;  (*Thrt)->RTag=Thread;
   (*Thrt)->rchild=*Thrt;

   if(!T) (*Thrt)->lchild=*Thrt;
   else{
       (*Thrt)->lchild=T;
       pre= (*Thrt);
       InThreading(T);
       (*Thrt)->rchild = pre;
       if(!pre->rchild) { pre->RTag=Thread; pre->rchild=(*Thrt);}
   }
}

void InThreading(BiThrTree p){

    if(p){
       InThreading(p->lchild);
       InThreading(p->rchild);
       if(!p->lchild) {p->LTag = Thread; p->lchild=pre;}
       if(!pre->rchild) {pre->RTag=Thread; pre->rchild=p;}
       pre=p;
    }
}
BiThrTree First(BiThrTree p){

   if(p){
       while(p->LTag==Link) p=p->lchild;
       if(p->RTag==Thread)
	  return p;
       else{
	  p=p->rchild;
	  First(p);
       }
   }

}

BiThrTree parent(BiThrTree T,BiThrTree p){

     BiThrTree Q[100],t;
     int f=0,r=0;

     r++; Q[r]=T;
     while(f!=r){
        f++; t=Q[f];
        if(t->lchild==p || t->rchild==p)
          return t;
        if(t->LTag==Link) {r++;Q[r]=t->lchild;}
        if(t->RTag==Link) {r++;Q[r]=t->rchild;}

     }
}

BiThrTree succ(BiThrTree T,BiThrTree p){
    BiThrTree f;

    if(p==T)  return 0;
    if(p->RTag==Thread) return p->rchild;
    f=parent(T,p);
    if(f->rchild==p) return f;
    if(f->lchild==p && f->RTag==Thread) return f;
    if(f->lchild==p && f->RTag==Link){
       return First(f->rchild);
    }


}

main()
{
  BiThrTree T,Th,p,f;
  char ch;
  
  CreateBiTree(&T);
  PostOrderTraverse(T,PrintElement);

  PostThreading(&Th,T);
  putchar('\n');

  p=First(T);
  printf("The First Node is:%c\n",p->data);

  f=parent(T,p);
  printf("parent  is:%c",f->data);

  printf("\nsucc is:%c\n",succ(T,p)->data);

  for(p=First(T);p!=Th&&p;p=succ(T,p))
    printf("%c",p->data);

  putchar('\n');

}