6-4-2.txt

数据结构源程序

/*线索树的基本运算与实现*/
#include <stdio.h>
#define MAXNODE 256
typedef int datatype;
typedef struct BiThrNode
{
	datatype data;
	struct BiThrNode *lchild,*rchild;
	int ltag,rtag;
}BiThrNodeType,*BiThrTree;

void menu();
int Initiate(BiThrTree *bt,datatype x);
BiThrTree InsertL(BiThrTree bt,datatype x,BiThrTree parent);
BiThrTree InsertR(BiThrTree bt,datatype x,BiThrTree parent);
void PreOrder(BiThrTree bt);
void InOrder(BiThrTree bt);
void PostOrder(BiThrTree bt);
BiThrTree Find(BiThrTree parent,datatype a);
int InOrderThr(BiThrTree *head,BiThrTree T);
void InThreading(BiThrTree T,BiThrTree *pre);
void ThrInOrder(BiThrTree T);

main()
{
	int n,m=1;
	BiThrTree t,head;

	/*clrscr();*/
	while(m)
	{
		menu();
		scanf("%d",&n);
		switch(n)
		{
			case 1:{/*初始化*/
				int flag;
				datatype x;
				printf("please input head point x:\n");
				scanf("%d",&x);
				flag=Initiate(&t,x);
				if(flag==1)
					printf("\nInitiate success!");
				else
					printf("\nInitiate fail!");
				break;
				}
			case 2:{/*建立线索树*/
				int flag;
				flag=InOrderThr(&head,t);
				if(flag==1)
					printf("\nThread success!");
				else
					printf("\nThread fail!");
				break;
				}
			case 3:{/*插入结点x作为a的左孩子*/
				datatype a,x;/*x作为a的左孩子*/
				BiThrTree parent=t;
				printf("please input a and x:\n");
				scanf("%d%d",&a,&x);
				parent=Find(parent,a);
				parent=InsertL(t,x,parent);
				if(parent!=NULL)
					t=parent;
				break;
				}
			case 4:{/*插入结点x作为a的右孩子*/
				datatype a,x;/*x作为a的右孩子*/
				BiThrTree parent=t;
				printf("please input a and x:\n");
				scanf("%d%d",&a,&x);
				parent=Find(parent,a);
				parent=InsertR(t,x,parent);
				if(parent!=NULL)
					t=parent;
				break;
				}
			case 5:{/*递归先序遍历*/
				PreOrder(t);
				break;
				}
			case 6:{/*递归中序遍历*/
				InOrder(t);
				break;
				}
			case 7:{/*递归后序遍历*/
				PostOrder(t);
				break;
				}
			case 8:{/*线索化的中序遍历*/
				ThrInOrder(head);
				break;
				}
			case 0:m=0;
		}
	}
}
void menu()
{
	/*clrscr();*/
	printf("\n");
	printf("\t\t1.initiate\n\n");
	printf("\t\t2.create thread\n\n");
	printf("\t\t3.insert Left\n\n");
	printf("\t\t4.insert Right\n\n");
	printf("\t\t5.preorder\n\n");
	printf("\t\t6.inorder\n\n");
	printf("\t\t7.postorder\n\n");
	printf("\t\t8.inorder thread\n\n");
	printf("\t\t0.exit\n\n");
	printf("\n\n\n\tplease select:");
}
int Initiate(BiThrTree *bt,datatype x)
{
	if((*bt=(BiThrNodeType*)malloc(sizeof(BiThrNodeType)))==NULL)
		return 0;
	(*bt)->data=x;
	(*bt)->ltag=0;
	(*bt)->rtag=0;
	(*bt)->lchild=NULL;
	(*bt)->rchild=NULL;
	return 1;
}
BiThrTree InsertL(BiThrTree bt,datatype x,BiThrTree parent)
{
	BiThrTree p;
	if(parent==NULL)
	{
		printf("\nerror!\n");
		return NULL;
	}
	if((p=(BiThrNodeType*)malloc(sizeof(BiThrNodeType)))==NULL)
		return NULL;
	p->data=x;
	p->ltag=0;
	p->rtag=0;
	p->lchild=NULL;
	p->rchild=NULL;
	if(parent->lchild==NULL)
		parent->lchild=p;
	else
	{
		p->lchild=parent->lchild;
		parent->lchild=p;
	}
	return bt;
}
BiThrTree InsertR(BiThrTree bt,datatype x,BiThrTree parent)
{
	BiThrTree p;
	if(parent==NULL)
	{
		printf("\nerror!\n");
		return NULL;
	}
	if((p=(BiThrNodeType*)malloc(sizeof(BiThrNodeType)))==NULL)
		return NULL;
	p->data=x;
	p->ltag=0;
	p->rtag=0;
	p->lchild=NULL;
	p->rchild=NULL;
	if(parent->rchild==NULL)
		parent->rchild=p;
	else
	{
		p->rchild=parent->rchild;
		parent->rchild=p;
	}
	return bt;
}
void PreOrder(BiThrTree bt)
{
	if(bt==NULL)
		return;
	printf("%5d",bt->data);
	PreOrder(bt->lchild);
	PreOrder(bt->rchild);
}
void InOrder(BiThrTree bt)
{
	if(bt==NULL)
		return;
	InOrder(bt->lchild);
	printf("%5d",bt->data);
	InOrder(bt->rchild);
}
void PostOrder(BiThrTree bt)
{
	if(bt==NULL)
		return;
	PostOrder(bt->lchild);
	PostOrder(bt->rchild);
	printf("%5d",bt->data);
}
BiThrTree Find(BiThrTree parent,datatype a)
{
	BiThrTree p;
	if(parent==NULL)
		p=NULL;
	else if(parent->data==a)
		p=parent;
	else
	{
		p=Find(parent->lchild,a);
		if(p->data!=a)
			p=Find(parent->rchild,a);
	}
	return p;
}
int InOrderThr(BiThrTree *head,BiThrTree T)
{
	BiThrTree pre;
	*head=(BiThrNodeType*)malloc(sizeof(BiThrNodeType));
	if(*head==NULL)
	{
		return 0;
	}
	(*head)->data=-32767;
	(*head)->ltag=0;
	(*head)->rtag=1;
	(*head)->rchild=*head;
	if(T==NULL)
	{
		(*head)->lchild=*head;
	}
	else
	{
		(*head)->lchild=T;
		pre=*head;
		InThreading(T,&pre);
		pre->rchild=*head;
		pre->rtag=1;
		(*head)->rchild=pre;
	}
	return 1;
}
void InThreading(BiThrTree T,BiThrTree *pre)
{
	if(T)
	{
		InThreading(T->lchild,pre);
		if(!T->lchild)
		{
			T->ltag=1;
			T->lchild=*pre;
		}
		if(!((*pre)->rchild))
		{
			(*pre)->rtag=1;
			(*pre)->rchild=T;
		}
		*pre=T;
		InThreading(T->rchild,pre);
	} /* end if */
}
void ThrInOrder(BiThrTree T)
{
	BiThrTree p,post=T;
	p=T->lchild;
	while(p->ltag!=1)
	{
		p=p->lchild;
	}
	printf("%5d",p->data);
	while((p->rchild)!=T)
	{
		post=p->rchild;
		if(p->rtag!=1)
		{
			while(post->ltag==0)
			{
				post=post->lchild;
			}
		}
		p=post;
		printf("%5d",p->data);
	} /* end while */
	printf("\n");		
}