如何实现二叉搜索树（BST）搜索算法伪代码？递归return存疑

你的写法完全正确，那些说递归调用左/右子节点时不需要return的说法是错误的。

递归搜索二叉搜索树的核心逻辑是要把最终的搜索结果（无论是匹配成功的内部节点，还是搜索失败的外部节点）逐层传递回初始调用者。如果去掉递归调用前的return，当前函数执行完递归调用后没有任何返回值，上层调用栈就无法获取到下层的搜索结果，最终整个搜索函数调用会返回空值，完全不符合预期。

下面是调整为中文表述的伪代码（保留原核心逻辑）：

function 搜索二叉树(k, v):
   if v是外部节点():
      return v
   if k == v的键():
      return v
   # 搜索左子树
   else if k < v的键():
      return 搜索二叉树(k, v.left)
   # 搜索右子树
   else: # k > v的键()
      return 搜索二叉树(k, v.right)

关键逻辑拆解 #

• 基准情况1：当当前节点是外部节点时，说明搜索失败，直接返回该节点作为失败标记
• 基准情况2：当当前节点的键与目标k匹配时，搜索成功，返回该节点
• 递归分支：
  • 当k小于当前节点键时，必须返回左子树的搜索结果——因为左子树的搜索结果才是我们需要的最终结果，不写return的话当前函数没有输出，上层调用拿不到值
  • 当k大于当前节点键时，同理必须返回右子树的搜索结果

内容的提问来源于stack exchange，提问作者IdeadlySkies