題意：給定節點數n和所有節點的深度總和d，問能否構造出這樣的二叉樹，能，則輸出“YES”，并且輸出n-1個節點的父節點（節點1為根節點），
題解：n個節點構成的二叉樹中，完全（滿）二叉樹的深度總和最小，單鏈樹（左/右偏數）的深度總和最大，若d在這個范圍內，則一定能構造出來；否則一定構造不出來，
1.初始構造一顆單鏈樹，依次把底部的節點放入上面的層，直到滿足深度總和為d
2.若當前深度總和sum > d，則先拿掉底端節點，
拿掉后，若sum依然比d大，就直接把底端節點放入有空位的最上層；
拿掉后sum <= d，dif = d - sum，
若dif >= 此時有空位的最上層深度，則深度為dif的層一定有空位，把底端節點放入該層，即可完成構造，
否則，依然把底端節點放入有空位的最上層，修改后的sum依舊比d大，繼續回圈即可，
3.退出回圈后就完成了構造，獲得了所求的樹，
具體存盤結構、表示方式和演算法程序見代碼（和注釋）：
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 /* 5 9 21 6 YES 7 1 1 2 2 4 4 6 8 8 9 22 9 YES 10 1 1 2 2 4 6 6 7 11 */ 12 int layer[5005], num[5005]; //layer[i]先存第i+1個點所在層的深度，num[i]是深度為i的層里的節點數 13 14 int main() { 15 int t, n, d; 16 scanf("%d", &t); 17 while (t--) { 18 scanf("%d%d", &n, &d); 19 memset(num, 0, sizeof num); 20 int sum = n * (n - 1) / 2, dep = 0, minn = 0; 21 num[0] = 1; //0深度層只有一個根節點 22 for (int i = 2; i <= n; i++) { 23 //i&(i - 1)的結果為把i二進制下最后一個1置0，i&(i - 1) == 0時，i為2的整數次冪 24 if ((i&(i - 1)) == 0)dep++; //第i+1層的第一個節點為2^i 25 minn += dep; //minn記錄滿二叉樹時的深度總和 26 27 layer[i - 1] = i - 1; //單鏈樹時，和為sum，layer[i]是第i+1個點所在層的深度 28 num[i - 1] = 1; //num[i]記錄深度為i的層的節點總數 29 } 30 if (d<minn || d>sum) { 31 puts("NO"); 32 continue; 33 } 34 puts("YES"); 35 dep = 1; //當前有空位的最上層的深度 36 for (int i = n - 1; i > 0 && sum > d; i--) { 37 sum -= i; //拿掉底端頂點 38 num[i]--; 39 if (sum > d) { //拿掉之后，sum仍然比d大時；直接放最上面 40 layer[i] = dep; //第i+1個點現在的深度為dep 41 sum += dep; 42 43 if (++num[dep] == (1 << dep))dep++; //若最上面的層滿了，修改為下一層 44 } 45 else { //拿掉之后，sum<=d時 46 int dif = d - sum; //看差值對應的層是否有空位 47 if (dif >= dep) { //有空位，則直接放到深度等于差值的那一層，構造成功 48 layer[i] = dif; 49 sum += dif; //寫出來更好理解 50 num[dif]++; //該層節點數++ 51 break; 52 } 53 else { //無空位，只能放最上面dep層 54 layer[i] = dep; 55 sum += dep; //此時sum仍然 > d 56 if (++num[dep] == (1 << dep))dep++; //若最上面的層滿了，修改為下一層 57 } 58 } 59 } 60 //構造成功，layer[i]是原來單鏈樹中深度為i的點(第i+1個點) 現在的深度，num[i]是第i層的節點總數 61 //現只用num中的資訊求解；layer中的資訊只是輔助理解，現在用來存最終答案(即第i個節點的父節點編號) 62 int id(2), fid(1); //當前節點編號，上一層首個節點的編號 63 for (int i = 1; num[i]; i++) { // while(深度為i的層節點數不為0) 64 for (int j = 0; j < num[i]; j++) { 65 //深度為i的層的第j個節點，在完全二叉樹中的編號為(1<<i)+j，上一層首個節點編號為1<<(i - 1) 66 //layer[id++] = fid + ((1 << i) + j) / 2 - (1 << (i - 1)); 直接算這個式子會溢位 67 layer[id++] = fid + j / 2; //簡化后得出，也可以直接理解推出來 68 } 69 fid += num[i - 1]; 70 } 71 for (int i = 2; i < n; i++) 72 printf("%d ", layer[i]); 73 printf("%d\n", layer[n]); 74 } 75 return 0; 76 }
附 完全二叉樹編號：
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/205853.html
標籤：其他
下一篇：洗掉鏈表的倒數第N個節點