Python实现Binary Search Tree时inorder中序遍历触发AttributeError报错

核心问题：中序遍历方法缺失递归终止条件 #

你编写的inorder方法没有对传入的current参数做非空判断，就直接尝试访问current.left属性触发递归：

• 当递归走到叶子节点的左/右子节点时，该位置的值为None
• 此时程序依然会执行self.inorder(None)调用，进入函数后尝试访问None.left，就会抛出你遇到的AttributeError

仅需要在inorder方法最开头新增递归终止逻辑即可，修复后的完整代码如下：

class node:
    def __init__(self,value):
        self.value = value
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def add(self,current,value):
        if self.root == None:
            self.root = node(value)
        else:
            if value < current.value:
                if current.left == None:
                    current.left = node(value)
                else:
                    self.add(current.left,value)
            if value > current.value:
                if current.right == None:
                    current.right = node(value)
                else:
                    self.add(current.right,value)

    def visit(self,node):
        print(node.value)

    def inorder(self,current):
        # 新增终止条件：当前节点为空时直接返回，不再向下递归
        if current is None:
            return
        self.inorder(current.left)
        self.visit(current)
        self.inorder(current.right)

Tree = BST()
root = node(2)
Tree.root = root
Tree.add(Tree.root,7)

Tree.inorder(Tree.root)

运行修复后的代码，会按中序遍历顺序输出：

2
7

你当前实现的add方法存在逻辑冗余：手动给BST设置根节点后，方法开头的if self.root == None判断永远不会命中，后续新增节点的逻辑是正常的。如果要优化可以调整add方法的参数设计，外部调用时不需要主动传入根节点，由方法内部判断根节点状态即可。

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