ln10.c

有关数据结构的一些例子。用C语言编写的。非常有价值的程序。对初学者有指导借鉴意义。

#define NULL 0
#define maxsize 64
#include "stdio.h"
//#include "alloc.h"
typedef int datatype;

typedef struct node
{ int ltag,rtag;
  datatype data;
  struct node *lchild,*rchild;
} bithptr;
bithptr *Q[maxsize],*S,*T,*L,*M;
bithptr *pre=NULL;

bithptr *CREAT1()
{ int ch;
  int front,rear;
  bithptr *root,*s;
  root=NULL;
  front=1; rear=0;
  printf("\n树:\n");
  scanf("%d",&ch);
  while(ch!=NULL)
  { s=NULL;
	if(ch!=-1)
	 { s=(struct node *)malloc(sizeof(bithptr));
	   s->data=ch;
	   s->lchild=NULL;
	   s->rchild=NULL;
	 }
	rear++;
	Q[rear]=s;
	if(rear==1)
	  root=s;
	else
	{ if(s!=NULL && Q[front]!=NULL)
		if(rear%2==0)
		  Q[front]->lchild=s;
		else
		  Q[front]->rchild=s;
	  if(rear%2==1)
		front++;
	}
  printf("%d\t",s->data);
  printf("%d\n",s);
  scanf("%d",&ch);
  }
  return(root);
}

INTHREAD(p)
bithptr *p;
{
   p->ltag=0;
   p->rtag=0;
   if(p!=NULL)
   { INTHREAD(p->lchild);
	 if(p->lchild==NULL)
		p->ltag=1;
	 else
		p->ltag=0;
	 if(p->rchild==NULL)
		p->rtag=1;
	 else
		p->ltag=0;
	 if(pre!=NULL)
	 { if(pre->rtag==1)
		  pre->rchild=p;
	   if(p->ltag==1)
		  p->lchild=pre;
	 }
  pre=p;
  INTHREAD(p->rchild);
   }
}

bithptr *INORDERN(p)
bithptr *p;
{ bithptr *q;
  if(p->rtag==1)
	return(p->rchild);
  else
  { q=p->rchild;
	while(q->ltag==0)
	  q=q->lchild;
	return(q);
  }
}

bithptr *INORDERP(p)
bithptr *p;
{ bithptr *q;
  if(p->ltag==1)
	 return(p->lchild);
  else
  { q=p->lchild;
	while(q->rtag==0)
	  q=q->rchild;
	return(q);
  }
}

TRINTHRE(p)
bithptr *p;
{ if(p!=NULL)
  { while(p->ltag==0)
	 p=p->lchild;
	do
	 { printf("%d\t",p->data);
	   p=INORDERN(p);
	 } while(p!=NULL);
  }
}

main()
{ 
  bithptr *l;
  S=CREAT1();
  INTHREAD(S);
  printf("GET next:\n");
  scanf("%d",&l);
  printf("The next is:\n");
  T=INORDERN(l);
  printf("%d\t",T->data);
  printf("%d\n",T);
  printf("The prior is:\n");
  L=INORDERP(l);
  printf("%d\t",L->data);
  printf("%d\n",L);
  printf("TRAVERSEINTHREAD:\n");
  TRINTHRE(S);
}