《算法競賽入門經典》6.3.1二叉樹-小球下落，java小球下落
有一棵二叉樹，最大深度為D，且所有的葉子深度都相同。所有結點從上到下從左到右編號為1，2，3，…，2eD-1。在結點1處放一個小球，它會往下落。每個結點上都有一個開關，初始全部關閉，當每次有小球落到一個開關上時，它的狀態都會改變。當小球到達一個內結點時，如果該結點的開關關閉，則往上走，否則往下走，直到走到葉子結點，如下圖所示。
一些小球從結點1處依次開始下落，最後一個小球將會落到哪裡呢？輸入葉子深度D和小球個數I，輸出第I個小球最後所在的葉子編號。假設I不超過整棵樹的葉子數；D<=20。輸出最多包含1000組數據。![]()
1 #include <stdio.h>
2 #include <string.h>
3 #define MAXN 20
4 int s[1<<MAXN]; //將1左移20位，即得最大結點個數為2eMAXN-1
5 int main(void)
6 {
7 int D, I;
8 while(scanf("%d%d", &D, &I) == 2)
9 {
10 memset(s, 0, sizeof(s)); //開關（默認0為關閉狀態），memset函數包含頭文件string.h
11 int k, n = (1<<D)-1; //n是最大結點編號
12 for(int i = 0; i < I; i++) //連續讓n個小球下落
13 {
14 k = 1;
15 for(; ;)
16 {
17 s[k] = !s[k];
18 k = s[k] ? k*2 : k*2+1; //根據開關狀態選擇下落方向
19 if(k > n) break; //已經落“出界”了，下落次數為D
20 }
21 }
22 printf("%d\n", k/2); //“出界”之前的葉子編號
23 }
24 return 0;
25 }
View Code
分析：
1.對於一個結點k，它的左兒子，右兒子的編號分別是2k和2k+1。
2.盡管每次小球都是嚴格下落D-1次，但上述代碼中采用“if(k>n) break”的方法判斷“出界”更具一般性。
3.該程序運算量太大：由於I可以高達2(D-1)，每個測試數據下落總層數可能會高達219*19（即I*19）=9961472,而一共可能有1000組數據。
方法二：
![]()
1 #include <stdio.h>
2 #include <string.h>
3 #define MAXN 20
4 int s[1<<MAXN]; //將1左移20位，即得最大結點個數為2eMAXN-1
5 int main(void)
6 {
7 int D, I; //定義小球的個數,即最後一個小球編號為I
8 //直接模擬最後一個小球的路線
9 while(scanf("%d%d", &D, &I) == 2)
10 {
11 memset(s, 0, sizeof(s)); //開關（默認0為關閉狀態），memset函數包含頭文件string.h
12 int k; //n是最大結點編號
13 for(int i = 0; i < I; i++) //連續讓n個小球下落
14 {
15 k = 1;
16 for(int i = 0; i < D-1; i++) //連續進行D-1次下落
17 if(I%2) { k = k*2; I = (I+1)/2; } //當I為奇數時，它是往左走的第（I+1）/2個小球
18 else { k = k*2+1; I /= 2; } //當I為偶數時，它是往右走的第I/2個小球
19 }
20 printf("%d\n", k); //輸出最後一個小球I的葉子編號
21 }
22 return 0;
23 }
View Code
分析：
1. （1）由於每個小球都會落在根節點上，前兩個小球必然是一個在左子樹，一個在右子數；則一般情況下，只需看小球編號的奇偶性，就能知道它是最終在哪棵子樹中。
（2）對於那些落入根節點落入左/右子樹的小球，只需知道該小球是第幾個落在根的左/右子樹裡，就可以知道它下一步往左還是往右。
（3）依此類推，直到小球落在葉子上。
2.程序不僅其運算量與小球編號無關，而且節省了一個巨大的數組s。
3.使用小技巧I%2判斷，避開對I奇偶性的討論。
