#include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct BiThrNode{ char data; struct BiThrNode *lchild,*rchild; int ltag,rtag;//0为左右子树,1为线索 }BiThrNode,*BiThrTree; BiThrTree pre; char preoder[101]; int index=0; void create(BiThrTree *t){ if (preoder[index]==' ') { index++; *t=NULL; return ; }else{ *t=(BiThrTree)malloc(sizeof(BiThrNode)); (*t)->data=preoder[index]; index++; create(&(*t)->lchild); create(&(*t)->rchild); } } void inthreading(BiThrTree t){ if (t) { inthreading(t->lchild); if (t->lchild) { t->ltag=0; }else{ t->ltag=1; t->lchild=pre; } if (pre->rchild) { pre->rtag=0; }else{ pre->rtag=1; pre->rchild=t; } pre=t; inthreading(t->rchild); } } void inorderthreading(BiThrTree t,BiThrTree *thrt){ *thrt=(BiThrTree)malloc(sizeof(BiThrNode)); (*thrt)->rtag=1; (*thrt)->rchild=*thrt;//右线索先回指,最后再把它指向最后一个节点 (*thrt)->ltag=0;//ltag和rtag是确定的 if (!t) { (*thrt)->lchild=(*thrt); }else{ (*thrt)->lchild=t; pre=*thrt;//记录下头结点 inthreading(t);//中序遍历进行中序线索化 //最后一个节点线索化 pre->rtag=1; pre->rchild=(*thrt); (*thrt)->rtag=1; (*thrt)->rchild=pre;//头结点线索化 } } void inoder_thr(BiThrTree thrt){ BiThrTree p=thrt->lchild; while (p!=thrt) { while (p->ltag==0) { p=p->lchild; } printf("%c ",p->data); while (p->rtag==1&&p->rchild!=thrt) { p=p->rchild; printf("%c ",p->data); } p=p->rchild; } printf("\n"); } void print(BiThrTree t){ if (t) { print(t->lchild); printf("%c ",t->data); print(t->rchild); } } void clean_thr(BiThrTree thrt){ if (thrt) { if (thrt->ltag==0) { thrt->ltag=1;//否则会重复 clean_thr(thrt->lchild); } if (thrt->rtag==0) { thrt->rtag=1;// clean_thr(thrt->rchild); } free(thrt); } } void clean(BiThrTree t){ if (t) { clean(t->lchild); clean(t->rchild); free(t); } } int main(){ BiThrTree t,thrt; // freopen("1.txt","r",stdin); while (scanf("%[^\n]",preoder)!=EOF) { index=0; create(&t); // print(t); // printf("\n"); inorderthreading(t,&thrt); // print(t); // printf("\n"); inoder_thr(thrt); clean_thr(thrt); getchar(); } // fclose(stdin); return 0; } /************************************************************** Problem: 2155 User: admin Language: C Result: Accepted Time:11 ms Memory:1148 kb ****************************************************************/