线索二叉树算法 .pdf

线索二叉树算法 #include #include #include 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 "来测试(注意空格)*/