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

各ノード (葉を除く) には 2 つの子があります。唯一の例外は、リストが次の場合です。

                              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

次に、配列の位置1(つまり、ノード 2) の場合:

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

これを続けるとi=0からi=6まで[6, 2, 2, 0, 0, 0, 0]となる。

このための 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]。

ただし、偶数番号の入力配列を処理するには、いくつかの変更が必要です (最も簡単な方法は、配列サイズを最も近い奇数に丸めてから、 の奇数番号の値から 1 を減算することですi)。

于 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 に答える