You need to enable JavaScript to run this app. 如何修复BST的InOrder返回None问题并实现PreOrder/PostOrder
优惠活动
大模型
产品
解决方案
定价
更多

如何修复BST的InOrder返回None问题并实现PreOrder/PostOrder

二叉搜索树遍历方法实现问题与修改方案

当前实现现状

  • 基于Python实现二叉搜索树(BST)功能,开发过程参考了经典树遍历教程,配套了对应树结构的参考示意图。
  • 已完成开发的BST方法包括:get、put、drawTree、createTree、find、size、depth、height,整体代码结构沿用类内嵌套递归辅助方法的风格。
  • 现存待解决问题:中序遍历逻辑实现错误,前序、后序遍历方法尚未编写;执行print(bst.InOrder())时返回结果为None。

现有问题定位

原InOrder方法存在三处核心逻辑错误:

  1. 边界判断逻辑无效:方法属于BST类实例,self是BST对象本身,self.root是BST持有的根节点属性,二者类型完全不同,self == self.root的判断永远不成立,遍历流程根本不会启动。
  2. 递归调用写法错误:没有绑定类方法作用域,也没有传入当前遍历的节点参数,直接全局调用InOrder()会触发运行时错误。
  3. 无返回值设计:原方法内部仅包含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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.29 11:24:06