首页 > 代码库 > UVa712 S-Trees (二叉树)

UVa712 S-Trees (二叉树)

链接:http://acm.hust.edu.cn/vjudge/problem/19200
分析:这题那个xi有啥用?二叉树正好对应二进制,将根结点表示为0,左子树就是i*2+0,右子树为i*2+1,所有叶子结点正好可以用0~(1<<n)-1(n为层数,根结点为第0层)的编号表示。

 1 #include <cstdio> 2  3 int main() { 4     int n, kase = 0; 5     while (scanf("%d", &n) == 1 && n) { 6         int x[10]; char buf[200]; 7         for (int i = 0; i < n; i++) scanf("%s", buf); 8         int m = 1 << n; int leaf[200]; 9         scanf("%s", buf);10         for (int i = 0; i < m; i++)11             leaf[i] = buf[i] - 0;12         printf("S-Tree #%d:\n", ++kase);13         int q; scanf("%d", &q);14         int dir[10];15         for (int i = 0; i < q; i++) {16             scanf("%s", buf);17             int v = 0;18             for (int j = 0; j < n; j++)19                 v = v * 2 + buf[j] - 0;20             printf("%d", leaf[v]);21         }22         printf("\n\n");23     }24     return 0;25 }

 

UVa712 S-Trees (二叉树)