/************************************************************/
/* 按层次顺序建立一棵二叉树 */
/************************************************************/
#include"Bintree.h"

Bintree Level_Creat()
{
Bintree root,p,s;
queue node;
node.front=node.rear=0;
char ch;
ch=getchar();
if(ch==' ')
{
return NULL;
}
root=(Binnode*)malloc(sizeof(Binnode)); //生成根结点
root->data=ch;
node.data[node.rear++]=root; //用队列实现层次遍历
while(node.front<node.rear)
{
p=node.data[node.front++];
ch=getchar(); //为了简化操作，分别对左右子结点进行赋值。
if(ch!=' ')//子树不空则进队列进行扩充。下同
{
s=(Binnode*)malloc(sizeof(Binnode));
s->data=ch;
p->lchild=s;
node.data[node.rear++]=s;
}
else
{
p->lchild=NULL;
}
ch=getchar();
if(ch!=' ')
{
s=(Binnode*)malloc(sizeof(Binnode));
s->data=ch;
p->rchild=s;
node.data[node.rear++]=s;
}
else
{
p->rchild=NULL;
}
}
return root;
}
int main()
{
Bintree root;
root=Level_Creat();
Inorder1(root);//测试，中序遍历
return 0;
}

//中序穿线二叉树.
#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;
}