On Dec 18, 4:34 am, Mr.SpOOn <mr.spoo...@gmail.com> wrote: > 2008/12/17 Terry Reedy <tjre...@udel.edu>: > > > Nodes only have single number indexes if you arrange them linearly. Then the > > index depends on how you arrange them, whether you start the array indexes > > with 0 or 1, and whether you start the level numbers with 0 or 1. Call the > > breadth-first sequence bf. Then the 1-based slice for 1-first level k is > > bf[2**(k-1):2**k)]. Again, proof by induction. > > Yes, I was referring to the heap numeration. > Anyway, Francesco Guerrieri answered me in a private message and > explained me the formula. > > But actually I was searching for other similar properties.
A tree with one node A, can have two children A CD C and D can each have two children A CD EF GH Taking 'x' to be the level number, each level can have 2**x members. Each member is a child of the higher level. You see the pattern, 1, 2, 4... then 8, 16, etc. The total number of nodes at a level is 2**x plus its earlier levels. 2**x + 2**(x-1) + ... + 2**0. = 2**(x+1) - 1. Taking the log2 of both sides, we have: log2 count_of_nodes = log2( 2**(x+1) - 1 ) Better yet: log2 ( count_of_nodes + 1 ) = log2( 2**(x+1) ) log2 ( count_of_nodes + 1 ) = x+1 -- http://mail.python.org/mailman/listinfo/python-list
