hi !
I'm trying to solve this problem .
I use the alog just like what Dreamer#1 did, but I got WA for serveral times.And now I can't find out what's wrong with my code.
1. I check the input N & H, if N is over 2^H-1 or less than H, and print impossible.
2. And I use recursion to build the tree.
3. I use preorder to traverse the tree, and print each one.
4. I check the space ' ' at the tail of my output.
and my program I/O
Code: Select all
30 5
30 30
50 30
50 6
60 7
4 1
10000 30
0 0
Code: Select all
Case 1: 15 7 3 1 2 5 4 6 11 9 8 10 13 12 14 23 19 17 16 18 21 20 22 27 25 24 26 29 28 30
Case 2: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Case 3: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 35 27 26 31 29 28 30 33 32 34 43 39 37 36 38 41 40 42 47 45 44 46 49 48 50
Case 4: 19 3 1 2 11 7 5 4 6 9 8 10 15 13 12 14 17 16 18 35 27 23 21 20 22 25 24 26 31 29 28 30 33 32 34 43 39 37 36 38 41 40 42 47 45 44 46 49 48 50
Case 5: 1 29 13 5 2 3 4 9 7 6 8 11 10 12 21 17 15 14 16 19 18 20 25 23 22 24 27 26 28 45 37 33 31 30 32 35 34 36 41 39 38 40 43 42 44 53 49 47 46 48 51 50 52 57 55 54 56 59 58 60
Case 6: Impossible.
Case 7: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1809 .......
here are my part of bulidtree code
Code: Select all
struct MyTree* buildTree( int N , int H , int inti ) {
struct MyTree *left = NULL , *right = NULL , *nowptr;
/* tree */
int i ;
if(H==1&&N==1)
return newItem(inti+1);
/* at the root */
if(H<=0)
return NULL;
/* just in case */
for( i = 1 ; i <= N ; i ++ )
if(isTree(i-1,H-1)==1&&isTree(N-i,H-1)==1) {
/* isTree is a method check that N is samller than 2^H*/
if(i!=1) {
left = buildTree(i-1,H-1,inti);
if(left==NULL)
continue;
}
if(i!=N) {
right = buildTree(N-i,H-1,inti+i);
if(right==NULL) {
free(left);
continue;
}
}
nowptr = newItem(inti+i);
nowptr->left = left ;
nowptr->right = right ;
return nowptr;
}/* for */
return NULL;
}
here are my main function
Code: Select all
while(scanf("%d %d",&N,&H)!=EOF&&N+H!=0) {
if(isTree(N,H)==1&&N>=H) {
topptr = buildTree(N,H,0);
if(topptr!=NULL) {
printf("Case %d:",times++);
PrintLev(topptr);
printf("\n");
}
else
printf("Case %d: Impossible.\n",times++);
}
else
printf("Case %d: Impossible.\n",times++);
}
Thanks you guys spend your precious time.
Please point out my err.[/code]