如何解决Python二叉树删除代码中的NoneType错误与AttributeError问题

首先，你遇到的AttributeError: 'NoneType' object has no attribute 'right'核心原因非常明确：你没有将insert函数的返回值重新赋值给root变量。

Python中函数参数采用「对象引用传递」，当你最初调用insert(root, 50)时，root是None，函数内部确实创建了新的Node(50)并返回，但这个返回值没有被赋值回root，导致root始终保持None状态。后续所有insert调用都是基于None执行，根本无法构建出有效的二叉树，最终访问root.right时自然会触发NoneType的属性错误。

修复步骤 #

1. 修正root的初始化与赋值逻辑 #

把你的初始化代码从：

root = None
insert(root, 50)
insert(root, 99)
# ... 其他insert调用

改成：

root = None
root = insert(root, 50)
root = insert(root, 99)
root = insert(root, 78)
# ... 后续所有insert调用都要把返回值赋值给root

或者更简洁的批量写法：

root = None
for key in [50, 99, 78, 57, 80, 4, 64, 35, 58, 33]:
    root = insert(root, key)

2. 修复delete_node的潜在未定义变量问题 #

你的delete_node函数里还有一个隐藏隐患：在寻找后继节点s的循环中，sparent仅在循环内部被赋值。如果s一开始就是r.right且没有左子节点（循环完全不执行），sparent会处于未定义状态，导致后续代码报错。可以提前初始化sparent为r来规避这个问题：

def delete_node(r):
    if r.left is None and r.right is None:
        return None
    elif r.left is not None and r.right is None:
        return r.left
    elif r.left is None and r.right is not None:
        return r.right
    else:
        s = r.right
        sparent = r  # 初始化sparent为r，避免未定义
        while s.left is not None:
            sparent = s
            s = s.left
        r.key = s.key
        if s == r.right:
            r.right = s.right
        else:
            sparent.left = s.right
        return r

验证修复效果 #

修改完成后，你原本的测试代码就能正常运行：

print(root.right.left.key)  # 输出78
start = timer()
delete(root.right.left)
print(timer() - start)
print(root.right.left.key)  # 输出80（删除78后，右子树的最小节点补位）

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