Python实现二叉搜索树中序遍历出现NameError错误求助

嘿，我一眼就瞅见你代码里的问题啦！出现NameError主要是因为递归调用和节点引用的几个小错误，咱们来逐个修正：

问题根源 #

1. 递归调用未使用self：你在in_order_traversal方法里直接写in_order_traversal(self.root.left)，Python会把它当成全局函数，而不是类的方法，自然找不到这个函数，就抛出NameError了。
2. 节点引用错误：你代码里写的print(root.data)，但root根本没在这个方法里定义啊！这里应该要打印当前遍历到的节点的数据才对。
3. 递归逻辑错位：中序遍历需要针对单个节点递归处理左右子树，但你现在的方法没有接收节点参数，直接操作self.root的子节点，这样递归根本没法逐层遍历下去。

修正后的代码方案一（用内部辅助函数） #

这个方案把递归逻辑封装在内部函数里，结构更清晰：

class BSTNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

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

    def insert(self, data):
        new_node = BSTNode(data)
        if self.root == None:
            self.root = new_node
        else:
            ptr = self.root
            prev = None
            while ptr != None:
                prev = ptr
                if data <= ptr.data:
                    ptr = ptr.left
                else:
                    ptr = ptr.right
            if data <= prev.data:
                prev.left = new_node
            else:
                prev.right = new_node

    def in_order_traversal(self):
        # 内部辅助函数，负责递归遍历单个节点
        def traverse(node):
            if node:
                traverse(node.left)  # 先遍历左子树
                print(node.data)     # 打印当前节点
                traverse(node.right) # 再遍历右子树
        # 从根节点启动遍历
        traverse(self.root)

bst = BST()
bst.insert(50)
bst.insert(25)
bst.insert(100)
bst.insert(80)
bst.insert(30)
bst.in_order_traversal()

修正后的代码方案二（直接给方法加节点参数） #

如果你不想用内部函数，也可以给in_order_traversal加一个可选的节点参数：

class BSTNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

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

    def insert(self, data):
        new_node = BSTNode(data)
        if self.root == None:
            self.root = new_node
        else:
            ptr = self.root
            prev = None
            while ptr != None:
                prev = ptr
                if data <= ptr.data:
                    ptr = ptr.left
                else:
                    ptr = ptr.right
            if data <= prev.data:
                prev.left = new_node
            else:
                prev.right = new_node

    def in_order_traversal(self, node=None):
        # 如果没传节点，默认从根节点开始
        if node is None:
            node = self.root
        if node:
            self.in_order_traversal(node.left)  # 递归左子树
            print(node.data)                    # 打印当前节点
            self.in_order_traversal(node.right) # 递归右子树

bst = BST()
bst.insert(50)
bst.insert(25)
bst.insert(100)
bst.insert(80)
bst.insert(30)
bst.in_order_traversal()

这两种方案都能解决你的NameError问题，而且能正确输出中序遍历的结果：25 30 50 80 100。

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