九度OJ 1176：树查找（完全二叉树）

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：5209

解决：2193

题目描述：: 有一棵树，输出某一深度的所有节点，有则输出这些节点，无则输出EMPTY。该树是完全二叉树。

输入：: 输入有多组数据。

每组输入一个n(1<=n<=1000)，然后将树中的这n个节点依次输入，再输入一个d代表深度。

输出：: 输出该树中第d层得所有节点，节点间用空格隔开，最后一个节点后没有空格。

样例输入：

样例输出：

2 3

来源：: 2010年北京邮电大学网院研究生机试真题

思路：

无须建树，直接找到该层的起点和终点输出即可。

代码：

#include <stdio.h>

#include <math.h>

#define N 1000

int main(void)

{

    int n, i;

    int a[N];

    int depth, d;

    while (scanf("%d", &n) != EOF)

    {

        depth = 0;

        int tmp = n;

        while (tmp)

        {

            tmp /= 2;

            depth ++;

        }

        for(i=0; i<n; i++)

            scanf("%d", &a[i]);

        scanf("%d", &d);

        if (d <= 0 || d > depth)

        {

            printf("EMPTY\n");

            continue;

        }

        int begin = pow(2, d-1) - 1;

        int end = pow(2, d) - 2;

        if (d == depth)

            end = n-1;

        //printf("begin=%d, end=%d, depth=%d, d=%d\n", begin, end, depth, d);

        printf("%d", a[begin]);

        for (i=begin+1; i<=end; i++)

            printf(" %d", a[i]);

        printf("\n");

    }

    return 0;

}

/**************************************************************

    Problem: 1176

    User: liangrx06

    Language: C

    Result: Accepted

    Time:10 ms

    Memory:1004 kb

****************************************************************/

巴特西

九度OJ 1176：树查找（完全二叉树）

最新文章

热门文章

巴特西

九度OJ 1176：树查找 （完全二叉树）

最新文章

热门文章

九度OJ 1176：树查找（完全二叉树）