// 先序線索化.cpp : 定義控制臺應(yīng)用程序的入口點。
//

#include "stdafx.h"

typedef struct BiThrNode
{
	char data;
	struct BiThrNode *lchild,*rchild;
	int LTag,RTag;
}Btree;
Btree *T,*P,*pre;

Btree *CreateBiTree(Btree *T)//按先序序列先序建立二叉樹
{
	 char ch;
	 scanf("%c",&ch);
	 if (ch==' ')
		 T=NULL;
	 else {
		   T=(Btree *)malloc(sizeof(BiThrNode));
		   T->data=ch;
		   T->lchild=CreateBiTree(T->lchild);
		   T->rchild=CreateBiTree(T->rchild);
		   }
	 return (T);
}


Btree *PreThreading(Btree *P)//先序的線索化
{
   if (P)
	{
		if (P->lchild) {P->LTag=0;} 
		if (!P->lchild)
		    {P->LTag=1;P->lchild=pre;}
		if (P->rchild) {P->RTag=0;}
		if (!P->rchild) P->RTag=1;
		if (pre&&pre->RTag==1)
		    {pre->rchild=P;}
		    pre=P;
		if (P->LTag==0) PreThreading(P->lchild);
		if (P->RTag==0) PreThreading(P->rchild);
	}

	return (P);
}

void preorder(Btree *p)//遍歷先序線索二叉樹
{
	printf("%c",p->data);
	while (p->rchild)
	{
		if (p->LTag==0)
		{p=p->lchild;}
		else p=p->rchild;
		printf("%c",p->data);
	}
}


main()
{
 Btree *tree1;Btree *tree2;Btree *tree3; 
 tree1=NULL;tree2=NULL;tree3=NULL;
 printf("請輸入樹中的元素（輸入的必須是一個滿二叉樹，以空格表示空樹）：");
 tree2=CreateBiTree(tree1);
 tree3=PreThreading(tree2);
 printf("先序線索化以后的先序遍歷如下：");
 preorder(tree3);
 printf("\n");
}