How to count children on a tree

Question

I have a list of numbers:

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

I am interested in finding an algorithm that can summarize the total number of children in this list, if the list is where the tree is:

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

I am looking for an algorithm that will give:

 [6, 2, 2, 0, 0, 0, 0] A = 6 B = 2 C = 2 D = 0 E = 0 F = 0 G = 0 

Each node (except leaves) has two children. The only exception is if the if even list:

  1 / \ 2 3 / \ / 4 5 6 

I would like to avoid creating a tree and counting the number of children in each node. Should there be a simple mathematical way to count the number of children from a list?

Answer 1

1-indexed array.

Then for node with index i, the left son has the index 2 * i, and the right one has 2 * i + 1.

Then go to the array from the end, now for node:

if the index of his (left or right) son goes beyond the bounds of the array, then he does not have (left or right) son.

If not, then you can find out the number of children of your son (we go through the array from the end). Result = number of children now son + number now son.

For instance:

 [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

In the case when the tree is balanced (i.e. the number of elements in the input list is odd), this can be calculated using:

 n = length of elements in input list 

Then for item i in the output list:

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

Then the number of children below this element in the tree:

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

So, for your example [1,2,3,4,5,6,7]:

 n = 7 

For array position 0 (i.e. node 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 for the position of array 1 (i.e. node 2):

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

Performing this, we obtain [6, 2, 2, 0, 0, 0, 0] for i = 0 to i = 6.

Python code for this would look like this:

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

This outputs [6.0, 2.0, 2.0, 0.0, 0.0, 0.0, 0.0] .

This will require some modification to work with numbered input arrays (the easiest way would be to round the size of the array to the nearest odd number, then subtract 1 from any odd numbered values ​​of i or similar).

Answer 3

Interpret the first array as a bunch in which the children from node n are in 2 * n + 1 and 2 * n + 2, and then recursively move through the tree:

 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) 

This will print:

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

Answer 4

As in the heap, children [i] = the sum of the children of the whole child + the number of children

As for the 0th element, a [0] = the number of children of his left child + the number of children of his right child + the number of his child therefore 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;
}