數組的二叉樹：插入數組的錯誤值

Question

我不知道我在做什麼錯。我有3個函數來將數據從兩個二叉樹存儲到數組中。我的問題如下：一切工作正常的ARR2，但不是ARR1。有誰知道如何解決這個問題？幫助將不勝感激！

編輯：第一個數組看起來像它也包含來自arr2和一些隨機數的值。

第一個函數創建數組並調用treeToArray。

void merge(Node* n1, Node* n2){ 
    int l1 = getTreeSize(n1); 
    cout << "array size " << l1 << endl; 
    int *arr1 = new int[l1]; 
    int i = 0; 
    treeToArray(n1, arr1, i); //This array is not filled how it's supposed to be. 

    int l2 = getTreeSize(n2); 
    cout << "array size " << l2 << endl; 
    int *arr2 = new int[l2]; //corrected this, thanks! 
    int j = 0; 
    treeToArray(n2, arr2, j); 

    for(int i = 0; i < l1; ++i) 
     cout << "array" << arr1[i] << " "; 

    merge(arr1, arr2, l1, l2); 

} 

treeToArray應該樹的數據存儲到所述陣列。

void treeToArray(Node* n, int values[], int index) { 
    if(n == NULL) 
      return; 

    if(n->left != NULL) 
      treeToArray(n->left, values, index); 

    cout << "speichere " << n->data << endl; 
    values[index] = n->data; 
    index++; 

    if(n->right != NULL) 
      treeToArray(n->right, values, index); 

} 

getTreeSize返回樹的大小。

int getTreeSize(Node* n) { 
     if(n == NULL) { 
      return 0; 
     } else { 
      return (getTreeSize(n->left) + getTreeSize(n->right) + 1); // 
     } 
} 

Answer 1

你treeToArray功能由值，這意味着有不同的呼叫之間沒有通信是一個整數指數。

我已經在第一次調用時用實際的索引值對代碼進行了註釋，但是如果您想遵循遞歸，則可以在調試器中單步執行。

void treeToArray(Node* n, int values[], int index) { 
    // start first call with index = 0 
    if(n == NULL) 
      return; 
    if(n->left != NULL) 
      treeToArray(n->left, values, index); 
    // we passed 0 to the left subtree call, and get nothing back 
    // so index is still 0 here 

    values[index] = n->data; 
    // we just overwrote the left subtree's first element with our data 
    index++; 

    if(n->right != NULL) 
      treeToArray(n->right, values, index); 
    // the right subtree now always starts from 1 ... 
} 

如果你改變它參照通過索引，呼叫可以合作：

void treeToArray(Node* n, int values[], int& index) { 
    // start first call with index = 0 
    if(n == NULL) 
      return; 
    if(n->left != NULL) 
      treeToArray(n->left, values, index); 
    // the left subtree call used a reference to the same 
    // index variable, so any modification is visible here too 

    values[index] = n->data; 
    // we write our node data after the left subtree 
    // (using the final value of index from the left subtree call) 
    index++; 
    // this affects the index in any parent call 

    if(n->right != NULL) 
      treeToArray(n->right, values, index); 
    // the right subtree also advances the same index value 
} 

請注意，您可以改爲回報新的索引，但是這是一個小的變化到您現有的代碼。

---

作爲參考，很容易單獨測試這個函數與一些小樹分離並檢查預期的輸出。這會在你引入第二棵樹和所有其他機器之前暴露出錯誤。