0.前言   

     二叉树（Binary Tree）的递归定义如下：二叉树要么为空，要么由根结点（root）、左子树（left subtree）和右子树（right subtree）组成，而左子树和右子树分别是一棵二叉树。

    树（tree）和二叉树类似，区别在于每个结点不一定只有两棵子树。比如树的目录，根结点有12棵子树：第1章，第2章，第3章，。。。、第12章，而第一章又有5棵子树：1.1，1.2，1.3，。。。1.5。

1.二叉树的编号

    【例题】6-6 小球下落

    【题目描述】

     有一棵二叉树，最大深度为D，且所有叶子的深度都相同。所有结点从上到下从左到右编号为1，2，3，。。。，2D-1。在结点1处放一个小球，它会往下落。每个内结点上都有一个开关，初始全部关闭。每当有小球落在一个开关上时，状态都会改变。当小球到达一个内结点时，如果该结点上的开关关闭，则往左走，否则往右走，直到走到叶子结点。如下图所示

一个小球从结点1开始依次下落，最后一个小球将会落在哪里？输入叶子深度D和小球个数I，输出第I个小球最后所在的叶子编号。假设I不超过整棵树的叶子个数。D<=20。输入最多包含1000组数据。

【样例输入1】

4 2  3 4  10 1  2 2  8 128  16 12345

【样例输出1】

12  7  512  3  255  36358

【题目分析】

• 可以发现，对于一个结点K、右子树结点的编号分别是2K和2K+1。这个结论非常重要。

• 给定一棵包含2d个结点（其中d为树的高度）的完全二叉树，如果把结点从上到下左右编号为1，2，3...，则结点k的左右子结点编号分别为2K和2K+1。、、

  
  
  

【参考代码】

#include<cstdio>  #include<cstring>  const int maxd=20;  int s[1<<maxd]; //最大结点个数为2^maxd -1  int main(){  	int D,I;  	while(scanf("%d%d",&D,&I)==2){  		memset(s,0,sizeof(s)); //开关  		int k,n=(1<<D)-1;// n是最大结点的编号  		for(int i=0;i<I;i++)  //连续让i个球下落   		{  			k=1;  			for(;;){  				s[k]=!s[k];  				k=s[k]? k*2: k*2+1;  //根据开关状态选择下落方向  				if(s > n) break;   			}   		}   		printf("%d\n",k/2); //"出界"之前的叶子编号   	}  	return 0;   }

(adsbygoogle = window.adsbygoogle || []).push({});