Wie Kinder in einem Baum zählen

Question

Ich habe eine Liste von Zahlen:

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

Ich bin interessiert, einen Algorithmus zu finden, die die Gesamt Kinder in dieser Liste, wenn die Liste zusammenfassen können, wo ein Baum:

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

ich suche nach einem Algorithmus, geben würde:

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


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

Jeder Knoten (mit Ausnahme der Blätter) hat zwei Kinder. Die einzige Ausnahme ist, wenn die Liste selbst wenn:

       1 
          / \ 
          2  3 
         /\ /
         4 5 6 

ich einen Baum zu vermeiden, möchte den Aufbau und dann an jedem Knoten die Anzahl der Kinder zu zählen. Es muss einen einfachen mathematischen Weg geben, um die Anzahl der Kinder aus einer Liste zu zählen?

Answer 1

1 indiziert das Array.

Dann für Knoten mit Index i ist der linke Sohn mit dem Index 2 * i, und rechts ist die 2 * i + 1.

Dann gehen Sie durch das Array von dem Ende, für den Knoten jetzt:

wenn der Index seines (links oder rechts) Sohns aus dem gebundenen von Array ist, dann hat er keinen (links oder rechts) Sohn.

Wenn nicht, dann können Sie die Anzahl der Kinder seines Sohnes wissen (wir gehen durch das Array von dann Ende). Das Ergebnis = Anzahl der Kinder von jetzt Sohn + Anzahl von jetzt Sohn.

Zum Beispiel:

[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

Interpretieren das erste Array als Haufen, in denen die Kinder des Knotens n in 2 * n + 1 und 2 * n + 2, dann rekursiv den Baum fahren:

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) 

Dies drucken:

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

Answer 3

Für den Fall, dass der Baum Balance sterben. die Anzahl der Elemente in der Eingabeliste ungerade ist), kann dies mit berechnet werden:

n = length of elements in input list 

Dann gilt für Element i in der Ausgabeliste:

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

Dann ist die Anzahl der Kinder an diesem Element in der Baum ist:

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

So für Ihr Beispiel von [1,2,3,4,5,6,7]:

n = 7 

Für Array-Position 0 (d.h. 1 node):

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

Dann dann für Feldposition 1, (d.h.Knoten 2):

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

mit dieser Trage hat [6, 2, 2, 0, 0, 0, 0] für i = 0 bis i = 6.

Python-Code für diese würde wie folgt aussehen:

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)] 

Diese [6.0, 2.0, 2.0, 0.0, 0.0, 0.0, 0.0] ausgibt.

Es müsste allerdings etwas modifiziert werden, um mit geradzahligen Eingangsarrays umgehen zu können (am einfachsten ist es, die Arraygröße bis zur nächsten ungeraden Zahl zu runden und dann 1 von allen ungeraden Zahlen von i oder ähnlichem zu subtrahieren).

Answer 4

Wie wir in Haufen zu tun, Kinder [i] = Summe von Kindern alle Kindes + Anzahl der Kinder

Wie bei dem 0. Elemente, a [0] = Anzahl der Kinder seines linken Kindes + Nummer Kinder von ihrem Recht Kind + Anzahl seines Kind so 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;
}