问题与解答

问题描述

对一棵完全二叉树，输出某一深度的所有节点，有则输出这些节点，无则输出EMPTY。

输入格式

输入有多组数据。

每组数据第一行输入一个结点数n(1<=n<=1000)，第二行将树中的这n个节点依次输入（每个结点存储的数据是一个数字），n个结点编号方式是层间从上到下、层内从左到右依次编号；第三行输入一个d代表深度。

当n=0时，表示输入结束。

输出格式

每组数据在一行上输出该树中第d层的所有节点，节点间用空格隔开。每组数据输出完成后要换行。

样例输入

4

1 2 3 4

2

0

样例输出

2 3

样例说明

该完全二叉树的第一层是1，第二层是2 3，第三层是4；题目要求输出第二层，则输出2 3。

关键：由深度确定完全二叉树数组的下标

#include<stdio.h>

#include<math.h>

#define MaxNum 1010

int main()

{

    int m,i,j,deep,deepest;

    while(scanf("%d",&m)!=EOF && m)       //多点测试输入

    {

        int T[MaxNum];

        for(i=1; i<=m; i++)

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

        scanf("%d",&deep);

        deepest = (int)(log(m)/log(2))+1; //完全二叉树的深度：根节点为深度1

        if(deep > deepest)

	/*给定深度大于树的最大深度： 输出结点为空*/

            printf("EMPTY\n");

        else

        if(deep == deepest)

        {

	/*给定深度等于树的最大深度： 输出最后一层结点*/

            i = (int)pow(2,deep-1); //最后一层首元素的下标

            for(i=i; i<=m; i++)     //最后一层不一定满

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

            printf("\n");   //注意换行

        }

        else

        {

	/*给定深度小于树的最大深度： 输出中间某层结点*/

            i = (int)pow(2, deep-1); //第deep层的首元素下标为i

            j = (int)pow(2, deep)-1; //第deep层的末元素下标为j（对于完全二叉树来说中间层必定是满的）

            for(i=i; i<=j; i++)

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

            printf("\n");

        }

    }

}

巴特西

<数据结构>XDOJ317.输出完全二叉树的某一层

问题与解答

最新文章

热门文章