//中序穿线二叉树.
#include<stdio.h>
#include<malloc.h>

typedef struct Binnode {
char data;
int lflag,rflag;//左右标记
/*
lflag=0 表示结点的左指针指向其左子女。
lflag=1 表示结点的左指针指向其中序遍历的前驱。
rflag=0 表示结点的左指针指向其右子女。
rflag=1 表示结点的左指针指向其中序遍历的前驱。
*/
struct Binnode *lchild,*rchild;
};
typedef Binnode* Bintree;

Bintree pre=NULL; //初始化前驱结点

/*******************************************/
/* 按照前序遍历建立二叉树 */
/*******************************************/

void Creat_Bintree(Bintree *root)
{
char ch;
if((ch=getchar())==' ')
{
*root=NULL;

}
else
{
*root=(Binnode*)malloc(sizeof(Binnode));
(*root)->data=ch;
Creat_Bintree(&(*root)->lchild);
Creat_Bintree(&(*root)->rchild);
}
}

/*******************************************/
/* 对二叉树进行中序穿线 */
/*******************************************/
void Inthreading(Bintree *t)
{
if(*t)
{
Inthreading(&(*t)->lchild);// 中序线索化左子树
(*t)->lflag=((*t)->lchild)?0:1;//对当前结点及其前驱结点进行穿线
(*t)->rflag=((*t)->rchild)?0:1;
if(pre)
{
if((*t)->lflag==1) (*t)->lchild=pre;
if(pre->rflag==1) pre->rchild=*t;
}
pre=*t;
Inthreading(&(*t)->rchild);// 中序线索化右子树
}
}

/*******************************************/
/* 中序遍历穿线二叉树 */
/*******************************************/

Bintree Insuccnode(Bintree p) //寻找结点P在中序遍历下的后继结点
{
Bintree q;
if(p->rflag==1)//P的右指针为线索，恰巧指向P的后继结点
{
return p->rchild;
}
else //寻找P的右子树中最左下的结点
{
q=p->rchild;
while(q->lflag==0)
{
q=q->lchild;
}
return q;
}
}

/********************************************************/
/* 中序遍历中序穿线二叉树 */
/********************************************************/

void Inthrtree(Bintree p)
{
if(p)
{
while(p->lflag==0) //求P中序遍历下的第一个结点
{
p=p->lchild;
}
do
{
printf("%-3c",p->data);
p=Insuccnode(p); //求P中序遍历下的后继结点
}
while(p);
}
}

int main()
{
Bintree t;
Creat_Bintree(&t);
Inthreading(&t);
Inthrtree(t);
printf("\n\n");
return 0;
}

谢了