Làm thế nào để đếm con trong một cây

Question

Tôi có một danh sách các số:

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

Tôi quan tâm đến việc tìm kiếm một thuật toán mà có thể tóm tắt tổng số trẻ em trong danh sách này nếu danh sách, nơi một cây:

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

tôi đang tìm một thuật toán mà sẽ cung cấp cho:

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


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

Mỗi nút (trừ lá) có hai trẻ em. Ngoại lệ duy nhất là nếu danh sách nếu ngay cả:

       1 
          / \ 
          2  3 
         /\ /
         4 5 6 

Tôi muốn tránh xây dựng một cây và sau đó đếm số lượng trẻ em tại mỗi nút. Phải có một cách toán học đơn giản để đếm số lượng trẻ em từ một danh sách?

Answer 1

1-đã lập chỉ mục mảng.

Sau đó đối với nút có chỉ mục i, con trai trái là chỉ mục 2 * i và bên phải là 2 * i + 1.

Sau đó đi qua mảng từ cuối cùng, cho nút bây giờ:

nếu chỉ số (trái hoặc phải) con trai của ông là ra khỏi ràng buộc của mảng, sau đó ông không có con trai (hoặc phải trái).

Nếu không, thì bạn có thể biết số con của con trai mình (chúng tôi đi qua mảng từ cuối đến cuối). Kết quả = số con của con trai hiện tại + số con trai của bây giờ.

Ví dụ:

[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

Giải thích các mảng đầu tiên như một đống, trong đó trẻ em của nút n là 2 * n + 1 và 2 * n + 2, sau đó đệ quy đi cây:

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) 

này sẽ in:

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

Answer 3

Đối với trường hợp cây là sự cân bằng chết. số phần tử trong danh sách đầu vào là số lẻ), điều này có thể được tính bằng:

n = length of elements in input list 

Sau đó cho các phần tử i trong danh sách kết quả:

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

Sau đó, số lượng trẻ em dưới rằng phần tử trong cây là:

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

vì vậy, ví dụ bạn của [1,2,3,4,5,6,7]:

n = 7 

Đối với vị trí mảng 0 (tức là nút 1):

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

Sau đó đến vị trí mảng sau đó 1, (tức lànút 2):

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

Thực hiện với điều này cho [6, 2, 2, 0, 0, 0] cho i = 0 đến i = 6.

mã Python cho điều này sẽ như thế nào:

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

này kết quả đầu ra [6.0, 2.0, 2.0, 0.0, 0.0, 0.0, 0.0].

Cần sửa đổi để xử lý các mảng đầu vào được đánh số chẵn (cách dễ nhất có thể là làm tròn kích thước mảng lên số lẻ gần nhất, sau đó trừ 1 từ bất kỳ giá trị số lẻ nào là i hoặc tương tự).

Answer 4

Giống như chúng ta làm trong đống, trẻ em [i] = tổng của trẻ em của tất cả các con + số của con

Giống như cho các phần tử 0, a [0] = số lượng trẻ em của con trái của nó + số trẻ em của con phải của nó + số con của nó do đó, một [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;
}