如何计算树中的孩子

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