线索二叉树算法

核心提示：#include <stdio.h>#include <malloc.h>#include<stdlib.h>typedef char DataType;/*定义DataType类型*/typedef enum {Link,Thread}PointerTag;typedef stru

#include <stdio.h>
#include <malloc.h>
#include<stdlib.h>
typedef char DataType;/*定义DataType类型*/
typedef enum {Link,Thread}PointerTag;
typedef struct node{
 DataType data;
 struct node *lchild, *rchild;/*左右孩子子树*/
 PointerTag LTag,RTag;
}BiThrNode; /*结点类型*/
typedef BiThrNode *BiThrTree ;/*二叉树类型*/
void  CreatBinTree(BiThrTree *T)
{ /*构造二叉链表,注意:输入序列是先序序列*/
 char ch;
 if ((ch=getchar())==' ')
　*T=NULL;
 else{ /*读入非空格*/
　*T=(BiThrNode *)malloc(sizeof(BiThrNode));/*生成结点*/
 (*T)->data=ch;(*T)->LTag=Link;(*T)->RTag=Link;
 CreatBinTree(&(*T)->lchild); /*构造左子树　  */
 CreatBinTree(&(*T)->rchild); /*构造右子树*/
 }
}
BiThrTree pre;/*全局变量*/
void InThreading(BiThrTree p)
{
 if(p)
 {InThreading(p->lchild);/*左子树线索化*/
 if(!p->lchild){p->LTag=Thread;p->lchild=pre;}/*前驱线索*/
 if(!pre->rchild){pre->RTag=Thread;pre->rchild=p;}/*后继线索*/
 pre=p;/*保持pre指向p*/
 InThreading(p->rchild);/*右子树线索化*/
 }
}
int InOrderThreading(BiThrTree *Thrt,BiThrTree T)
　　　　　　　　　　　　　　　　  /*中序遍厉二叉树T，并将其中序线索化，Thrt指向头结点*/
{ if(!(*Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(0);
  (*Thrt)->LTag=Link;(*Thrt)->RTag=Thread;/*建头结点*/
  (*Thrt)->rchild=*Thrt;/*右指针回指*/
  if(!T) (*Thrt)->lchild=*Thrt;
  else
  { (*Thrt)->lchild=T;pre=*Thrt;
　  InThreading(T);/*中序遍历进行中序线索化*/
 pre->rchild=*Thrt;pre->RTag=Thread;/*最后一个结点线索化*/
 (*Thrt)->rchild=pre;
  }
  return 1;
}
int print(BiThrTree e)
{printf("%d  %c  %d\n",e->LTag,e->data,e->RTag);return 1;}

int InOrderTraverse(BiThrTree T,int (* visit)(BiThrTree e))
　　　　　　　　　　　　　　　　  /*T指向头结点，头结点的左链lchild指向根结点，中序遍厉二叉树*/
{BiThrTree p;
 p=T->lchild;/*p指向根结点*/
 while(p!=T)/*空树或遍厉结束时，p==T*/
 {while(p->LTag==Link) p=p->lchild;
  if(!visit(p)) return 0;/*打印*/
  while(p->RTag==Thread&&p->rchild!=T)
  {p=p->rchild;visit(p);}/*访问后继结点*/
  p=p->rchild;
 }
 return 1;
}
void main()
{ /*测试程序*/
 BiThrTree T,Thrt;
 CreatBinTree(&T);
　  InOrderThreading(&Thrt,T);
　  InOrderTraverse(Thrt,print);
}
/*可输入"-+a  *b  -c  d  /e  f  "来测试(注意空格)*/