问题与解答

问题描述

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

输入格式

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

输出格式

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

样例输入

3 12

0 0

样例输出

4

#include<stdio.h>

#include<queue>      //队列

using namespace std;

int main()

{

    int m,n,x,num;

    queue<int> Q; //创建队列保存子树结点

    while(scanf("%d%d", &m,&n)!=EOF && m && n)  //多点测试

    {

        num = 0;

        Q.push(m); //加入第一个结点

        num++;     //sum++

        while(1)

        {

            /*取出当前结点*/

            x = Q.front();

            Q.pop();

            /*添加当前结点的子树结点*/

            if(2*x <= n)   {Q.push(2*x);   num++;} //每添加一个结点sum++

            else break;

            if(2*x+1 <= n) {Q.push(2*x+1); num++;}

            else break;

        }

        while(!Q.empty()) Q.pop();  //不要忽略

        printf("%d\n", num);

    }

}

题后反思: 本质是BFS

这题的本质是遍历结点
遍历有两种实现方式：BFS\DFS
- BFS: 利用队列暂存元素
- DFS: 利用栈暂存元素
这题原解法的实质就是BFS, 而且不难知道，这题也可以用DFS(递归)求解，不过这往往涉及树的二叉链表实现，会比较繁琐

巴特西

<数据结构>XDOJ314.完全二叉树的子树

问题与解答

题后反思: 本质是BFS

最新文章

热门文章