SDUT 2136、2137 二叉树的建立与各种遍历-白红宇

SDUT 2136、2137 二叉树的建立与各种遍历

阅读量：5010 次

发布时间：2019-06-12

本文共 2668 字，大约阅读时间需要 8 分钟。

暑假就没看二叉树这块。

2136

数据结构实验之二叉树的建立与遍历

View Code

1 #include
      
        2 #include
       
         3 #include
        
          4 struct node 5 { 6     int data; 7     struct node *l,*r; 8 }; 9 struct node *t;10 int count=0;11 struct node *creat(struct node *t)//建树12 {13     char ch;14     scanf("%c",&ch);15     if(ch==',')16     {17         return NULL;18     }19     else20     {21         t=(struct node*)malloc(sizeof(struct node));22         t->data=ch;23         t->l=creat(t->l);24         t->r=creat(t->r);25     }26     return t;27 }28 void inorder(struct node *t)//中序遍历29 {30     if(t)31     {32         inorder(t->l);33         printf("%c",t->data);34         inorder(t->r);35     }36 }37 void postorder(struct node *t)//后序遍历38 {39     if(t)40     {41         postorder(t->l);42         postorder(t->r);43         printf("%c",t->data);44     }45 }46 void leaf(struct node *t)//求叶子节点47 {48     if(t)49     {50         if(t->l==NULL&&t->r==NULL)51         count++;52         leaf(t->l);53         leaf(t->r);54     }55 }56 int deep(struct node *t)//求深度57 {58     int lchild,rchild;59     if(!t)60     return 0;61     lchild=deep(t->l);62     rchild=deep(t->r);63     return lchild>rchild?lchild+1:rchild+1;64 }65 int main()66 {67     struct node *s;68     int num;69     s=creat(t);70     inorder(s);71     printf("\n");72     postorder(s);73     printf("\n");74     leaf(s);75     printf("%d\n",count);76     num=deep(s);77     printf("%d\n",num);78     return 0;79 }

2137

数据结构实验之求二叉树后序遍历和层次遍历

BFS一直不大会用。唉。

View Code

1 #include
      
        2 #include
       
         3 #include
        
          4 struct node 5 { 6     char data; 7     struct node *l,*r; 8 }; 9 struct node *t;10 struct node *creat(char *pre,char *in ,int len)//建立二叉树11 {12     int k;13     if(len<=0)14     return NULL;15     struct node *head;16     head=(struct node*)malloc(sizeof(struct node));17     head->data= *pre;18     char *p;19     for(p=in;p!=NULL;p++)20     {21         if(*p == *pre)22         break;23     }24     k=p-in;25     head->l=creat(pre+1,in,k);26     head->r=creat(pre+k+1,p+1,len-k-1);27     return head;28 }29 void postorder(struct node *t)//后序遍历30 {31     if(t)32     {33         postorder(t->l);34         postorder(t->r);35         printf("%c",t->data);36     }37 }38 void lorder(struct node *t)//层次遍历39 {40     int front=0,rear=1,ans[100],n=0,i;41     struct node * q[100];42     q[0]=t;43     while(front
         
          data;47         if(t->l!=NULL) q[rear++]=t->l;48         if(t->r!=NULL) q[rear++]=t->r;49     }50     for(i=0;i