4514: 【例】【入门】结点的查找(2186)

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

有一棵 lns="http://www.w3.org/1998/Math/MathML">n 个结点的完全二叉树，按照从上到下、从左到右的顺序，结点编号分别是 lns="http://www.w3.org/1998/Math/MathML">1∼n ，该二叉树的根所在的层数为lns="http://www.w3.org/1998/Math/MathML">1；

请问该二叉树的第 lns="http://www.w3.org/1998/Math/MathML">k 层有哪些结点，按照从左到右的顺序输出这些结点的编号？（如果第 lns="http://www.w3.org/1998/Math/MathML">k 层没有结点，请输出 EMPTY）

输入

读入有多组数据。

每组数据的输入 lns="http://www.w3.org/1998/Math/MathML">2 个整数 lns="http://www.w3.org/1998/Math/MathML">n 和 lns="http://www.w3.org/1998/Math/MathML">k (lns="http://www.w3.org/1998/Math/MathML">1≤n≤1000)，lns="http://www.w3.org/1998/Math/MathML">n 代表完全二叉树的结点数量，再输入一个 lns="http://www.w3.org/1998/Math/MathML">k 代表深度（lns="http://www.w3.org/1998/Math/MathML">1≤k≤20）。

如果读入的 lns="http://www.w3.org/1998/Math/MathML">n 为 lns="http://www.w3.org/1998/Math/MathML">0 ，表示读入结束。

输出

输出该树中第 lns="http://www.w3.org/1998/Math/MathML">k 层得所有结点，结点间用空格隔开。

如果第 lns="http://www.w3.org/1998/Math/MathML">k 层没有结点，请输出EMPTY。

样例输入 复制 

5 7
7 2
0

样例输出 复制 

EMPTY
2 3

提示

#include<bits/stdc++.h>
using namespace std;
/*
如果要求第k层有多少结点(假设k层是存在的)
第1层~第k-1层在完全二叉树中一定是满的，第k层的第1个结点的编号是:2^(k-1)
分两种情况:
如果第k层是满的:第k层的最后一个结点的编号一定是2ぺk-1
如果第k层不满:第k层是叶子结点，最后一个结点的编号一定是n
*/
int n, k;
int main() {
    int s, e;
    while (1) {
        cin >> n;
        if (n == 0) break;
        cin >> k;
        //计算出第k层的第1个结点的编号
        s = (int) pow(2, k - 1);
        if (s > n) {
            cout << "EMPTY" << endl;
            continue;
        }
        e = (int) pow(2, k) - 1;
        //输出第k层的结点
        for (int i = s; i <= n && i <= e; i++) {
            cout << i << " ";
        }
        cout << endl;
    }
    return 0;
}

来源/分类

提交提交记录统计露一手!