7

我有一个数字列表：

[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

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

4

4 回答 4

4

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
于 2013-04-26T11:09:20.777 回答
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

然后对于 then 数组位置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] for i=0 to 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）。

于 2013-04-26T12:02:42.423 回答
1

将第一个数组解释为堆，其中节点 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]

于 2013-04-26T11:27:24.683 回答
0

就像我们在堆中所做的那样，children[i] = 其所有孩子的孩子的总和 + 孩子的数量

与第 0 个元素一样，a[0] = 其左孩子的孩子数量 + 其右孩子的孩子数量 + 其孩子的数量 所以 a[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;
}

于 2013-04-27T10:27:33.993 回答