首页 > 试题广场 >

二叉树

[编程题]二叉树

热度指数：14750 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

如上所示，由正整数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)。

输出描述:

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

示例1

输入

3 12
0 0

输出

算法知识视频讲解

Benson666

#include <iostream>
using namespace std;
int res=0;
void add(int x, int last){
    if(x>last) return;
    res++;
    add(2*x, last);
    add(2*x+1, last);
}
int main(){
    int m,n;
    while(cin>>m>>n){
        add(m,n);
        cout<<res<<endl;
    }
}

发表于 2018-03-20 14:19:14 回复(2)

丶冽。



简单的递归一下，子节点分别是父节点的二倍和二倍+1，只要不超过，就递归遍历结果+1.
int result;
void get(int m,int n){
    if(m<=n)  result++;
    else return;
    get(2*m,n);
    get(2*m+1,n);
}
int main(){
    int n,m;
    while(cin>>m){
        cin>>n;
        result=0;
        get(m,n);
        cout<<result<<endl;
    }
    return 0;
}

编辑于 2018-06-08 21:36:02 回复(1)

Java

LHC0512

Java 递归解法

import java.util.Scanner;

public class Main {
    static int count=0;
    static int n;
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        n = scanner.nextInt();
        fun(m);
        System.out.println(count);
    }

    static  void fun(int m){
        if (m<=n){
            count++;
            fun(m*2);
            fun(m*2+1);
        }
    }
}

发表于 2020-03-07 11:00:48 回复(0)

Python

TimeMac

不用递归，耗时。同一颗树来说，从当前层开始，记录最左节点数（左结点是上一层最左结点*2）最右结点（右结点是上一层最右结点*2+1）。如果最右结点>=总结点数，结束。

而二叉树的结点数是每层是上一层的两倍。

最后一层要处理。如果左结点未超总结点数，则把剩余的加上。

while True:
    try:
        i,num = list(map(int,input().split()))
        result,level = 1,1
        leftNode,rightNode = 2*i,2*i+1
        while rightNode <= num:
            level *= 2
            result += level
            leftNode *= 2
            rightNode = rightNode*2 + 1
        if leftNode <= num:
            result += num-leftNode+1
        print(result)
    except Exception:
        break

编辑于 2018-09-29 20:44:23 回复(0)

为啥要起名字

while True:
try:
m,n=list(map(int,raw_input().strip().split()))
count,num=1,1
left,right=2*m,2*m+1
while right<=n:
num=num*2
count+=num
left=left*2
right=2*right+1
if left<=n:
count+=n-left+1
print(count)
except:
break

发表于 2018-05-30 15:28:01 回复(1)

Java

Pigeon_



import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int m = scanner.nextInt();
            int n = scanner.nextInt();
            System.out.println(findSubTree(m, n) - 1);
        }
        scanner.close();
    }

    static int findSubTree(int x, int n) {
        if (x > n)
            return 1;
        return findSubTree(2 * x, n) + findSubTree(2 * x + 1, n);
    }
}

/*
 * 递归部分实际求的是树的虚拟叶结点数，所谓虚拟叶结点，是指把一棵树补成完全二叉树而
 * 新添加的虚拟叶结点。 可以证明，虚拟叶结点数=树结点数+1。证明如下：
 * 设虚拟叶结点数为x，有x = 2*n0 + n1， 设树总结点数为n，有n = n0 + n1 + n2。
 * 树同时具有性质n0 = n2+1, 所以，x = n0
 * + n1 + n2 + 1 = n+1。 注：上述ni是度为i的结点
 */

编辑于 2018-01-21 21:40:22 回复(0)

都别抢我洞洞鞋

//很简单的分治法
#include <iostream>

using namespace std;

//一共有n个节点，m节点所在子树的节点个数
int Function(int m,int n){
    if(m>n){
        return 0;
    }else{
        return Function(2*m,n) + Function(2*m+1,n) +1;
    }
}

int main()
{
    int m,n;
    while(scanf("%d%d",&m,&n)!=EOF){
               if(m==0&&n==0){
                break;
                }
        printf("%d\n",Function(m,n));
    }
    return 0;
}

发表于 2021-03-08 21:18:59 回复(0)

用户抉择

#include <stdio.h>

int num(int m,int n)
{
    if(m>n) return 0;
    else return 1+num(m*2,n)+num(m*2+1,n);
}

int main()
{
    int m,n;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        if(m==0&&n==0) break;
        printf("%d\n",num(m,n));
    }
}

发表于 2021-02-21 21:18:42 回复(1)

纠结offer的菜狗

#include<iostream>
using namespace std;

int main()
{
    int m,n;
    while(cin >> m >> n && m && n)
    {
        int level = 0,nodes = 0;
        int t = m;
        while(m <= n && t <= n)
        {
            m *= 2;
            t = 2 * t + 1;
            level++;
        }
        if(m <= n && t > n)
            nodes += n - m + 1;
        nodes += (1 << level) - 1;
        cout << nodes << endl;
    }
    return 0;
}

发表于 2021-01-30 15:17:36 回复(0)

漫漫云天自翱翔

因为是完全二叉树，利用二叉树的性质，左节点等于两倍当前节点，右节点等于两倍+1，递归条件m<=n

#include<iostream>
using namespace std;
//const int maxn=100050;
//int tree[maxn];
int s;
int m,n;
void f(int temp){
    if(temp<=n){
        s++;
        f(2*temp);
        f(2*temp+1);
    }
}
int main(){
    while(cin>>m>>n){
        s=0;
        if(n==0&&m==0){
            return 0;
        }
        f(m);
        cout<<s<<endl;
    }
    return 0;
}

发表于 2020-07-29 22:37:01 回复(0)

C/C++

YhX.

#include <stdio.h>
int res=0;
void add(int x, int last){
    if(x>last) return;//last往后是空节点所以结束
    res++;//放入一个合法节点,结点个数加一
    add(2*x, last);//开始加后两个子节点
    add(2*x+1, last);
}
int main(){
    int m,n;
    while(scanf("%d%d",&m,&n)!=EOF){
        add(m,n);
        printf("%d\n",res);
        res=0;
    }
}

发表于 2020-04-06 18:07:36 回复(1)

littlejay

#include<iostream> //完全二叉树顺序存储的遍历，吓唬人的水题
using namespace std;
int m,n,cnt=0;
void DFS(int root){
    if(root>n) return;
    cnt++;
    DFS(root*2);
    DFS(root*2+1);
}
int main(){
    while(cin >> m >> n){
        if(m==0 && n==0) break;
        cnt=0;
        DFS(m);
        cout << cnt << endl;
    }
    return 0;
}

发表于 2020-03-21 21:55:11 回复(0)

C/C++

松果子201908140959918

////方法不是很简介，但是能够通过

#include <iostream>

#include <math.h>

using namespace std;

int main()
{
int m, n, grade_n, grade_m,m1,m2,n_buttom,ans;
long n_buttom_sum;
cin >> m >> n;
for (int k=1; k<n ; k++) //计算n的级数
{
if (n > (pow(2,k-1) - 1) && n <= (pow(2,k) - 1))
{
grade_n = k;
break;
}
}
for (int j=1; j<m ; j++)//计算m的级数
{
if (m > pow(2,j-1) - 1 && m <= pow(2,j) - 1)
{
grade_m = j;
break;
}
}
m1 = m - (pow(2,grade_m - 1) - 1);//m所在级所占数量
m2 = pow(2,grade_m - 1);//m所在级节点总数
n_buttom = n - (pow(2,grade_n-1) - 1);//n的叶数目
n_buttom_sum = pow(2,grade_n-1);//n最后一级可有的最大页数目

if (n_buttom < (n_buttom_sum*(m1-1)/m2))//m所在子树中,最后一列位置与n在最
//后一列所包含叶数比对，如果小于，则m所在子树最后一列不含叶节点
{
ans = pow(2,grade_n - grade_m) - 1;
cout << ans << endl;
}
if (n_buttom > (n_buttom_sum*(m1-1)/m2) && n_buttom <= n_buttom_sum*m1/m2)
{
ans = pow(2,grade_n - grade_m) - 1 + n_buttom - n_buttom_sum*(m1-1)/m2;
cout << ans << endl;
}
if (n_buttom > (n_buttom_sum*m1/m2))
{
ans = pow(2,grade_n - grade_m + 1) - 1;
cout << ans << endl;
}
}

发表于 2019-08-24 14:29:36 回复(0)

C/C++

Jcakbrocp

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int subnum(int m, int n){     int num = 0;     queue<int> q;     q.push(m);     while (!q.empty()){         int i = q.front();         q.pop();         if (i * 2 <= n){             num++;             q.push(i*2);         }         if (i * 2 + 1 <= n){             num++;             q.push(i * 2 + 1);         }     }     return num;
}
int main(){     int m, n;     while (cin >> m >> n){         cout<<subnum(m,n)<<endl;     }
}

发表于 2019-03-15 22:09:12 回复(1)

chenxd

C语言版本：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cmath>
using namespace std;
int f(int m,int n){
    if(2*m>n) return 1;
    if(2*m+1>n) return 2;
    return 1+f(2*m,n)+f(2*m+1,n);
}
int main(){
    int m,n;
    while(cin>>m>>n){
        cout<<f(m,n)<<endl;
    }
    return 0;
}

编辑于 2019-01-23 20:19:41 回复(0)

找到好工作！！！

#include<stdio.h>
#include<cmath>
int Line(int n){
 return log(n)/log(2)+1;
}
int NodeNum(int l1,int l2,int m,int n){
 if(l1==l2) 
 {
  printf("==\n");
  return 0;
 }
 int cnt=pow(2,l2-l1+1)-1;//计算2的几次方
 int time=l2-l1;
 int p1=m*pow(2,time);
 int p2=m;
 while(time--)
  p2=p2*2+1;
 if(p2<=n)
  return cnt;
 else if(p1<=n)
  return cnt-(p2-n);
 else 
  return pow(2,l2-l1)-1;
}
int main(){
 int n,m;
 while(scanf("%d%d",&m,&n)!=EOF){
  int l1=Line(m);
  int l2=Line(n);
  int cnt=NodeNum(l1,l2,m,n);
  printf("%d\n",cnt);
 }
 return 0;
}

发表于 2019-01-22 10:14:34 回复(0)

C/C++

watle自动机

问题模型即完全二叉树

#include <stdio.h>
int m,n;
int main(){
    int left,right,sum;
    while(scanf("%d %d",&m,&n)!=EOF){
        //根结点:所在子树为整个二叉树
        if(m==1)
            printf("%d\n",n);
        //非根结点:从当前结点到此结点的子树最底层最右端的结点数目即为所求
        else{
            //sum-动态记录结点m所在子树中包括的结点的数目
            //left.right-结点m所在子树某层最左端和最右端的结点编号
            //初始化sum=1，即算入结点m
            sum=1;
            //求出结点m下一层两个结点的编号
            left=2*m;
            right=2*m+1;
            //left.right有一者<=n时，循环
            while(left<=n || right<=n){
                //right<=n 说明当前层的所有结点均在完全二叉树内
                if(right<=n)
                    sum+=(right-left+1);
                //left<=n且right>n，说明当前层编号为n+1~right的结点不在完全二叉树内
                //注意减去这部分
                else if(left<=n && right>n)
                    sum+=(n-left+1);
                left=2*left;
                right=2*right+1;
            }
            //结果
            printf("%d\n",sum);
        }
    }
    return 0;
}

发表于 2019-01-03 18:48:01 回复(0)

hustsun

#include <cstdio>
int res = 0;
void preOrder(int i, int n){
    if(i <= n) res++;
    else return;
    preOrder(2 * i, n);
    preOrder(2 * i + 1, n);
}

int main(void){
    int m, n;
    while(scanf("%d%d", &m, &n) != EOF){
        res = 0;
        preOrder(m, n);
        printf("%d\n", res);
    }
    return 0;
}

发表于 2018-03-08 13:30:52 回复(0)

Lan.Bing#ZiYi

#include <iostream>

int main(){
    int m,n;
while(std::cin>>m>>n)
    {
        
		if( m==0 && n==0) break;
        int a=m,b=m,h=1;
        
        while(a*2<=n) 
        {
            h++;
            a*=2;
            b=b*2+1;
        }
        int s=(1<<h)-1 ;
	if(n>b)
		std::cout << s<<std::endl;
	else
		std::cout << s-(b-n)<<std::endl;
    }
}

发表于 2017-03-17 16:13:54 回复(0)

C/C++

|讨厌鬼|

#include<stdio.h>
int countNode(int m,int n){
    if(m>n) return 0;
    return countNode(2*m,n)+countNode(2*m+1,n)+1;
} 
int main(){
    int m,n;
    while(scanf("%d%d",&m,&n)!=EOF){
        if(m==0&&n==0) break;
        printf("%d\n",countNode(m,n));
    }
    return 0;
}

编辑于 2019-03-08 12:27:05 回复(13)