在C++中構建分段樹

我正在嘗試在C++中構建分段樹。以下爲相同的遞歸函數：在C++中構建分段樹

int buildTree(int node,int start,int end,int tree[]) 
{ 
     // printf("Node is: %d\n",node); 
    printf("start: %d\tend:%d\tnode:%d\t\n",start,end,node); 
    if (start == end) 
    { 
     // printf("start: %d,node: %d,array[start] : %d\n",start,node,array[start]); 
     tree[node] = array[start]; 
     return array[start]; 

    } 
    else 
    { 
     int mid = (start + end)/2; 

     buildTree(2 * node ,mid + 1,end,tree); 
     buildTree(2 * node + 1,start,mid,tree); 

     tree[node] = tree[ 2 * node ] + tree[ 2 * node + 1 ]; 
     return tree[node]; 
    } 
}

該陣列是全局定義：

int array[] = {1,2,3,4,5};

以下調用後的樹：

int main(int argc, char const *argv[]) 
{ 
    int tree[100]; 
    buildTree(0,0,4,tree); 
    for (int i = 0; i < 9; ++i) 
    { 
     printf("%d : %d\n",i, tree[i]); 
    } 
    return 0; 
}

給出了輸出：

start: 0 end:4 node:0 
start: 3 end:4 node:0 
start: 4 end:4 node:0 
start: 3 end:3 node:1 
start: 0 end:2 node:1 
start: 2 end:2 node:2 
start: 0 end:1 node:3 
start: 1 end:1 node:6 
start: 0 end:0 node:7 
0 : 15 
1 : 6 
2 : 3 
3 : 3 
4 : 474810352 
5 : 32766 
6 : 2 
7 : 1 
8 : 0

因此，th e節點4和5從不處理。我在哪裏做錯了？我覺得我在遞歸方面很難。

來源

2017-06-18 learner

解決這些問題的正確工具是你的調試器。在*堆棧溢出問題之前，您應該逐行執行您的代碼。如需更多幫助，請閱讀[如何調試小程序（由Eric Lippert撰寫）]（https://ericlippert.com/2014/03/05/how-to-debug-small-programs/）。至少，你應該[編輯]你的問題，以包含一個[Minimal，Complete，and Verifiable]（http://stackoverflow.com/help/mcve）例子來重現你的問題，以及你在調試器中所做的觀察。 –

您正在一遍一遍地構建'node [0]'b/c'2 * 0 == 0'。 –

我該如何避免這種情況？ – learner

我使用某種方式構建了一個段樹，使用相同的實現。

你應該調用該函數buildTree初始節點= 1

buildTree(1,0,4,tree);

這應該修正這個錯誤。

而且大部分的段樹實現碼使用的節點（2 *節點）的範圍（開始 - >中期）和所述節點（2 *節點+ 1）的範圍（中間+ 1 - >結束）。

我認爲這是一個約定的問題。但是堅持使用約定會讓你更容易調試你的代碼，並且更容易讓其他程序員理解它。

所以你可以重寫遞歸調用爲：

buildTree(2 * node ,start,mid,tree); 
buildTree(2 * node + 1,mid+1,end,tree);

相反的：

buildTree(2 * node ,mid + 1,end,tree); 
buildTree(2 * node + 1,start,mid,tree);

來源

2017-06-18 09:29:25

在C++中構建分段樹

回答

相關問題