Convert a post-order binary tree traversal index to an level-order (breadth-first) index

Assuming a complete binary tree, each node can be adressed with the position it appears in a given tree traversal algorithm.

For e开发者_JS百科xample, the node indices of a simple complete tree with height 3 would look like this:

breadth first (aka level-order):

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

post-order dept first:

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

The height of the tree and an index in the post-order traversal is given.

How can i calculate the breadth first index from this information?

I think it has to be computed iteratively/recursively. Having said that, someone will come along in 37 seconds with a simple single-line computation and downvote me. Nonetheless, it can be solved by thinking of it recursively. Consider the simple tree (1-based) of a depth-first post-order traversal:

   3
  / \
 1   2

From a recursive standpoint, that's all you have to think about. You are either at the root of the subtree (3), in the left part of the subtree (1) or in the right part (2). If you are at the root, then you are done. Otherwise, the left and right subtrees are identical and the post-order traversal index in the right subtree is equal to the corresponding left subtree index + the number of nodes in the subtree.

The following code performs this computation in O(log n). For a tree with depth 10 (1023 nodes), it computes the index value in a maximum of 10 iterations (recursions).

It tracks the depth of the given node and computes the breadth-first row position based on whether it is dealing with the left or right subtree. Note that this uses 1-based index values. I found it simpler to think of it in those terms (a tree of depth 2 has 3 nodes in it and the top-most node in a post-order traversal is 3). Also note that it considers a tree depth of 1 to have one node (I'm not sure if that is the typical convention or not).

// Recursively compute the given post-order traversal index's position
// in the tree:  Its position in the given level and its depth in the tree.
void ComputePos( int treedepth, int poindex, int *levelposition, int *nodedepth )
{
    int nodes;
    int half;

    // compute number of nodes for this depth.
    assert( treedepth > 0 );
    nodes = ( 1 << ( treedepth )) - 1;
    half = nodes / 2;   // e.g., 7 / 2 = 3

    //printf( "poindex = %3d, Depth = %3d, node count = %3d", poindex, treedepth, nodes );

    (*nodedepth)++;

    if ( poindex == nodes ) {
        // This post-order index value is the root of this subtree
        //printf( "  Root\n" );
        return;
    }
    else if ( poindex > half ) {
        // This index is in the right subtree
        //printf( "  Right\n" );
        poindex -= half;
        *levelposition = 2 * *levelposition + 1;
    }
    else {
        // Otherwise it must be in the left subtree
        //printf( "  Left\n" );
        *levelposition = 2 * *levelposition;
    }

    treedepth -= 1;
    ComputePos( treedepth, poindex, levelposition, nodedepth );
}

int main( int argc, char* argv[] )
{
    int levelposition = 0;   // the 0-based index from the left in a given level
    int nodedepth = 0;  // the depth of the node in the tree
    int bfindex;
    int treedepth = atoi( argv[1] );   // full depth of the tree (depth=1 means 1 node)
    int poindex = atoi( argv[2] ); // 1-based post-order traversal index

    ComputePos( treedepth, poindex, &levelposition, &nodedepth );

    //printf( "ComputePos( %d, %d ) = %d, %d\n", treedepth, poindex, levelposition, nodedepth );

    // Compute the breadth-first index as its position in its current
    // level plus the count of nodex in all the levels above it.
    bfindex = levelposition + ( 1 << ( nodedepth - 1 ));
    printf( "Post-Order index %3d = breadth-first index %3d\n", poindex, bfindex );

    return 0;
}

Here are the values computed for the following tree (depth 4), which shows the post-order traversal index values (1-based).

            15
          /    \
         /      \
        /        \
       /          \
      /            \
     7             14     
    / \            / \    
   /   \          /   \   
  3     6       10    13  
 /\    / \      /\    / \ 
1  2  4   5    8  9  11  12


[C:\tmp]for /l %i in (1,1,15) do po2bf 4 %i
Post-Order index   1 = breadth-first index   8
Post-Order index   2 = breadth-first index   9
Post-Order index   3 = breadth-first index   4
Post-Order index   4 = breadth-first index  10
Post-Order index   5 = breadth-first index  11
Post-Order index   6 = breadth-first index   5
Post-Order index   7 = breadth-first index   2
Post-Order index   8 = breadth-first index  12
Post-Order index   9 = breadth-first index  13
Post-Order index  10 = breadth-first index   6
Post-Order index  11 = breadth-first index  14
Post-Order index  12 = breadth-first index  15
Post-Order index  13 = breadth-first index   7
Post-Order index  14 = breadth-first index   3
Post-Order index  15 = breadth-first index   1

Brute-force way, until you find a better answer:

1. Build the tree from the post-order array/index, making each node's value the current array index.

Consume the index: The first half of the index is your left subtree, the second half is your right subtree, the middle node is the root. Recurse for each subtree.

1. Traverse the tree breadth-first, putting the calculated breadth-first index into map as the value of the mapped pair, with the key the node's value. map.put( node.value, tree_visitor.current_index)

2. Interrogate the map, passing on the desired key (which is the index of the post-order node) to get the index of the corresponding breadth-first node.