#二叉树子树节点判断#北京大学机试#acwing
思路:本题给出总节点数n和子树根节点m,先使用位运算计算出每组数据对应的根节点层数和树的总层数,此时用两个变量分别逐层记录该子树某层最左和最右节点的编号,直到最底层。此时:
若总结点数落在左和右之中,则子树节点为完全n-1层+多余节点,其他情况较为简单
接下来分别打印treenum即可
/*如上所示,由正整数 1,2,3……组成了一颗特殊二叉树。我们已知这个二叉树的最后一个结点是 n。现在的问题是,结点 m所在的子树中一共包括多少个结点。 比如,n=12,m=3那么上图中的结点 13,14,15以及后面的结点都是不存在的,结点 m所在子树中包括的结点有 3,6,7,12,因此结点 m的所在子树中共有 4个结点。 输入格式:输入数据包括多行,每行给出一组测试数据,包括两个整数 m,n。最后一行 0 0 表示输入结束。 输出格式:对于每一组测试数据,输出一行,该行包含一个整数,给出结点 m所在子树中包括的结点的数目。 数据范围:1≤m≤n≤109,最多包含 20组数据。 输入样例: 3 12 0 0 输出样例: 4 */ #include <cstdio> #include <iostream> using namespace std; int main() { int n = 12, m = 3; while (1){ scanf("%d%d", &m, &n);//输入数据 if (m == 0 && n == 0) { break; } int i = 1;//从一层开始获取层数 int begin_level = 0;//存储子树的根在第几层 int final_level = 0;//存储树的总层数 while (1) { if (m >= 1 << (i - 1) && m < 1 << i) { begin_level = i; } if (n >= 1 << (i - 1) && n < 1 << i) { final_level = i; break; } ++i; } int left_side = m; int right_side = m; for (i = begin_level; i < final_level; i++) { left_side = left_side * 2; right_side = right_side * 2 + 1; } int treenum = 0; if (left_side > n) { //说明m叶节点都在倒数第二层 treenum = (1 << (final_level - begin_level)) - 1; } else if (right_side >= n) {//说明m子树有一部分叶节点在最后一层 treenum = (1 << (final_level - begin_level)) + n - left_side; } else { treenum = (1 << (final_level - begin_level + 1)) - 1;//说明子树叶节点全在最后一层 } printf("%d\n", treenum); } return 0; }