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

BST第n小（C）

回答

相关问题