文章

33

粉丝

0

获赞

135

访问

3.7k

头像
二叉树 题解:完全二叉树的下标
P1233 北京大学机考题
发布于2026年3月20日 09:03
阅读数 93

surprisesurprisesurprisesurprisesurprisesurprisesurprisesurprisesurprisesurprisesurprisesurprisesurprisesurprisesurprisesurprisesurprisesurprisesurprisesurprisesurprise

如题,给了一个完全二叉树.并且无穷多.那么肯定存不下
但是根据学过的数据结构会有,
        某结点i
子节点2i        2i+1 ,

那么子节点回溯到父节点的下标只需要 x = x/2
那么只需要对比x y 谁在底下,那么谁先回溯。

#include <stdio.h>


int main(){

	int x,y;
	while(scanf("%d %d", &x, &y) == 2){//读取数据

	while(x != y){
		if(x > y){
			x = x / 2;//比如x=10  y=4  ,那么x在底下.x先回溯到与y同一层 
                      //x/=2 => x=5.那么仍有x>y  x/=2  => x=2  同理对y,有y/=2  => y=2 x=y则退出.
		}else if(x < y){
			y = y / 2;
		}else{
			break;
		}
	}
	printf("%d\n", x);
}
	return 0;
}

 

登录查看完整内容


登录后发布评论

1 条评论
HKX9XAS
2026年3月23日 17:12

当一开始输入的两个数本来就相等时,父节点是他们本身。

赞(0)
回复给: