314完全二叉树的子树

题目：完全二叉树的子树

问题描述

对一棵完全二叉树，采用自上而下、自左往右的方式从1开始编号，我们已知这个二叉树的最后一个结点是n，现在的问题是结点m所在的子树一共包括多少个结点？

输入格式

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

输出格式

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

样例输入

        3 12

    0 0

样例输出

        4

 1 #include<stdio.h>
 2 int Count(int m,int n);
 3 
 4 int main()
 5 {
 6     int m,n;
 7     
 8     while(1)
 9     {
10         scanf("%d%d",&m,&n);
11         
12         if(m==0&&n==0) break;
13     
14         int numberOfChild=0;
15         numberOfChild=Count(m,n);
16         
17         printf("%d\n",numberOfChild);
18     }
19     return 0;
20 }
21 
22 int Count(int m,int n)//n is the total
23 {
24     int numberofVertex;
25     if(m>n) numberofVertex=0;
26     else
27     {
28         numberofVertex=Count(m*2,n)+Count(m*2+1,n)+1;
29     }
30     return numberofVertex;
31 }

典型递归；

需要注意的是，求的是结点m所在的子树一共包括多少个结点，要加上m本身（递归多加一个1）；

写这种有返回值的递归函数，还是得另开一个临时变量作为返回值，不然绕不清楚（numberofVertex）；