如何在樹上數兒童

Question

我有號碼的清單：

[1, 2, 3, 4, 5, 6, 7] 

我感興趣的是找到一種算法，可以歸納總孩子在此列表中如果列表，其中一棵樹：

       1 
          / \ 
          2  3 
         /\ /\ 
         4 5 6 7 

我正在尋找一種算法，會給：

[6, 2, 2, 0, 0, 0, 0] 


A = 6 
B = 2 
C = 2 
D = 0 
E = 0 
F = 0 
G = 0 

每個節點（除了葉）有兩個孩子。唯一的例外是，如果列表中如果連：

       1 
          / \ 
          2  3 
         /\ /
         4 5 6 

我想避免建立一個樹，然後在每個節點計數的兒童人數。必須有一個簡單的數學方法來計算列表中的孩子數量？

Answer 1

1索引的數組。

然後，對於索引爲i的節點，左邊的子是索引2 * i，右邊是2 * i + 1。

然後通過陣列走在最後，對於現在的節點：

，如果他（左或右）兒子的指數是越界陣列，那麼他有沒有（左或右）的兒子。

如果沒有，那麼你可以知道他兒子的子女數（我們從那時開始經過數組）。結果=現在的兒子的子女數+現在的兒子數。

例如：

[1, 2, 3, 4, 5, 6, 7] 
A is the result array. 
1.A=[0, 0, 0, 0, 0, 0, 0],now(now is a index) = 7(1-indexed) since 7*2>7, a[7]=0 
2.A=[0, 0, 0, 0, 0, 0, 0],now = 6,since 6*2>7, a[6]=0 
3.A=[0, 0, 0, 0, 0, 0, 0],now = 5,since 5*2>7, a[5]=0 
4.A=[0, 0, 0, 0, 0, 0, 0],now = 4,since 4*2>7, a[4]=0 
5.A=[0, 0, 2, 0, 0, 0, 0],now = 3,since 3*2<7 and 3*2+1<7, a[3]=2+a[6]+a[7]=2 
6.A=[0, 2, 2, 0, 0, 0, 0],now = 2,since 2*2<7 and 2*2+1<7, a[2]=2+a[4]+a[5]=2 
7.A=[6, 2, 2, 0, 0, 0, 0],now = 1,since 1*2<7 and 1*2+1<7, a[1]=2+a[2]+a[3]=6 

Answer 2

解釋所述第一陣列作爲堆，其中節點n的孩子們在2 * n + 1和2 * N + 2，則遞歸地遊樹：

def children(t, n): 
    if 2 * n + 1 >= t: 
     return 0 
    elif 2 * n + 2 >= t: 
     return 1 
    else: 
     return 2 + children(t, 2 * n + 1) + children(t, 2 * n + 2) 

size = 7 
childcounts = [ children(size, i) for i in range(size) ] 
print(childcounts) 

這將打印：

[6,2，2，0，0，0，0]

Answer 3

對於情況下樹是平衡死。元件的輸入列表中的數量是奇數），這可以用下式計算：

n = length of elements in input list 

然後，對於在輸出列表中元素i：

d = depth of element in tree = floor(log2(i+1))+1 

然後，在該元件下方的兒童數量樹是：

n_children = n - ((2^d)-1)/2^(d-1) 

因此，對於你[1,2,3,4,5,6,7]的例子：

n = 7 

對於陣列位置0（即，節點1）：

d = depth = floor(log2(1))+1 = 1 
n_children = (7 - ((2^1)-1))/2^(1-1) 
      = (7 - 1)/2^0 
      = 6/1 
      = 6 

然後，對於那麼陣列位置1（即，節點2）：

d = depth = floor(log2(2))+1 = 2 
n_children = (7 - ((2^2)-1))/2^(2-1) 
      = (7 - 3)/2 
      = 2 

對此進行[6,2,2,0,0,0,0]（i = 0到i = 6）。

這個Python代碼看起來像：

import math 

def n_children(list_size, i): 
    depth = math.floor(math.log(i+1,2)) + 1 
    return (list_size - ((2**depth)-1))/2**(depth-1) 

print [n_children(7, i) for i in range(7)] 

此輸出[6.0, 2.0, 2.0, 0.0, 0.0, 0.0, 0.0]。儘管（最簡單的方法可能是將數組大小舍入爲最接近的奇數，然後從任何奇數值i或類似值中減1），但需要進行一些修改來處理偶數編號的輸入數組。

Answer 4

就像我們在堆做， 兒[i] =及其所有子+號子的

像第0個元素，[0] =它的左子+號的兒童人數的兒童總和它的右子+其子 數量的孩子這麼的[0] = 2 + 2 + 2

for(int i=n-1;i>=0;i--) {
if(i*2+2 < n) a[i]+=a[i*2+2]+1;
if(i*2+1 < n) a[i]+=a[i*2+1]+1;
}