Convert the binary tree traversal index after ordering into a level index (width)

Question

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

For example, node indices of a simple full tree with a height of 3 would look like this:

width first (aka order):

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

post-order:

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

Given the height of the tree and the index in a roundabout way.

How can I calculate the width of the first index from this information?

Answer 1

I think it should be computed iteratively / recursively. Having said that, someone will come in 37 seconds with a simple one-line calculation and lower me. However, this can be solved by thinking about it recursively. Consider a simple tree (based on 1) of the first postoperative depth traversal:

  3 / \ 1 2 

From a recursive point of view, everything you need to think about. You are either located at the root of the subtree (3), either on the left side of the subtree (1), or on the right side (2). If you are at the root, then everything is ready. Otherwise, the left and right subtrees are the same, and the post-order traversal index in the right subtree is equal to the corresponding index of the left subtree + the number of nodes in the subtree.

The following code performs this calculation in O(log n) . For a tree with a depth of 10 (1023 nodes), it calculates an index value of a maximum of 10 iterations (recursion).

It keeps track of the depth of a given node and calculates the width position of the first row depending on whether it deals with left or right subtree. Note that this uses an index value based on 1. It was easier for me to think about it in these terms (a depth tree 2 has 3 nodes in it, and the top node in a roundabout order has 3). Also note that he believes that the depth of tree 1 has one node (I'm not sure if this is a typical convention or not).

 // Recursively compute the given post-order traversal index 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; // eg, 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; } 

Below are the values ​​calculated for the next tree (depth 4), which shows the values ​​of the post-order crawl index (based on 1).

  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 

Answer 2

Most likely, until you find a better answer:

• Create a tree from the array / index after ordering, making each node the value of the current index of the array.

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.

• Rotate the width of the tree first by putting the calculated width index on the map as the value of the displayed pair with the key of the node value. map.put( node.value, tree_visitor.current_index)

• Interrogate the map by passing the desired key (which is the post-order node index) to get the index of the corresponding node width.