二叉树子树结点个数
描述
如上所示，由正整数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)。最后一组测试数据中包括两个0，表示输入的结束，这组数据不用处理。
输出
对于每一组测试数据，输出一行，该行包含一个整数，给出结点m所在子树中包括的结点的数目。
输入样例 1
3 7
142 6574
2 754
0 0
输出样例 1
3
63
498
题解：
解答这道题主要可以分为以下几步：
1、确定子树根结点所在层数
2、确定二叉树的总层数
3、计算子树左下角和右下角的结点数值分别是多少
4、判断子树最下方的左右结点和二叉树的右下结点的关系，确定子树最下层有多少个结点
5、计算总结点数
（1）第1、2步都是要确定层数，其实层数并不难确认，我们分析一下二叉树就可以得出规律
每一层的开始结点为2^(层数-1)，所以我们只需要确定结点与2之间幂的次数，就可以确定结点所在层数
int count(long long int x) { int ans = 0; while(x != 0){ x/=2; ans++; } return ans; }
（2）子树的左右下角的结点也是有规律的，我们以3为子树根结点来分析一下：
左下角的结点是其（根结点乘2）得来，右下角则等于（根结点*2+1）
long long left(long long int x,long long int y) { while(y--) { x*=2; } return x; } long long right(long long int x,long long int y) { while(y--) { x = x * 2 + 1; } return x; }
（3）判断子树最下方的左右结点和二叉树的右下结点的关系，确定子树最下层有多少个结点
if(n <= right(m,q-p) && n >= left(m,q-p)) sum += n-left(m,q-p)+1; if(n > right(m,q-p)) sum += right(m,q-p) - left(m,q-p) +1;
（4）确定子树的结点总个数，因为结点的个数是指数增长的，我们只需要知道子树的层数就可以计算出子树的结点个数，我通过快速幂的来计算
long long int quickPower(long long int x,long long int y) { long long int result = 1; // 定义变量 while (y > 0) // 当指数大于 0 时进行幂运算 { if (y & 1) // y 和 1 做与运算,相当于对 2 求模 { result = result * x; // 如果 y 为奇数,则结果成一个 x } x = x * x; // x 乘二次方,下次使用 y = y >> 1; // y 右移一位,相当于除以 2 } return result; // 返回结果 }
完整代码如下：
#include<stdio.h> int count(long long int x) { int ans = 0; while(x != 0){ x/=2; ans++; } return ans; } long long int quickPower(long long int x,long long int y) { long long int result = 1; // 定义变量 while (y > 0) // 当指数大于 0 时进行幂运算 { if (y & 1) // y 和 1 做与运算,相当于对 2 求模 { result = result * x; // 如果 y 为奇数,则结果成一个 x } x = x * x; // x 乘二次方,下次使用 y = y >> 1; // y 右移一位,相当于除以 2 } return result; // 返回结果 } long long left(long long int x,long long int y) { while(y--) { x*=2; } return x; } long long right(long long int x,long long int y) { while(y--) { x = x * 2 + 1; } return x; } int main() { long long int m,n; while(scanf("%lld %lld",&m,&n)!=EOF){ if(m+n==0) break; //printf("%d\n",count(m,n)); int p = count(m); int q = count(n); // printf("p=%d,q=%d\n",p,q); // printf("l=%lld,r=%lld\n",left(m,q-p),right(m,q-p)); long long int sum = quickPower(2,q-p)-1; if(n <= right(m,q-p) && n >= left(m,q-p)) sum += n-left(m,q-p)+1; if(n > right(m,q-p)) sum += right(m,q-p) - left(m,q-p) +1; printf("%lld\n",sum); } return 0; }
