zcmu-4928: 二叉树

4928: 二叉树 

Time Limit: 1 Sec  Memory Limit: 32 MB
Submit: 24  Solved: 17
[Submit][Status][Web Board]

Description

 

    如上所示，由正整数1，2，3……组成了一颗特殊二叉树。我们已知这个二叉树的最后一个结点是n。现在的问题是，结点m所在的子树中一共包括多少个结点。

    比如，n = 12，m = 3那么上图中的结点13，14，15以及后面的结点都是不存在的，结点m所在子树中包括的结点有3，6，7，12，因此结点m的所在子树*有4个结点。

Input

输入数据包括多行，每行给出一组测试数据，包括两个整数m，n (1 <= m <= n <= 1000000000)。最后一组测试数据中包括两个0，表示输入的结束，这组数据不用处理。 

Output

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

Sample Input

3 7 142 6574 2 754 0 0

Sample Output

3 63 498

HINT

 

Source

数据结构高分笔记

[Submit][Status][Web Board]

 

节点x所在子树是以他为root的子树，比如x = 5,y= 11则子树为～～

每一层的节点数 = 层数 * 2，左子树 = 父节点 * 2，右子树 = 父节点 * 2 + 1，

所以从 以x节点为root的左右子树开始遍历（所以root自己也要算做一点），一直到右子树的位置>= y,所求的节点个数就是加上右子树的位置>= y前每一层的所有的节点个数，

举例：x = 3,y = 14,子树为，

(1) left = 6,r = 7,t = 2,ans = 1 + 2,

(2) left = 12, r = 15,t = 4,(r >= y 了，所以break，ans没有加上这一层所有的节点)

所以再判断下，加上下一行的几个节点～

#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
    int x,y;
    while(scanf("%d%d",&x,&y) && x && y)
    {
        int left = 2 * x;
        int right = 2 * x + 1;
        int t = 1;
        int ans = 1;//自己也算做一点
        while(right <= y)//遍历每一层,直到最后一个节点
        {
            t *= 2;//每一层的节点数
            ans += t;
            left *= 2;//左孩子所在节点序号
            right = right * 2 + 1;//右孩子所在节点序号
        }
        if(left <= y)   ans += y - left + 1;
        cout<<ans<<endl;
    }
    return 0;
}