BST第n小（C）

該函數試圖找到BST中第n個最小的數。我明白它本質上只是一個爲了穿過櫃檯。如果是這樣的話，爲什麼這個代碼不工作？BST第n小（C）

假設我的BST正確實施（它是），爲什麼它打印出9？它應該打印在smallest_helper碼出6

int bst_ith_smallest(BST_PTR t, int i) 
{ 
    if(i > count) 
     fprintf(stderr, "Input is greater than BST size"); 

    return (smallest_helper(t->root, i)); 
} 


int smallest_helper(NODE *r, int i) 
{ 
    if(r==NULL) 
     return; 

    smallest_helper(r->left, --i); 

    if(i == 0) 
     return r->val; 

    smallest_helper(r->right, --i); 
} 


My test function: 

int main() 
{ 
    int i; 

    int a[] = {8, 2, 7, 9, 11, 3, 2, 6}; 


    BST_PTR t = bst_create(); 

    for(i=0; i<8; i++) 
    bst_insert(t, a[i]); 

    printf("%d\n", bst_ith_smallest(t, 3)); <------ HERE the function is called 
    //other tests here 
}

來源

2013-12-09 juice

正如@RUP所說。你可能需要'--i'而不是'我 - '。 – jnovacho

我很抱歉是的，我在我的代碼中這樣做了，忘了更新它。這不是問題。 – juice

對不起，發生了信心危機並刪除了我的評論。問題在於，當你遞減和減少'i'時，當你遞迴時，你會失去這個遞減 - 'i'只會向你顯示深度。你可以通過引用傳遞'i'，或者當你結束一個遞歸時傳遞'i'的新版本。 – Rup

兩個問題：你應該遞減時訪問節點，只有當你的櫃檯，你應該傳播的返回值。另外，當函數返回一個時，請注意return沒有值。

試試這個：

int smallest_helper(NODE *r, int i) 
{ 
    if (r == NULL) { 
     return -1; 
    } 
    int val; 
    val = smallest_helper(r->left, i); 
    if (val >= 0) { 
     return val; 
    } 
    if (--i == 0) { 
     return r->val; 
    } 
    val = smallest_helper(r->right, i); 
    if (val >= 0) { 
     return val; 
    } 
    return -1; 
}

那假設你的BST沒有負值，因此使用負值指示無效狀態。

來源

2013-12-09 17:27:46 ericbn

回答

相關問題