代码之家 › 专栏 › 技术社区 › M.Hamra

如何编写递归函数来返回BST中的最小值?

binary-search-tree recursion c

M.Hamra · 技术社区 · 7 年前

我正在尝试编写一个递归函数,它将返回二叉搜索树中的最小值。

int RecursiveFindMin(Tree t) {
  if (t==NULL)
    return -1;
  else {
    if (t!=NULL)
        RecursiveFindMin(t->left);
  }

  return t->val;   
}

我希望在BST中获得最小值

相反,大多数时候,我得到的是第二小的结果! 我不太擅长递归函数,我希望帮助

2 回复 | 直到 7 年前

dbush 7 年前

对函数进行递归调用时,会放弃返回值。所以递归实际上什么都不做。您所做的只是返回传入的第一个节点的值。

您也没有使用正确的退出条件。您希望在当前节点为NULL时不停止(因为您可以对它做什么?)但是当左边节点为空。然后,所需的值位于该节点中。

因此,更改条件以检查左侧节点,并返回递归调用的值:

int RecursiveFindMin(Tree t) {
  if (t->left==NULL)
    return t->val;   
  else {
    return RecursiveFindMin(t->left);
  }
}

abdullah 7 年前

您正在返回每个左节点值。最后返回根值。您应该找到最左边的节点,并将该值固定为最小值。

const int kInf = 100000000;
int RecursiveFindMin(Tree t) {
    if (t == NULL) return kInf;
    int v = RecursiveFindMin(t->left);
    return v == kInf? t->val : v;   
}

我用过 kInf 对于树中不存在的值。

推荐文章

mourinho · Python中按顺序遍历树返回列表

7 年前

Dongho Han · 用C语言中的二叉搜索树查找合计

7 年前

Richard Cooper · 使用递归的C++二叉搜索树

7 年前

Pranshu · 无法删除二进制搜索树中的根节点

7 年前

user2411290 · BST Delete函数不删除目标节点(Java)

7 年前