将后序遍历的二叉树索引转换为层序（广度优先）索引

Question

假设有一棵完全二叉树，可以通过遍历算法中节点出现的位置来确定每个节点的地址。

例如，高度为3的简单完全二叉树的节点索引如下所示：

广度优先（也称层序）遍历：

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

后序遍历优先：

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

已知树的高度和后序遍历中的一个索引。

如何从这些信息计算出广度优先遍历的索引？

- strfry

Answer 1

我认为这必须通过迭代/递归计算来完成。尽管如此，可能会有人在37秒内提供一个简单的单行计算方法，并给我点个踩。然而，可以通过递归思考来解决它。考虑深度优先后序遍历的简单树（基于1）：

   3
  / \
 1   2

从递归的角度来看，这就是你需要考虑的所有内容。你要么在子树的根部（3），要么在左侧子树（1），要么在右侧子树（2）。如果你在根处，那么就完成了。否则，左右子树是相同的，右子树的后序遍历索引等于相应的左子树索引+子树中节点的数量。

以下代码以O(log n)的时间复杂度执行此计算。对于深度为10（1023个节点）的树，它最多在10次迭代（递归）中计算出索引值。

它跟踪给定节点的深度，并基于其处理左侧或右侧子树来计算广度优先行位置。请注意，它使用基于1的索引值。我发现用这种方式更容易理解（深度为2的树有3个节点，在后序遍历中，最上面的节点是3）。还请注意，它认为树的深度为1有一个节点（我不确定这是否是典型惯例）。

// 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;
}

以下是计算出的数值，针对以下树形结构（深度为4），显示了后序遍历索引值（从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

- Mark Wilkins

Answer 2

暴力方法，直到找到更好的答案：

1. 从后序数组/索引构建树，使每个节点的值为当前数组索引。

消耗索引：索引的前一半是左子树，后一半是右子树，中间节点是根。对于每个子树进行递归。

1. 广度优先遍历树，将计算出的广度优先索引放入映射的值中，以节点的值作为键。 map.put(node.value, tree_visitor.current_index)

2. 查询映射，将所需的键（即后序节点的索引）传递给它，以获取相应广度优先节点的索引。

- tpdi