numeric method for generating indices for in-order traversal of a tree stored in a list/array.

tree_inorder_traversal.py

def generate_jumps(height):                                                                                  
    if height <= 2:                                                                                          
        return []                                                                                            
    max_jump = height - 1                                                                                    
    jumps = []                                                                                               
    j = 3                                                                                                    
    for j in range(2, max_jump):                                                                             
        jumps = jumps + [j] + jumps                                                                          
    jumps.extend([max_jump] + jumps)                                                                         
    return jumps                                                                                             
                                                                                                             
                                                                                                             
def iter_jumps(height):                                                                                      
    if height <= 2:                                                                                          
        return                                                                                               
    max_jump = height - 1                                                                                    
    counters = [int(2 ** (n - 2) - 1) for n in range(0, height)]                                             
    counters.reverse()                                                                                       
    for i in xrange(2 ** (max_jump - 1) - 1):                                                                
        index = counters.index(i)                                                                            
        cur_jump = max_jump - index                                                                          
        counters[index] += (2 ** (cur_jump - 1))                                                             
        yield cur_jump                                                                                       
    return                                                                                                   
                                                                                                                          
def iter_in_order(height):                                                                                   
    left_lim = 2 ** (height - 1)                                                                             
    right_lim = (2 ** height)                                                                                
    jumps = generate_jumps(height)                                                                           
    c, j = left_lim, height                                                                                  
    while 1:                                                                                                 
        yield c                                                                                              
        right = (2 * c + 1)                                                                                  
        if right < right_lim:                                                                                
            c = int(2 ** (height - j - 1)) * right                                                           
            j = height                                                                                       
        elif c % 2 == 0:                                                                                     
            c /= 2                                                                                           
            j -= 1                                                                                           
        else:                                                                                                
            try:                                                                                             
                j = jumps.pop()                                                                              
            except IndexError:                                                                               
                break                                                                                        
            c = c >> j                                                                                       
            j = height - j                                                                                   
    return                                                                                                   
                                                                                                             
                                                                                                             
def gen_traversal_order(height):                                                                             
    return list(iter_in_order(height))                                                                       
                                            

>>> tree_test.gen_traversal_order(3)
[4, 2, 5, 1, 6, 3, 7]
>>> tree_test.gen_traversal_order(4)
[8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15]


>>> tree_test.generate_jumps(5)
[2, 3, 2, 4, 2, 3, 2]
>>> tree_test.generate_jumps(7)
[2, 3, 2, 4, 2, 3, 2, 5, 2, 3, 2, 4, 2, 3, 2, 6, 2, 3, 2, 4, 2, 3, 2, 5, 2, 3, 2, 4, 2, 3, 2]