ポストオーダーのバイナリツリートラバーサルインデックスをレベル順（幅優先）インデックスに変換する

Question

完全なバイナリツリーであると仮定すると、各ノードは所与のツリートラバーサルアルゴリズムに現れる位置で忠告することができる。

例えば、高さ3を有する単純な完全なツリーのノードのインデックスは次のようになります最初

幅（別名レベル順）：最初

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

ポスト次DEPT：

を

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

ポストオーダートラバーサルのツリーの高さとインデックスが与えられます。

この情報から幅優先の最初のインデックスを計算するにはどうすればよいですか？

Answer 1

反復的に/再帰的に計算する必要があると思います。それを言っても、誰かが37秒で簡単な1行の計算で降りてきてくれますし、私を落胆させます。それにもかかわらず、再帰的に考えることで解決できます。それはあなたが考えるように持っているすべてです、再帰的な観点から

3 
/\ 
1 2 

：深さ優先ポスト順トラバーサルのシンプルなツリーを（1ベース）を検討してください。サブツリーのルート（3）、サブツリーの左側（1）、または右側のパート（2）のいずれかにあります。あなたがルートにいる場合、あなたは完了です。それ以外の場合、左右のサブツリーは同一であり、右のサブツリーのポストオーダートラバーサルインデックスは、対応する左のサブツリーインデックス+サブツリー内のノードの数に等しい。

この計算はO(log n)で実行されます。深度10（1023ノード）のツリーの場合、最大10回の反復（再帰）でインデックス値が計算されます。

これは、指定されたノードの深さを追跡し、左または右のサブツリーを扱っているかどうかに基づいて幅優先の行の位置を計算します。これは、1ベースのインデックス値を使用することに注意してください。これらの用語で考えるのは簡単です（深さ2のツリーに3つのノードがあり、ポストオーダートラバーサルの最上位のノードは3です）。また、ツリーの深さが1であるとみなして、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 

Answer 2

ブルートフォース方法、あなたはより良い答えを見つけるまで：

1. は、各ノードの値を現在の配列インデックスを作成、ポスト・オーダーの配列/インデックスからツリーを構築します。

インデックスを消費します。インデックスの前半は左サブツリー、後半は右サブツリー、中間ノードはルートです。各サブツリーの再帰。ツリーの幅優先トラバース

1. 、キーノードの値と、マッピングされた一対の値としてマップに算出し幅優先のインデックスを置きます。 map.put(node.value, tree_visitor.current_index)

2. 対応する幅優先ノードのインデックスを取得するために、目的のキー（ポストオーダーノードのインデックス）を渡して、マップを問い合わせます。