將後序二叉樹遍歷索引轉換爲水平順序（寬度優先）索引

假設一個完整的二叉樹，每個節點可以用它在給定的樹遍歷算法中出現的位置來處理。將後序二叉樹遍歷索引轉換爲水平順序（寬度優先）索引

例如，一個簡單的完整的樹有高度3節點指標應該是這樣的：

廣度優先（又名級順序）：

後序部門第一：

給出了樹的高度和後序遍歷中的索引。

如何從這些信息計算廣度優先指數？

來源

2010-12-20 strfry

我認爲它必須迭代/遞歸計算。話雖如此，有人會用簡單的單線計算在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

來源

2010-12-21 04:50:07

蠻力方式，直到找到一個更好的答案：

從後序排列/索引構建樹，使得每個節點的值當前數組索引。

消費索引：索引的前半部分是你的左子樹，後半部分是你的右子樹，中間節點是根。遞歸每個子樹。

遍歷樹廣度優先，將所計算出的寬度優先的索引映射作爲映射對的值，與密鑰的節點的值。 map.put(node.value, tree_visitor.current_index)
詢問映射，傳遞所需的鍵（這是後序節點的索引）以獲取相應廣度優先節點的索引。

來源

2010-12-20 23:20:25 tpdi

將後序二叉樹遍歷索引轉換爲水平順序（寬度優先）索引

回答

相關問題