_tree.c

数据结构的全部课件（机密文件）

#include "conio.h"
#include"stdio.h"
#include"malloc.h"
struct  node
   { int  data;
     struct node  *lc,*rc;
   };
 typedef  struct node *bitreptr , *tpointer;

  tpointer  nar[20] ;
  int m,k,y;
 bitreptr  create (bitreptr  root)
   { 
	 int n,i,x,j,f;
      tpointer  p;
      scanf("%d",&n);
      for  (i=1; i<=n ; i++)
	{  scanf ("%d%d",&x,&j);
	    nar[j]=(tpointer)malloc(sizeof(struct node));
	    nar[j]->data=x; 
		nar[j]->lc=0; 
		nar[j]->rc=0;
	    if  (j==1)  
			root=nar[j];
		else  
		{  f=j / 2;
			if  (j % 2==0)  
				nar[f]->lc=nar[j];
			  else 
				  nar[f]->rc=nar[j];
		      }
	   }
	  return(root);
     };
void  inorder(bitreptr   p)
  { int top,bool;
    tpointer q;

    top=0; bool=0; q=p;
    while  (! bool)
     { if  (q!=0)
       {  nar[top+1]= q;  top++; q=q->lc; }
      else  { if  (top==0 )   bool=1;
	       else  { q=nar[top]; top--;
		      printf (q->data);
		      q=q->rc;
		    }
	    } 
    }
};

   void  inorder1(bitreptr   p)
      {
	   if  (p!= 0)
	   {   
		   inorder1 ( p->lc);
	      printf ( "   %    d",p->data);
	      inorder1 (p->rc);
	   }
      };
     void  preorder(bitreptr   p)
      {
	if  (p!= 0)
	  {   printf ( "   %    d",p->data);
	      preorder ( p->lc);

	      preorder (p->rc);
	  }
      };
     void  postorder(bitreptr   p)
      {
	if  (p!= 0)
	  {   postorder ( p->lc);

	      postorder (p->rc);
	       printf ( "   %    d",p->data);
	  }
      };

  void  layerscan ( bitreptr  p)
  {  
	  int front,rear; tpointer q;
      front=0; rear=0;
	nar[rear+1]=p; 
	rear=rear+1;
	while  (front!=rear)
	 { 
		front=front+1;
		q=nar[front];
	   if  (q!=0)
	     { 
		   printf ("   %   d", q->data);
	       if  (q->lc!=0 )   
		   { rear=rear+1; nar[rear]=q->lc;}
	       if  (q->rc!=0 )   
		   { rear=rear+1; nar[rear]=q->rc;} 
	      }
	   }
	};


    void  drawabt ( bitreptr  p)
    { 
		int front,rear,num[100],k,n,inter=40,layer; 
		tpointer q;
      front=0;
	  rear=0;
     nar[rear+1]=p; 
	 num[rear+1]=1;
	 rear=rear+1;
	 k=1;  
	 layer=1;
     while  (front!=rear)
	 { 
		 front=front+1;
		 q=nar[front]; 
		 n=num[front];
	   while (k<n) 
	   { k*=2;layer++;inter/=2;}

	   if (k>n) 
	   { k/=2; inter*=2;layer--;}
	   gotoxy(inter+2*(n-k)*inter,y+2*layer); printf("%3d",q->data);

	   if  (q->lc)   { rear=rear+1; nar[rear]=q->lc;num[rear]=2*n;};
	   if  (q->rc)   { rear=rear+1; nar[rear]=q->rc;num[rear]=2*n+1;} ;

	   }
	};
     bitreptr  create1 (bitreptr   p)
      {   
		 int x;
	  scanf ("%d",&x);
	    if  (x )
		{  p=(struct node *)malloc (sizeof(*p));
		   p->data=x;
		   p->lc= create1 (p->lc);
		   p->rc=create1 (p->rc);
		 }
	      else  p=0;
	 return(p);
	};


	 int  count ( bitreptr p)
	     {   if  (p== 0)  return(0);
		   else  return(1+count (p->lc)+ count (p->rc));

	      }
	  int  count0 ( bitreptr p)
	     {   if  (p== 0)  return(0);
		   else  if (p->lc==0 && p->rc==0)  return(1);
		    else  return(count0(p->lc)+count0(p->rc));

	      };
  int  count1 ( bitreptr p)
  {   if ( (p== 0) || (p->lc==0 && p->rc==0))  return(0);
    else  if (p->lc!=0 && p->rc!=0)  return(count1(p->lc)+count1(p->rc));
	else
	   return(1+count1(p->lc)+count1(p->rc));

	      }

	  int  count2 ( bitreptr p)
	     {   if ( (p== 0) || (p->lc==0 && p->rc==0))  return(0);
		   else  if (p->lc!=0 && p->rc!=0)  return(1+count2(p->lc)+count2(p->rc));
		      else
		      return(count2(p->lc)+count2(p->rc));

	      };
	  bitreptr  exch(bitreptr  p)
	  {   tpointer q;
	      if (p!=0)
		  {
		    p->lc=exch(p->lc);

		    p->rc=exch(p->rc);
		    q=p->lc;p->lc=p->rc; p->rc=q;
		  }
	     return p;
	  };

	  bitreptr copy (bitreptr p1,bitreptr p)
	  { if (p1!=0)
	      {   p=(struct node *)malloc (sizeof(*p));
		  p->data=p1->data;
		  p->lc= copy (p1->lc,p->lc);
		  p->rc=copy (p1->rc,p->rc);
		}
		  else  p=0;
	    return(p);
	  };


	   void drawavl(bitreptr  t,int  l,int n)
		{       int f,i,b,k;
			if (t!=0)
			     {  k=1;
				for (i=1;i<=l-1;i++)  k=k*2;
				    k=k-1;
				k=n-k;
				f=40;
			       for (i=1;i<=l-1;i++)
				 {
				   b=f;
				   f=f/2;
				 }
				 gotoxy(f+b*(k-1),y+2*(l-1));
				 printf("%d",t->data);
				drawavl(t->lc,l+1,2*n);drawavl(t->rc,l+1,2*n+1);
			      } 
			    };

	int  depth ( bitreptr  p )
	      { int d1,d2;
		 if  (p==0)  return(0);
		  else
		      {  d1= depth ( p->lc);
			 d2= depth ( p->rc);
			 return( 1+(d1>d2?d1:d2));
		      }
	       };

	main()
	{  
		bitreptr  root1,root2;
		  tpointer  p,q;
		  int i,j;
		     printf("\n\n\n");
		     root1=0;
		  root1=create(root1);

		  printf("\n");
		  clrscr();
		   y=wherey();
		 /* drawavl(root1,1,1);
		  root1=exch(root1);
		  printf("\n\n\n\n\n\n\n\n"); */
		   y=wherey();
		  drawabt(root);
		  return 1;
	}