題目

有一棵二叉樹，最大深度為D，且所有的葉子深度都相同。所有結點從上到下從左到右編號為1，2，3，…，2eD-1。在結點1處放一個小球，它會往下落。每個結點上都有一個開關，初始全部關閉，當每次有小球落到一個開關上時，它的狀態都會改變。當小球到達一個內結點時，如果該結點的開關關閉，則往上走，否則往下走，直到走到葉子結點，如下圖所示。

一些小球從結點1處依次開始下落，最后一個小球將會落到哪里呢？輸入葉子深度D和小球個數I，輸出第I個小球最后所在的葉子編號。假設I不超過整棵樹的葉子數；D<=20。輸出最多包含1000組數據。
樣例輸入：
4 2
3 4
10 1
2 2
8 128
16 12345
樣例輸出：
12
7
512
3
255
36358

分析與解答

<0>.給定一顆2^d個結點的完全二叉樹，如果把結點從上到下從左到右編號，則結點k的左右子結點編號分別為2k，2k+1
<1>.根據觀察，對于根結點，小球編號為奇數落在左子樹，偶數落在右子樹
<2>.每個節點都可以看成根結點，并且與他兩個子結點組成一個新的二叉樹
<3>.根據根結點1，找規律發現，如果小球編號為奇數，他是往左走的第（i+1)/2個小球，如果小球編號為偶數，他是往右走的第i/2個小球。
<4>.如果把每個子節點看成一個根結點，那么每個結點的小球也滿足3的規律
<5>.第i個小球，從結點編號為k的地方下落，如果i為奇數，那么此時等價于第(i+1)/2個小球，從結點編號為k*2的地方下落，如果i為偶數，那么此時等價于第i/2個小球，從結點編號為k*2+1的地方下落，然后通過<1>，我們就知道他下一步是向左還是向右走
<6>.二叉樹深度為d，小球下落d-1次，每循環一次，我們就知道他落在哪，下一步怎么走，如果循環d-1次，剛好走到最后的葉子結點，此時知道他落在哪，輸出k就行

代碼：

#include<cstdio>int main(){int d,I;while(scanf("%d%d",&d,&I)==2){int k=1;for(int i=0;i<d-1;++i){if(I%2){k=k*2;I=(I+1)/2;}else {k=k*2+1;I/=2;}}printf("%d\n",k);} }

方法二：
利用模擬，二叉樹編號

#include<cstdio> #include<cstring> const int maxd =20; int s[1<<maxd]; int main(){int D,I;while(scanf("%d%d",&D,&I)){memset(s,0,sizeof(s));int k,n =(1<<D)-1;//n是最大節點編號 for(int i=0;i<I;++i){k=1;for(;;){s[k]!=s[k];//每次開關變化 k=s[k]?k*2:k*2+1;//根據開關狀態選擇下落方向 if(k>n) break;//出界了 }}printf("%d\n",k/2);//出界之前葉子編號 } }

總結

以上是生活随笔為你收集整理的(完全二叉树编号）小球下落的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。