二叉樹的編號 例題 6-6 小球下落問題 有一棵二叉樹，最大深度為D，且所有葉子深度都相同。所有節點從上到下，從左到右編號為1,2,3,4，....，2^D-1。在節點1處放置小球，他會往下落。每個節點上都有一個開關，初始全部關閉，每當有小球落到一個開關上時，狀態都會改變，當一個小球到達節點時，如果該節點上的開關關閉則往左走，否則往右走，直到走到葉子節點，一些小球從節點1處開始依次下落。最后一個小球回到哪里呢？輸入葉子深度D，小球個數I，輸入第I個小球最后所在的葉子編號。假設I不超過整棵樹的葉子個數，D<=20。輸入最多包含1000組數據。 **get ** 4 2 3 4 10 1 2 2 8 128 16 12345 put 12 7 512 3 255 36358

#include

#include

const int maxd=20;

int s[1<

int main()

{

int D,I;

while((cin>>D>>I)==2)

{

memset(s,0,sizeof(s));

int k=1,n=(1<

for(int i=0;i

{

k=1;

for(;;;)

{

s[k]=!s[k];

k=s[k]?2*k:2*k+1;

if(k>n)break;

}

}

cout<

}

return 0;

}

代碼非常基礎不難理解，用k表示小球現在所在的節點位置再進行判斷是否出界出界則跳出循環后進行下一步循環并且對k進行初始化，直到循環結束即第I個小球下落到底。

但是，這樣做的代碼有一個明顯的缺陷，那就是時間復雜度問題，運算量太大，由于I可以高達2^D-1，每組測試數據下落總層數可能會高達(2^19)*19=9961472，并且一共可能有10000組數據。 還有一種方法我們可以這樣理解，每個小球都會落到根節點上，并且前兩個小球一定必然是一個落在左邊子樹上一個落在右邊子樹上，一般的，只需要看小球編號的奇偶性，就能直到他最終會在那棵子樹中，對于那些落入根節點左子樹的小球來說，只需要知道該小球是第幾個落在根的左子樹，就可以直到他下一步往左還是往右了，依次類推，直到小球落到葉子上為止。 如果使用題目中給的編號I，則當I是奇數時，他是往左走的第(I+1)/2個小球，當I是偶數時，他是往右走的第I/2個小球。這樣，可以直接模擬最后一個小球的路線，實現代碼：

while((cin>>D>>I)==2)

{

int k=1;

for(int i=0;i

if(I%2){

k=k*2;

I=(I+1)/2;

}

else

{

k=k*2+1;

I/=2;

}

cout<

}

總結

以上是生活随笔為你收集整理的二叉树小球下落问题c语言,#C++初学记录（树和二叉树）的全部內容，希望文章能夠幫你解決所遇到的問題。

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