Python递归实现二叉搜索树查找报键未找到错误,排查插入逻辑问题
递归实现二叉搜索树插入问题核心排查
你的测试场景下出现“插入无异常但查找不到对应键”的问题,绝大多数是两类递归实现的经典逻辑错误:
高频错误点
- 第一类:递归插入时未将新节点挂载到父节点的子引用上
这是写递归插入最常踩的坑:当递归走到空的插入位置、成功生成新的TreeNode节点后,没有把递归函数返回的新节点,赋值到父节点对应的left/right属性上。
此时插入流程全程无报错,但新节点完全没有被接入整棵树的结构里,根节点的右子指针始终为None,后续查找13时会直接走到空节点,触发InvalidKeyError。
典型错误代码片段:def _insertRec(self, current_node, key, value): if not current_node: # 正确生成新节点,但上层没有接返回值 return TreeNode(key, value) if key < current_node.key: # 只调用递归,不将返回结果赋值给left self._insertRec(current_node.left, key, value) elif key > current_node.key: # 只调用递归,不将返回结果赋值给right self._insertRec(current_node.right, key, value) return current_node - 第二类:插入与查找的分支方向逻辑错位
即插入时键值大小判断的左右分支,和查找时的判断规则不匹配:比如插入时把大于当前节点的键赋值给左子树,查找时却按照“大于当前键走右分支”的规则遍历,自然会走到空节点抛出不存在的异常。
快速定位步骤
- 在每次插入完成后,直接打印根节点的左右子节点键值,核对结构是否符合预期:
- 插入(9,"nine")后:根节点key=9,left=None,right=None
- 插入(5,"five")后:根节点left=5,right=None
- 插入(13,"thirteen")后:根节点right应当为13,若此处显示right为None,即可确认是第一类未挂载节点的问题
- 逐行核对
_insertRec和_findRec的大小判断逻辑,保证两个方法的左右分支规则完全一致。
正确实现参考
class TreeNode: def __init__(self, key, value): self.key = key self.value = value self.left = None self.right = None class BinarySearchTree: def __init__(self): self.root = None def _insertRec(self, current, key, value): if not current: return TreeNode(key, value) if key < current.key: current.left = self._insertRec(current.left, key, value) elif key > current.key: current.right = self._insertRec(current.right, key, value) else: current.value = value return current def insert(self, key, value): self.root = self._insertRec(self.root, key, value) def _findRec(self, current, key): if not current: raise InvalidKeyError(f"Key {key} not found") if key == current.key: return current.value elif key < current.key: return self._findRec(current.left, key) else: return self._findRec(current.right, key) def find(self, key): return self._findRec(self.root, key)
内容的提问来源于stack exchange,提问作者Oliver Southon
相关产品推荐
相关产品推荐

