二叉搜索树插入节点报错：Node对象无insert属性

触发AttributeError: 'Node' object has no attribute 'insert'的直接原因是：insert方法仅定义在BST类中，Node类只初始化了data、left、right三个属性，没有实现insert方法。当执行self.root.right.insert(val)时，self.root.right是Node类实例，调用不存在的方法自然会抛出属性错误。
除此之外现有插入逻辑还有缺陷：仅判断了根节点的直接左右子节点，没有向下遍历树结构的逻辑，即使给Node补上insert方法，也无法正确插入三层及更深位置的节点。

两种常规实现方式二选一即可：

方案1：遍历逻辑放在BST类中，用临时指针找插入位置 #

不需要给Node类新增方法，从根节点开始遍历找到合适的叶子节点位置插入新节点即可，逻辑更直观，是日常开发更常用的写法：

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


class BST:
    def __init__(self):
        self.root = None
        
    def insert(self, val):
        new_node = Node(val)
        if self.root is None:
            self.root = new_node
            return
        # 用临时指针遍历，*不要直接修改self.root*，否则会丢失原有树结构
        cur = self.root
        while True:
            if cur.data > val:
                if cur.left is None:
                    cur.left = new_node
                    break
                cur = cur.left
            elif cur.data < val:
                if cur.right is None:
                    cur.right = new_node
                    break
                cur = cur.right
            # 重复值默认直接跳过，可根据需求调整规则，比如重复值放右子树
            else:
                break

bt1 = BST()
bt1.insert(1)
bt1.insert(2)
bt1.insert(0)
bt1.insert(10)

方案2：给Node类新增insert方法，实现递归插入 #

如果要保留node.insert(val)的调用形式，就把递归插入的逻辑下沉到Node类中，BST类的insert方法仅处理根节点为空的边界情况：

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
    
    def insert(self, val):
        if self.data > val:
            if self.left is None:
                self.left = Node(val)
            else:
                self.left.insert(val)
        elif self.data < val:
            if self.right is None:
                self.right = Node(val)
            else:
                self.right.insert(val)


class BST:
    def __init__(self):
        self.root = None
        
    def insert(self, val):
        if self.root is None:
            self.root = Node(val)
        else:
            self.root.insert(val)

bt1 = BST()
bt1.insert(1)
bt1.insert(2)
bt1.insert(0)
bt1.insert(10)

• 两种实现都符合二叉搜索树的插入规则，递归写法代码更简洁，非递归写法（方案1）性能更好，不会有递归深度溢出的问题
• 二叉搜索树默认不存储重复值，上述示例代码遇到重复值直接跳过，如果业务需要存储重复值，可以自定义规则，比如统一将重复值插入到左子树或右子树

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