algorithm - 如何数一棵树上的 child

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

每个节点(叶子节点除外)都有两个子节点。唯一的异常(exception)是如果列表是偶数:

                              1
                            /   \
                           2     3
                          / \   / 
                         4   5 6   

我想避免构建一棵树，然后计算每个节点的 child 数量。必须有一种简单的数学方法来计算列表中 child 的数量吗？

Answer 1

1-索引数组。

然后对于索引为 i 的节点，左儿子的索引为 2*i，右儿子为 2*i+1。

然后从最后遍历数组，对于现在的节点:

如果他(左或右)儿子的索引超出数组范围，则他没有(左或右)儿子。

如果不是，那么就可以知道他儿子的 child 数(从那一端开始遍历数组)。结果=现在儿子的 child 数+现在儿子的数量。

例如:

[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