題意:有一棵完全二叉樹,每層元素有同一變量表示,從上到下分别為x1,x2,... 最後一層葉子結點會有0或1的指派,輸入給出。然後如果xi取值為0時,則往左子樹走,否則往右子樹走,直到走到葉子結點,得到一值。
思路:因為是完全二叉樹,可以用順序存儲,數組實作即可。另外也隻需存葉子結點的值就行了。對一結點k來說,左孩子是2k,右孩子是2k+1。因為高度最大為7,最多有x7,是以可以直接取數組的第二位,即下标1,來獲得xk中的k。
注意:每個測試樣例後有個空行,WA了一次~
二維數組作形參: 一是 char (*pt)[4] ; 二是 char pt[][5] 如果寫成char *pt[5] 就會提示錯誤:cannot convert `char (*)[5]' to `char**' for argument `3' to `void process(char*, int, char**)' 意思是實參是char(*)[5],而形參是char**,不比對。
[ ]的優先級高于*,char (*pt)[4] 表示一個指向數組的指針,指向具有4個char值的數組的指針;char *pt[5] 表示指針數組,char型指針數組、有5個元素。
Code:
#include<stdio.h>
#include<string.h>
#define MAXN 200
void process(char *vva,int len,char varord[][5]);
int tree[MAXN];
int main()
{
int cnt=1;
int n;
while(scanf("%d",&n)==1 && n)
{
char varord[8][5];
for(int i=0;i<n;++i)
scanf("%s",varord[i]);
getchar();
for(int i=0;i<(1<<n);++i)
{
char c=getchar();//printf("%c ",c);
tree[(1<<n)+i]=c-'0';
}
//for(int i=0;i<(1<<n);++i)
// printf("%d ",tree[i+(1<<n)]);
int m;
scanf("%d",&m);
printf("S-Tree #%d:\n",cnt++);
for(int i=0;i<m;++i)
{
char vva[10];
scanf("%s",vva);
process(vva,strlen(vva),varord);
}
printf("\n\n");
}
return 0;
}
void process(char *vva,int len,char varord[][5])
{
int k=1;
for(int i=0;i<len;++i)
{
int t=varord[i][1]-'0';//因最多是x7,是以這裡可以直接減字元0。注意下标是1不是2.
if(vva[t-1]=='0') k=2*k;
else k=2*k+1;
}
printf("%d",tree[k]);
}