xiansuo.c

win3 console 平台下程序

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#define N 50

typedef struct treenode
{
	int data;
	struct treenode *lchild,*rchild,*parent;
	int ltag,rtag;
}PTREENODE,*PTREENODEPTR;

PTREENODEPTR pre;

void creattree(PTREENODEPTR *root)
{
	int value,front,rear;
	PTREENODEPTR t,q[N];
	scanf("%d",&value);
	if(value)
	{
		(*root)=(PTREENODEPTR)malloc(sizeof(PTREENODE));
		(*root)->data=value;
		(*root)->parent=NULL;
		front=rear=1;
		q[front]=*root;
	}
	else{
		printf("input error\n");
		return;
	}
	while(rear<=front)
	{
		t=q[rear];
		rear++;
		fflush(stdin);
		scanf("%d",&value);
		if(value==0){
			t->lchild=NULL;
			t->ltag=1;
		}
		else{
			t->lchild=(PTREENODEPTR)malloc(sizeof(PTREENODE));
			t->lchild->data=value; t->lchild->parent=t; t->ltag=0;
			front++; q[front]=t->lchild;
		}
		fflush(stdin);
		scanf("%d",&value);
		if(value==0){
			t->rchild=NULL;
			t->rtag=1;
		}
		else
		{
			t->rchild=(PTREENODEPTR)malloc(sizeof(PTREENODE));
			t->rchild->data=value; t->rchild->parent=t; t->rtag=0;
			front++; q[front]=t->rchild;
		}
	}
}

void inthreading (PTREENODEPTR p)
{
	if(p)
	{
		inthreading(p->lchild);
		if(!p->lchild)
		{
			p->ltag=1;
			p->lchild=pre;
		}
		if(!pre->rchild)
		{
			pre->rtag=1;
			pre->rchild=p;
		}
		pre=p;
		inthreading(p->rchild);
	}
}

void inorthrea(PTREENODEPTR *thrt,PTREENODEPTR t)
{
	(*thrt)=(PTREENODEPTR)malloc(sizeof(PTREENODE));
	(*thrt)->ltag=0;
	(*thrt)->rtag=1;
	(*thrt)->rchild=(*thrt);
	if(!t)
		(*thrt)->lchild=(*thrt);
	else
	{
		(*thrt)->lchild=t;
		pre=(*thrt);
		inthreading(t);
		pre->rchild=(*thrt);
		pre->rtag=1;
		(*thrt)->rchild=pre;
	}
}


int tinorder(PTREENODEPTR thrt)
{
	PTREENODEPTR p;             
	int count=0;
	p=thrt->lchild;
	while(p!=thrt)
	{
		while(p->ltag==0)
			p=p->lchild;
		printf("%3d",p->data);
		count++;
		while(p->rtag==1&&p->rchild!=thrt)
		{
			p=p->rchild;
			printf("%3d",p->data);
			count++;
		}
		p=p->rchild;
	}
	return count;
}

void destroy(PTREENODEPTR thrt)//线索化毁树
{
	PTREENODEPTR  p;
	p=thrt->lchild;
	while(p!=thrt)
	{
		while(p->ltag==0)
		{
			p=p->lchild;
		}
		pre=p;
		while(p->rtag==1&&p->rchild!=thrt)
		{
			p=p->rchild;
			free(pre);
			pre = p;
		}
		pre = p;
		p=p->rchild;
		free(pre);
	}
}


void main()
{
	PTREENODEPTR root,thrt;
	int count;

	creattree(&root);
	inorthrea(&thrt,root);
	count=tinorder(thrt);
	printf("\nThere're %3d elems in the tree.",count);
	destroy(root);
	free(thrt);
	getch();
}