ch5_20.c

数据结构的一些小算法

#include <alloc.h>
#include <stdio.h>
#define M 10
typedef struct node
{  char data;
   int lt,rt;
   struct node *lc,*rc;
}JD;

JD *zxxsh(JD *bt)
{  JD *p,*pr,*s[M],*t;
   int i=0;
   t=(JD *)malloc(sizeof(JD));
   t->lt=0;
   t->rt=1;
   t->rc=t;
   if(bt==NULL)
      t->lc=t;
   else
   {  t->lc=bt;
      pr=t;
      p=bt;
      do
      {   while(p!=NULL)
	  {   s[i++]=p;
	      p=p->lc;
	  }
	  if(i>0)
	  {   p=s[--i];
	      printf("%c  ",p->data);
	      if(p->lc==NULL)
	      {   p->lt=1;
		  p->lc=pr;
	      }
	      if(pr->rc==NULL)
	      {   pr->rt=1;
		  pr->rc=p;
	      }
	      pr=p;
	      p=p->rc;
	  }
      }while(i>0||p!=NULL);
      pr->rc=t;
      pr->rt=1;
      t->rc=pr;
   }
   return(t);
}

void zxblxss(JD *t)
{   JD *p;
    p=t->lc;
    do
    {   while(p->lt==0)
	   p=p->lc;
	printf("%c  ",p->data);
	while((p->rt==1)&&(p->rc!=t))
	{   p=p->rc;
	   printf("%c  ",p->data);
	}
	p=p->rc;
    }while(p!=t);
}

void zxblxss_2(JD *t)
{   JD *p;
    p=t->rc;
    do
    {   printf("%c  ",p->data);
	while((p->lt==1)&&(p->lc!=t))
	{   p=p->lc;
	   printf("%c  ",p->data);
	}
	p=p->lc;
	while(p->rt==0)
	   p=p->rc;

    }while(p!=t);
}

JD *crt_bt_pre(JD *bt)
{  char ch;
   printf("ch=");
   scanf("%c",&ch);
   getchar();
   if(ch==' ')  bt=NULL;
   else
   {   bt=(JD *)malloc(sizeof(JD));
       bt->data=ch;
       bt->lt=bt->rt=0;
       bt->lc=crt_bt_pre(bt->lc);
       bt->rc=crt_bt_pre(bt->rc);
   }
   return(bt);
}

void main()
{  JD *head=NULL;
   JD *t;
   head=crt_bt_pre(head);
   head=zxxsh(head);
   printf("\n");
   zxblxss(head);
   printf("\n");
   zxblxss_2(head);
}