ln9.c

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

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

typedef struct node
{ datatype data;
  struct node *lchild,*rchild;
} bitree;
bitree *Q[maxsize],*S,*T,*L;

/*typedef struct
{ datatype data[maxsize];
  int top;
} seqstack;
seqstack *T,*L;
/*int j=0;*/

bitree *CREAT1()
{ int ch;
  int front,rear;
  bitree *root,*s;
  root=NULL;
  front=1; rear=0;
  printf("\n树:\n");
  scanf("%d",&ch);
  while(ch!=NULL)
  { s=NULL;
	if(ch!=-1)
	 { s=malloc(sizeof(bitree));
	   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);
  scanf("%d",&ch);
  }
  return(root);
}
/*
SETNULL(r)
seqstack *r;
{ r->top=-1;
}

seqstack *PUSH(m,n)
seqstack *m;
datatype n;
{ if(m->top==maxsize-1)
   { printf("overflow\n");
	 return(NULL);
   }
  else
   { m->top++;
	 m->data[m->top]=n;
   }
  return(m);
}

int POP(a)
seqstack *a;
{ if(a->top==-1)
   { printf("underflow\n");
	 return(NULL);
   }
  else
   { a->top--;
	 return(a->data[a->top+1]);
   }
}

seqstack *CREAT2()
{ int k=0;
  char r;
  seqstack *l;
  l=NULL;
  l->top=-1;
  printf("SEQSTACK:\n");
  scanf("%c",&ch);
  while(ch!='#')
  { l->top++;
	l->data[l->top]=ch;
	printf("%c\t",l->data[l->top]);
	j++;
	scanf("%c",&ch);
  }
  while(l->data[k]!=NULL && k<j+1)
  { l->top++;
	r=PUSH(l,p);
	printf("%c\t",r);
	j++;
  }
 return(l);
}

INORDER(bitree *t,bitree *p,seqstack *s)
{
  SETNULL(s);
  p=t;
  while(p->data!=NULL || s->top!=-1)
  { if(p!=NULL)
	 { PUSH(s,p->data);
	   p=p->lchild;
	 }
	else
	 { p->data=POP(s);
	   printf("%d\t",p->data);
	   p=p->rchild;
	 }
  }
}   */

INORDER(t)
bitree *t;
{ if(t!=NULL)
   { INORDER(t->lchild);
     printf("%d\t",t->data);
     INORDER(t->rchild);
   }
}

PREORDER(t)
bitree *t;
{ if(t!=NULL)
   { printf("%d\t",t->data);
     PREORDER(t->lchild);
     PREORDER(t->rchild);
   }
}

PORDER(t)
bitree *t;
{ if(t!=NULL)
   { PORDER(t->lchild);
     PORDER(t->rchild);
     printf("%d\t",t->data);
   }
}

main()
{
  S=CREAT1();
  T=S;
  L=T;
  printf("\n中序遍历:\n");
  INORDER(S);
  printf("\n前序遍历:\n");
  PREORDER(T);
  printf("\n后序遍历:\n");
  PORDER(L);
}