首页 > 试题广场 >

二叉树

[编程题]二叉树

热度指数：14610 时间限制：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

输出

算法知识视频讲解

Java

爱吃碳水的克里斯

这题的解题思路:根据题目给出的数的形态，判断出该树符合完全二叉树的特性，利用这一点来进行递归判断如果结点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

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)

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)