如何修复BST的InOrder返回None问题并实现PreOrder/PostOrder
二叉搜索树遍历方法实现问题与修改方案
当前实现现状
- 基于Python实现二叉搜索树(BST)功能,开发过程参考了经典树遍历教程,配套了对应树结构的参考示意图。
- 已完成开发的BST方法包括:
get、put、drawTree、createTree、find、size、depth、height,整体代码结构沿用类内嵌套递归辅助方法的风格。 - 现存待解决问题:中序遍历逻辑实现错误,前序、后序遍历方法尚未编写;执行
print(bst.InOrder())时返回结果为None。
现有问题定位
原InOrder方法存在三处核心逻辑错误:
- 边界判断逻辑无效:方法属于BST类实例,
self是BST对象本身,self.root是BST持有的根节点属性,二者类型完全不同,self == self.root的判断永远不成立,遍历流程根本不会启动。 - 递归调用写法错误:没有绑定类方法作用域,也没有传入当前遍历的节点参数,直接全局调用
InOrder()会触发运行时错误。 - 无返回值设计:原方法内部仅包含
print语句,没有收集遍历结果的逻辑,调用完成后自然返回None,无法被print输出有效内容。
遍历方法修改方案
和现有代码的递归设计风格保持一致,采用“公开入口方法+私有递归辅助方法”的两层结构,遍历过程将节点key按顺序收集到列表中,最终返回结果列表,保证调用时可以直接拿到遍历结果。
核心实现逻辑
- 中序遍历(InOrder):遍历顺序为「左子树 → 当前节点 → 右子树」
- 前序遍历(PreOrder):遍历顺序为「当前节点 → 左子树 → 右子树」
- 后序遍历(PostOrder):遍历顺序为「左子树 → 右子树 → 当前节点」
可直接替换的代码
将原类中逻辑错误的InOrder方法完全删除,替换为以下实现即可:
# 中序遍历 def InOrder(self): result = [] self._in_order_helper(self.root, result) return result def _in_order_helper(self, node, result): if not node: return self._in_order_helper(node.left, result) result.append(node.key) self._in_order_helper(node.right, result) # 前序遍历 def PreOrder(self): result = [] self._pre_order_helper(self.root, result) return result def _pre_order_helper(self, node, result): if not node: return result.append(node.key) self._pre_order_helper(node.left, result) self._pre_order_helper(node.right, result) # 后序遍历 def PostOrder(self): result = [] self._post_order_helper(self.root, result) return result def _post_order_helper(self, node, result): if not node: return self._post_order_helper(node.left, result) self._post_order_helper(node.right, result) result.append(node.key)
效果验证
替换代码后执行如下测试代码:
bst = BST() bst.createTree() print(bst.InOrder()) print(bst.PreOrder()) print(bst.PostOrder())
将分别输出按遍历规则排序的key列表,不会再返回None。
内容的提问来源于stack exchange,提问作者Fumin
相关产品推荐
相关产品推荐

