[数据结构与算法]中序线索二叉树实现（带注释及测试文本）

#include<iostream>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char TElemType;

typedef enum{Link,Thread}PointerTag;
typedef struct BiThrNode{
  TElemType data;
  struct BiThrNode* lchild,*rchild;
  PointerTag LTag;
  PointerTag RTag;
}BiThrNode,*BiThrTree;
Status CreateBiThrNode(BiThrTree *B)
{
  char ch;
  scanf("%c",&ch);
  if(ch=='#')*B=NULL;
  else{
    if(!((*B)=(BiThrNode *)malloc(sizeof(BiThrNode))))
    {
      exit(0);
    }
    (*B)->data=ch;
    (*B)->LTag=Link;
    (*B)->RTag=Link;
    CreateBiThrNode(&(*B)->lchild);
    CreateBiThrNode(&(*B)->rchild);
  }
  return OK;
}
void InThreading(BiThrTree B,BiThrTree *pre)
{
    if(!B)return ;
    InThreading(B->lchild,pre);
    if(!B->lchild)//左边没孩子，lchild就是前驱
    {
      B->LTag=Thread;
      B->lchild=*pre;
    }
    if(!(*pre)->rchild)//递归完,pre为左子树最后一个节点
    {
      (*pre)->RTag=Thread;
      (*pre)->rchild=B;
    }
    //左子树和根节点安排妥了
    *pre=B;//pre对右子树来说是前驱节点
    InThreading(B->rchild,pre);//处理根节点和右子树的关系
}
Status InorderThrThreading(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);
    return OK;
  }
  BiThrTree pre;
  pre=(*Thrt);
  (*Thrt)->lchild=T;
  InThreading(T,&pre);
  //结束后pre是二叉树中序遍历的最后一个节点
  pre->rchild=*Thrt;
  pre->RTag=Thread;
  (*Thrt)->rchild=pre;
  return OK;
}
Status InOrderTraverse(BiThrTree T)
{
  BiThrNode *p=T->lchild;
  while(p!=T)
  {
    while(p->LTag==Link)p=p->lchild;
    printf("%c",&p->data);
    while(p->LTag==Thread&&p->rchild!=T)//终止条件为当前节点右子树不为空,即左子树遍历完成
    {
      p=p->rchild;
      printf("%c",p->data);
    }
    p=p->rchild;
  }
  return OK;
}
int main()
{
  BiThrTree B,T;
  //test:hda##c#b##gf#e###
  CreateBiThrNode(&B);
  InorderThrThreading(&T,B);
  printf("中序遍历：");
  InOrderTraverse(T);
  system("pause");
}