1 #include2 #include 3 4 typedef enum 5 { 6 Link, 7 Tread 8 }PointerTag; 9 10 typedef char TElemType; 11 12 typedef struct TreeNode 13 { 14 TElemType data; //数据单元 15 16 struct TreeNode *pLChild, *pRChild; //左右孩子指针 17 PointerTag LTag, RTag; //左右标志 ==0：孩子指针；==1：前后驱 18 }TreeNode, Tree; 19 20 TreeNode *gPre = NULL; 21 22 /* 先序创建二叉树 */ 23 void CreateTree(Tree **_t) 24 { 25 TElemType ch = -1; 26 27 scanf("%c", &ch); 28 29 if(ch == '#') 30 *_t = NULL; 31 else 32 { 33 *_t = (Tree*)malloc(sizeof(TreeNode)); 34 if(*_t == NULL) 35 return; 36 (*_t)->data = ch; 37 (*_t)->LTag = Link; 38 (*_t)->RTag = Link; 39 CreateTree(&((*_t)->pLChild)); 40 CreateTree(&((*_t)->pRChild)); 41 } 42 } 43 44 /* 遍历二叉树 */ 45 int InOrderThraverse_Thr(Tree *_t) 46 { 47 Tree *p =NULL; 48 49 p = _t->pLChild; 50 while(p != _t) 51 { 52 while(p->LTag == Link) 53 p = p->pLChild; 54 55 printf("%c ", p->data); //对节点的操作 56 57 while((p->RTag == Tread) && (p->pRChild != _t)) 58 { 59 p = p->pRChild; 60 61 printf("%c ", p->data); 62 } 63 p = p->pRChild; 64 } 65 66 return 0; 67 } 68 69 void InOrderThreading(Tree *_p) 70 { 71 if(_p) 72 { 73 InOrderThreading(_p->pLChild); //左树线索初始化 74 if(!_p->pLChild) //前驱线索 75 { 76 _p->LTag = Tread; 77 _p->pLChild = gPre; 78 } 79 if(!gPre->pRChild) //后继线索 80 { 81 gPre->RTag = Tread; 82 gPre->pRChild = _p; 83 } 84 gPre = _p; 85 86 InOrderThreading(_p->pRChild); //右子树线索初始化 87 } 88 } 89 90 /* 线索化二叉树 */ 91 int InOrderThread_Head(Tree **_h, Tree *_t) 92 { 93 (*_h) = (TreeNode *)malloc(sizeof(TreeNode)); 94 if(*_h == NULL) 95 return -1; 96 97 (*_h)->pRChild = *_h; 98 (*_h)->RTag = Link; 99 100 if(!_t)101 {102 (*_h)->pLChild = *_h;103 (*_h)->LTag = Link;104 }105 else106 {107 gPre = *_h;108 (*_h)->LTag = Link;109 (*_h)->pLChild = _t;110 InOrderThreading(_t);111 gPre->pRChild = *_h;112 gPre->RTag = Tread;113 (*_h)->pRChild = gPre;114 }115 116 return 0;117 }118 119 int main(void)120 {121 Tree *t=NULL, *temp=NULL;122 123 printf("请输入前序二叉树的内容：\n");124 CreateTree(&t);125 InOrderThread_Head(&temp, t); //加入头结点，并线索化 126 printf("输出中序二叉树的内容:\n"); 127 InOrderThraverse_Thr(temp); 128 129 printf("\n");130 return 0;131 }
mrrs@ubuntu:~/Desktop/DSC$ ./test请输入前序二叉树的内容：ABDG##H###CE#I##F##输出中序二叉树的内容:G D H B A E I C F