首页 > 试题广场 >

二叉树

[编程题]二叉树
  • 热度指数: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

输出

4
这题的解题思路:根据题目给出的数的形态,判断出该树符合完全二叉树的特性,利用这一点来进行递归判断 如果结点i 的左孩子2*i<n 且结点2*i+1<n 则结点i的孩子总数+1 再一次递归遍历左右孩子结点即可,递归退出条件为2*i>n 或 2*i+1>n 则直接退出
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int count = 0;        //孩子的总结点数
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int m = in.nextInt();//求m结点一共有多少个结点
            int n = in.nextInt();//总结点数
            if (m == 0 && n == 0)
                break;
            //解题思路:分别求该结点的左右孩子有多少个结点即可
            getCount(m, n);
            System.out.println(count);
        }
    }
    public static void getCount(int i,
                                int n) {    //i表示第i个结点 n表示总结点数
        if (i > n)      //递归退出条件
            return;
        count++;        //结点总数+1
        getCount(i * 2, n);         //递归求左孩子结点总数
        getCount(i * 2 + 1, n);     //递归求右孩子结点总数
    }
}


发表于 2023-03-21 10:59:50 回复(0)
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)


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)