二叉搜索树插入操作出现AttributeError错误的问题排查

核心错误原因 #

第一次插入数据时，BST类的root初始化为None，调用treeSearch时将None传入Node.isExternal方法，而None对象没有left属性，直接触发AttributeError。除此之外，代码还有几处逻辑和参数问题需要修正：

具体问题点及修复 #

1. BST初始化缺少根外部节点
   原代码中BST.__init__将root设为None，但根据你的外部/内部节点定义，树的初始状态应该是一个空的外部节点（而非None）。
   修复：

   class BST:
       def __init__(self):
           self.root = Node()  # 创建一个空的外部节点作为根
   

2. Node类__init__方法参数缺失默认值
   Node的构造函数第一个参数key没有默认值，导致expandExternal中创建子节点时Node()会触发参数错误。
   修复：

   def __init__(self, key=None, left=None, right=None, parent=None, elem=None):
       self.left = left
       self.right = right
       self.parent = parent
       self.key = key
       self.elem = elem
   

3. treeSearch函数的边界处理
   虽然修复BST初始化后不会再传入None，但可以给treeSearch增加一层判断，避免意外传入None的情况：

   def treeSearch(self, node, key):
       if node is None or Node.isExternal(node):
           return node
       if key == node.key:
           return node
       elif key < node.key:
           return self.treeSearch(node.left, key)
       else:
           return self.treeSearch(node.right, key)
   

完整修复后的代码 #

class Node:
    # elem is element of Node.
    def __init__(self, key=None, left=None, right=None, parent=None, elem=None):
        self.left = left
        self.right = right
        self.parent = parent
        self.key = key
        self.elem = elem

    # External Node Check 
    def isExternal(node):
        if (node.left is None) and (node.right is None):
            return True
        else:
            return False
    
    # Internal Node Check
    def isInternal(node):
        if (node.left is not None) and (node.right is not None):
            return True
        else:
            return False
    
    def expandExternal(z):
        leftnode = Node()
        rightnode = Node()
        leftnode.parent = z
        rightnode.parent = z
        z.left = leftnode
        z.right = rightnode
        return
    
class BST:
    def __init__(self):
        self.root = Node()

    def insertItem(self, key, elem):
        node = self.treeSearch(self.root, key)
        if Node.isInternal(node):
            return
        node.elem = elem
        node.key = key
        Node.expandExternal(node)
        return
    
    def treeSearch(self, node, key):
        if node is None or Node.isExternal(node):
            return node
        if key == node.key:
            return node
        elif key < node.key:
            return self.treeSearch(node.left, key)
        else:
            return self.treeSearch(node.right, key)

def main():
    n=int(input("ENTER THE NUMBER OF STUDENTS: \n"))

    b=BST()

    for i in range (n):
        print("\nENTER THE DETAILS OF STUDENT ",i+1,":")
        key=int(input("Enter the roll num:        "))
        name=input("Enter name:        ")
        b.insertItem(key, name)

if __name__ == '__main__':
    main()

补充说明 #

• 你的外部节点定义是左右子节点都为None，内部节点是左右都不为None（通过expandExternal将外部节点转为内部节点），这个逻辑是自洽的，修复上述问题后即可正常插入学号和姓名数据。
• 如果需要支持重复学号的处理，可以在insertItem中当Node.isInternal(node)时做相应的覆盖或提示逻辑。

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