暑假就没看二叉树这块。
2136
数据结构实验之二叉树的建立与遍历
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2136
View Code
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 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 else 20 { 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
数据结构实验之求二叉树后序遍历和层次遍历
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2137
BFS一直不大会用。唉。
View Code
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 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<rear) 44 { 45 t =q[front++]; 46 ans[n++]=t->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<n;i++) 51 { 52 printf("%c",ans[i]); 53 } 54 } 55 int main() 56 { 57 struct node *h; 58 int n,len; 59 char pre[100],in[100]; 60 h=(struct node*)malloc(sizeof(struct node)); 61 scanf("%d",&n); 62 while(n--) 63 { 64 scanf("%s%s",pre,in); 65 len=strlen(pre); 66 h=creat(pre,in,len); 67 postorder(h); 68 printf("\n"); 69 lorder(h); 70 printf("\n"); 71 } 72 return 0; 73 } 74 /*从先序遍历中读入根节点；然后从中序遍历中找到与根节点相等的元素，将中序序列分成两个部分，左边的为二叉树的左子树，右边为二叉树的右子树；最后递归调用得到根节点的左右子树*/