二叉树

考虑两种情况：
①结点m和n不在同一行
②结点m和n处在同一行

#include <iostream>
#include <cmath>
using namespace std;
int cal(int n){
    int h = log(n) / log(2) + 1;
    return h;
}
int main(){
    int m, n;
    while(cin >> m >> n){
        if (m == 0 && n == 0)
            break;
        // n 节点和 m 节点的高度差
        int h = cal(n) - cal(m);

        int k = (int)pow(2, h);
        //最后一层的起始节点为start = m * 2 ^ h 
        int start = m * k;
        //以 m 节点为根结点的子树最右侧元素end = (1 + m) * 2 ^ h - 1
        int end = (1 + m) * k - 1;
        //以 m 节点为根结点的子树（除去最后一层）的元素总数tot = 2 ^ h - 1
        int tot = k - 1;
        //最后一层也是满的
        if(end <= n){
            tot += k;
        }else{
            if(n >= start){
                tot += n - start + 1;
            }
        }
        cout << tot << endl;
    }
    return 0;
}

每一行的节点数等于right-left+1，把每一行相加起来即可。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,left,right,cnt;
    while((cin>>m>>n)&& n && m)
    {
        cnt=0;
        left=right=m;
        while(left<=n)
        {
            cnt=cnt+right-left+1;//每一层的节点数目为right-left+1。 
            left=2*left;
            right=2*right+1;
            if(right>n) right=n;
        }
        cout<<cnt<<endl;
    }
    return 0;
}