#二叉树子树节点判断#北京大学机试#acwing

思路:本题给出总节点数n和子树根节点m,先使用位运算计算出每组数据对应的根节点层数和树的总层数,此时用两个变量分别逐层记录该子树某层最左和最右节点的编号,直到最底层。此时:

若总结点数落在左和右之中,则子树节点为完全n-1层+多余节点,其他情况较为简单

接下来分别打印treenum即可

/*如上所示,由正整数 1,2,3……组成了一颗特殊二叉树。我们已知这个二叉树的最后一个结点是 n。现在的问题是,结点 m所在的子树中一共包括多少个结点。
比如,n=12,m=3那么上图中的结点 13,14,15以及后面的结点都是不存在的,结点 m所在子树中包括的结点有 3,6,7,12,因此结点 m的所在子树中共有 4个结点。
输入格式:输入数据包括多行,每行给出一组测试数据,包括两个整数 m,n。最后一行 0 0 表示输入结束。
输出格式:对于每一组测试数据,输出一行,该行包含一个整数,给出结点 m所在子树中包括的结点的数目。
数据范围:1≤m≤n≤109,最多包含 20组数据。
输入样例:
3 12
0 0
输出样例:
4 */
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
    int n = 12, m = 3;
    while (1){
        scanf("%d%d", &m, &n);//输入数据
    if (m == 0 && n == 0) { break; }

    int i = 1;//从一层开始获取层数
    int begin_level = 0;//存储子树的根在第几层
    int final_level = 0;//存储树的总层数
    while (1) {
        if (m >= 1 << (i - 1) && m < 1 << i) {
            begin_level = i;
        }
        if (n >= 1 << (i - 1) && n < 1 << i) {
            final_level = i;
            break;
        }
        ++i;
    }

    int left_side = m;
    int right_side = m;
    for (i = begin_level; i < final_level; i++) {
        left_side = left_side * 2;
        right_side = right_side * 2 + 1;
    }
    int treenum = 0;
    if (left_side > n) { //说明m叶节点都在倒数第二层
        treenum = (1 << (final_level - begin_level)) - 1;
    } else if (right_side >= n) {//说明m子树有一部分叶节点在最后一层
        treenum = (1 << (final_level - begin_level)) + n - left_side;
    } else {
        treenum = (1 << (final_level - begin_level + 1)) - 1;//说明子树叶节点全在最后一层
    }
    printf("%d\n", treenum);
}
    return 0;
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
10-05 10:13
已编辑
HHHHaos:让这些老登来现在秋招一下,简历都过不去
点赞 评论 收藏
分享
评论
1
1
分享
牛客网
牛客企业服务