assuming complete binary tree, each node can adressed position appears in given tree traversal algorithm.
for example, node indices of simple complete tree height 3 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 tree , index in post-order traversal given.
how can calculate breadth first index information?
i think has computed iteratively/recursively. having said that, come along in 37 seconds simple single-line computation , downvote me. nonetheless, can solved thinking of recursively. consider simple tree (1-based) of depth-first post-order traversal:
3 / \ 1 2
from recursive standpoint, that's have think about. either @ root of subtree (3), in left part of subtree (1) or in right part (2). if @ root, done. otherwise, left , right subtrees identical , post-order traversal index in right subtree equal corresponding left subtree index + number of nodes in subtree.
the following code performs computation in o(log n). tree depth 10 (1023 nodes), computes index value in maximum of 10 iterations (recursions).
it tracks depth of given node , computes breadth-first row position based on whether dealing left or right subtree. note uses 1-based index values. found simpler think of in terms (a tree of depth 2 has 3 nodes in , top-most node in post-order traversal 3). note considers tree depth of 1 have 1 node (i'm not sure if typical convention or not).
// recursively compute given post-order traversal index's position // in tree: position in given level , depth in tree. void computepos( int treedepth, int poindex, int *levelposition, int *nodedepth ) { int nodes; int half; // compute number of nodes 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 ) { // post-order index value root of subtree //printf( " root\n" ); return; } else if ( poindex > half ) { // index in right subtree //printf( " right\n" ); poindex -= half; *levelposition = 2 * *levelposition + 1; } else { // otherwise must in left subtree //printf( " left\n" ); *levelposition = 2 * *levelposition; } treedepth -= 1; computepos( treedepth, poindex, levelposition, nodedepth ); } int main( int argc, char* argv[] ) { int levelposition = 0; // 0-based index left in given level int nodedepth = 0; // depth of node in tree int bfindex; int treedepth = atoi( argv[1] ); // full depth of 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 breadth-first index position in current // level plus count of nodex in levels above it. bfindex = levelposition + ( 1 << ( nodedepth - 1 )); printf( "post-order index %3d = breadth-first index %3d\n", poindex, bfindex ); return 0; }
here values computed following tree (depth 4), shows 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) 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
Comments
Post a Comment