学步园

#include<stdio.h>
#include<stdlib.h>

typedef struct tree
{
	int data;
	struct tree *lchild,*rchild;

	int lflag,rflag;			//左右标记：lflag=1当前节点左孩子指向前驱，
								//rflag=1右孩子指向当前节点后继
}bitree,*ptree;

//先序创建二叉树
int creattree(ptree *T)
{
	int data;
	scanf("%d",&data);
	if(data == 0)(*T) = NULL;
	else
	{
		(*T) = (ptree)malloc(sizeof(bitree));
		if(!(*T)){printf("operate error.\n");exit(1);}
		(*T)->data = data;
		(*T)->lflag = 0;		//树的节点左右标记为0
		(*T)->rflag = 0;
		creattree(&(*T)->lchild);
		creattree(&(*T)->rchild);
	}
	return 1;
}


//中序线索二叉树
void inthreading(ptree root,ptree *pre)
{
	if(root)
	{
		inthreading(root->lchild,&(*pre));
		if(!root->lchild)
		{
			root->lchild = (*pre);
			root->lflag = 1;
		}
		if(!(*pre)->rchild)
		{
			(*pre)->rchild = root;
			(*pre)->rflag = 1;
		}
		(*pre) = root;
		inthreading(root->rchild,&(*pre));
	}
}

//建立头结点，中序线索二叉树
void inthreadingwithhead(ptree head,ptree root)
{
	ptree pre;
	head->lflag = head->rflag = 1;
	head->data = 0;
	head->rchild = head;
	if(!root)
	{
		head->lchild = NULL;
	}
	else
    {
		head->lchild = root;
        pre = head;
        inthreading(root,&pre);
        pre->rchild = head;
        pre->rflag = 1;
        head->rchild = pre;
    }
}

//中序线索遍历二叉树
void inordertraverse(ptree head)
{

    if(head)
    {
        if(head->lflag == 0)
			inordertraverse(head->lchild);
		printf("%d ",head->data);
		if(head->rflag == 0)
			inordertraverse(head->rchild);
    }
	return ;
}

int main()
{
	ptree root;
	bitree head;
	creattree(&root);
	inthreadingwithhead(&head,root);
	printf("中序遍历结果为：\n");
	inordertraverse(head.lchild);
	printf("\n");
	return 0;
}