线索二叉树就是把左或者右孩子为空的位置，设置为前驱或者后继 因为中序遍历第一个元素是C，没有前驱，最后一个元素F也没有后继，所以我们设置一个头结点，C的前驱和F的后继都指向投节点，头节点的前驱为根节点，后继为最后一个元素F。
#include"stdio.h" #include"stdlib.h" //线索标志位 //link表示指向左右孩子 //thread表示指向前驱后继 enum{link, thread}; //二叉树结构体 struct btree { char data; struct btree *lchild, *rchild; int ltag, rtag; }; //全局变量，指向刚访问过的结点 struct btree *pre; //用户按照前序遍历方式创建二叉树 void create_btree(struct btree **T) { char c; *T = (struct btree *)malloc(sizeof(struct btree)); scanf("%c", &c); if(' ' == c) { *T = NULL; } else { (*T)->data = c; //线索标志位全部初始化为link (*T)->ltag = link; (*T)->rtag = link; create_btree(&(*T)->lchild); create_btree(&(*T)->rchild); } } //中序遍历二叉树，更改线索标志位以及前驱后继 void inthread(struct btree *T) { if(T) { inthread(T->lchild); //如果左孩子为空，线索标志位改为thread，lchild指向前驱 //中序遍历二叉树的第一个结点的前驱为头结点 if(!(T->lchild)) { T->ltag = thread; T->lchild = pre; } //如果右孩子为空，线索标志位改为thread，rchild指向后继 //中序遍历二叉树的最后一个结点的后继为头结点 if(!(pre->rchild)) { pre->rtag = thread; pre->rchild = T; } //pre为刚访问过的结点 pre = T; inthread(T->rchild); } } //创建头节点，并让pre初始化为头结点 void inordthread(struct btree **P, struct btree *T) { //初始化头结点 (*P) = (struct btree *)malloc(sizeof(struct btree)); //头结点左标志位为link，左孩子为二叉树根结点 //头结点右标志位为thread，后继初始化为自己，后面会设置为二叉树最后一个结点 (*P)->ltag = link; (*P)->rtag = thread; (*P)->lchild = T; (*P)->rchild = *P; if(!T) { (*P)->lchild = *P; } else { //pre初始化为头结点 pre = *P; inthread(T); //中序遍历二叉树的最后一个结点的标志位为thread //后继为头结点 pre->rtag = thread; pre->rchild = *P; //头结点的后继为最后一个结点 (*P)->rchild = pre; } } //打印中序遍历二叉树 void visit(char c) { printf("%c", c); } //使用线索中序遍历二叉树 void inordtraversal(struct btree *P) { //临时结点p2，初始化为根结点 struct btree *p2; p2 = P->lchild; //若p2不等于头结点，说明遍历没有完成 while(p2 != P) { //p2有左孩子，一直往下遍历 while(p2->ltag == link) { p2 = p2->lchild; } visit(p2->data); //若没有右孩子且后继不为头结点，p2等于p2的后继(一直往后走) while(p2->rtag == thread && p2->rchild != P) { p2 = p2->rchild; visit(p2->data); } //若没有后继，p2等于p2的右孩子 p2 = p2->rchild; } } int main() { struct btree *P, *T; create_btree(&T); inordthread(&P, T); inordtraversal(P); printf("\n"); return 0; }第一行是输入，第二行是中序遍历输出。
