c - BST 第 n 个最小 (C)

Question

此函数尝试查找 BST 中第 n 个最小的数。我知道这本质上只是一个计数器的有序遍历。如果是这样，那么为什么这段代码不起作用？

假设我的 BST 已正确实现(事实确实如此)，为什么它会打印出 9？它应该打印出 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
}

Answer 1

smallest_helper 代码中存在两个问题:您应该仅在访问节点时递减计数器，并且应该传播返回值。另外，当函数应该返回值时，请注意没有值的 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 没有负值，因此负值用于指示无效条件。