九度OJ——1176树查找

AI那点小事

发布于 2020-04-18 19:54:47

5480

发布于 2020-04-18 19:54:47

文章被收录于专栏：AI那点小事

题目描述：有一棵树，输出某一深度的所有节点，有则输出这些节点，无则输出EMPTY。该树是完全二叉树。输入：输入有多组数据。每组输入一个n(1<=n<=1000)，然后将树中的这n个节点依次输入，再输入一个d代表深度。输出：输出该树中第d层得所有节点，节点间用空格隔开，最后一个节点后没有空格。样例输入： 4 1 2 3 4 2 样例输出： 2 3

思路：用数组存储完全二叉树，首先找到指定层的定一个元素的下标i，判断2*i-1(对应满二叉树的该层的最后一个元素)是否属于这个完全二叉树，若是则打印从i到2*i-1的元素，若不是但i是则打印从i到N的元素，否则输出EMPTY。 AC代码：

#include <iostream>
#include <cmath> 
#include <cstring>
using namespace std;

int Tree[1001] = {0};
int N,level,start;

int main()
{
    while(cin>>N){
        memset(Tree,0,sizeof(Tree[0])*1001);
        for(int i = 1 ; i <= N ; i++){
            cin>>Tree[i];
        }
        cin>>level;
        start = 1;
        while(level > 1){
            start *= 2;
            level--;
        }
        if(start*2-1 <= N){//该层最后一个结点属于二叉树 
            cout<<Tree[start];
            for(int i = start+1 ; i <= start*2-1 ; i++){
                cout<<" "<<Tree[i];     
            }       
        }else if(start <= N && start*2-1 > N){
            cout<<Tree[start];
            for(int i = start+1 ; i <= N ; i++){
                cout<<" "<<Tree[i]; 
            }
        }else{
            cout<<"EMPTY";
        }
        cout<<endl; 
    }

    return 0;
 }