CH5_20.C
上传用户:lgb298
上传日期:2013-03-22
资源大小:1025k
文件大小:2k
源码类别:

软件工程

开发平台:

C/C++

  1. #include <alloc.h>
  2. #include <stdio.h>
  3. #define M 10
  4. typedef struct node
  5. {  char data;
  6.    int lt,rt;
  7.    struct node *lc,*rc;
  8. }JD;
  9. JD *zxxsh(JD *bt)
  10. {  JD *p,*pr,*s[M],*t;
  11.    int i=0;
  12.    t=(JD *)malloc(sizeof(JD));
  13.    t->lt=0;
  14.    t->rt=1;
  15.    t->rc=t;
  16.    if(bt==NULL)
  17.       t->lc=t;
  18.    else
  19.    {  t->lc=bt;
  20.       pr=t;
  21.       p=bt;
  22.       do
  23.       {   while(p!=NULL)
  24.   {   s[i++]=p;
  25.       p=p->lc;
  26.   }
  27.   if(i>0)
  28.   {   p=s[--i];
  29.       printf("%c  ",p->data);
  30.       if(p->lc==NULL)
  31.       {   p->lt=1;
  32.   p->lc=pr;
  33.       }
  34.       if(pr->rc==NULL)
  35.       {   pr->rt=1;
  36.   pr->rc=p;
  37.       }
  38.       pr=p;
  39.       p=p->rc;
  40.   }
  41.       }while(i>0||p!=NULL);
  42.       pr->rc=t;
  43.       pr->rt=1;
  44.       t->rc=pr;
  45.    }
  46.    return(t);
  47. }
  48. void zxblxss(JD *t)
  49. {   JD *p;
  50.     p=t->lc;
  51.     do
  52.     {   while(p->lt==0)
  53.    p=p->lc;
  54. printf("%c  ",p->data);
  55. while((p->rt==1)&&(p->rc!=t))
  56. {   p=p->rc;
  57.    printf("%c  ",p->data);
  58. }
  59. p=p->rc;
  60.     }while(p!=t);
  61. }
  62. void zxblxss_2(JD *t)
  63. {   JD *p;
  64.     p=t->rc;
  65.     do
  66.     {   printf("%c  ",p->data);
  67. while((p->lt==1)&&(p->lc!=t))
  68. {   p=p->lc;
  69.    printf("%c  ",p->data);
  70. }
  71. p=p->lc;
  72. while(p->rt==0)
  73.    p=p->rc;
  74.     }while(p!=t);
  75. }
  76. JD *crt_bt_pre(JD *bt)
  77. {  char ch;
  78.    printf("ch=");
  79.    scanf("%c",&ch);
  80.    getchar();
  81.    if(ch==' ')  bt=NULL;
  82.    else
  83.    {   bt=(JD *)malloc(sizeof(JD));
  84.        bt->data=ch;
  85.        bt->lt=bt->rt=0;
  86.        bt->lc=crt_bt_pre(bt->lc);
  87.        bt->rc=crt_bt_pre(bt->rc);
  88.    }
  89.    return(bt);
  90. }
  91. void main()
  92. {  JD *head=NULL;
  93.    JD *t;
  94.    head=crt_bt_pre(head);
  95.    head=zxxsh(head);
  96.    printf("n");
  97.    zxblxss(head);
  98.    printf("n");
  99.    zxblxss_2(head);
  100. }