模拟二叉树 — 纪念植树节…

模拟二叉树 — 纪念植树节……

给定一颗完全二叉树；可知道这棵树有以下特点：

1、若父亲结点为k，则其左孩子结点为2*k，右孩子结点为2*k+1

2、若深度为D，结点最多为(1<<D)  — 1 ；

有一些小球从结点1处依次开始下落，问最后一个小球将会落到哪里？

如果遇到这样的问题，肯定不能用深度遍历，原因是，每个小球都要从上往下依次下落。

可以用循环来做，但是时空复杂度比较高；

#include<iostream>
#include<string.h>
using namespace std ;

#define MAX 20

int main()	{
	int D , I ;
	cin >> D >> I ;
	int s[100] ;
	memset(s,0,sizeof(s)) ;
	int n = 1<<D - 1 ;
	int k ;
	for(int i = 1 ; i <= I ; i++)	
		for(k = 1 ; k <= n ; k = s[k] ? 2*k : 2*k+1 )	
			s[k] = !s[k] ;
	cout << k << endl ;
}

第二种方法就是模拟了，直接模拟最后一个球要走的路径，如果最后一个球是第 I 次放，若I为奇数，肯定是忘左走，否则往右走，到达下一层时，若I为奇数，I = (I+1) / 2 , 若为偶数，I = I / 2 ；然后再判断I为奇数还是偶数，若为奇数，则往左走，否则往右走。

#include<iostream>
using namespace std ;

int main()	{
	int D , I ;
	cin >> D >> I ;
	int k = 1 ;
	for(int i = 1 ; i < D ; i++)
		if(I&1)	{k *= 2 ; I = (I+1)/2 ;}
		else	{k = 2 * k + 1 ; I = I/2 ;}
	cout << k << endl ;
	return 0 ;
}