[保研/考研机试] KY85 二叉树北京大学复试上机题 C++实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了[保研/考研机试] KY85 二叉树北京大学复试上机题 C++实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目链接：

二叉树https://www.nowcoder.com/share/jump/437195121692000296981

描述

[保研/考研机试] KY85 二叉树北京大学复试上机题 C++实现,机试刷题记录,c++,算法,数据结构

如上所示，由正整数1，2，3……组成了一颗特殊二叉树。我们已知这个二叉树的最后一个结点是n。现在的问题是，结点m所在的子树中一共包括多少个结点。比如，n = 12，m = 3那么上图中的结点13，14，15以及后面的结点都是不存在的，结点m所在子树中包括的结点有3，6，7，12，因此结点m的所在子树中共有4个结点。

输入描述：

输入数据包括多行，每行给出一组测试数据，包括两个整数m，n (1 <= m <= n <= 1000000000)。

输出描述：

对于每一组测试数据，输出一行，该行包含一个整数，给出结点m所在子树中包括的结点的数目。

示例1

输入：

3 12
0 0

输出：

思路：

定义递归函数 cal，其中参数 m 表示当前结点，参数 n 表示最后一个结点。
如果 m 大于 n，表示当前结点超过最后一个结点，返回 0。
否则，递归计算左子树和右子树中包括的结点数，再加上当前结点 m 本身。
在 main 函数中，循环读入输入的 m 和 n，调用递归函数 cal 计算结果，并输出。如果输入为 0 时结束循环。

源代码：

#include <iostream>
using namespace std;

// 定义递归函数，计算结点 m 所在子树中包括的结点数目
int cal(int m, int n) {
    if (m > n) {
        return 0; // 结点 m 超过最后一个结点 n，返回 0
    }
    else {
        // 递归计算左子树和右子树中包括的结点数，再加上 m 本身
        return cal(2 * m, n) + cal(2 * m + 1, n) + 1;
    }
}

int main() {
    int m, n;
    while (cin >> m >> n) {
        int res = 0; // 存储结果
        if (m == 0 && n == 0) {
            break; // 输入为 0 时结束循环
        }
        res = cal(m, n); // 调用递归函数计算结果
        cout << res << endl; // 输出结果
    } 

    return 0;
}