Python中AVL树左子树左旋触发NoneType属性错误问题

核心问题定位 #

• 你遇到的报错本质是空指针访问：调用rotate_left(root.left)时传入的是值为b的叶子节点，这个节点本身没有右子节点，代码执行rotated_root = root.right时直接拿到了None，后续给None对象绑定left属性自然会抛错。
• 原代码的异常捕获逻辑完全起不到防护作用：try块只包裹了获取rotated_root.left的两行，当rotated_root本身就是空值时，代码根本不会进入捕获逻辑，直接走到下一行赋值操作触发崩溃。
• 你之前自行修复后出现的输出不全问题，是因为边界处理没有对齐左旋的操作规则：对于没有右子节点的待旋转节点，左旋操作本身就没有可执行的基础，强行调整指针就会弄丢原本的节点关联，导致输出缺失。

左旋的操作前提 #

左旋不是对任意节点都能执行的操作，有明确的适用条件：对某个节点做左旋，必须保证该节点有非空的右子节点——因为左旋的本质就是把右子节点抬升为当前子树的新根，没有右子节点时根本不存在旋转的操作基础。
标准的左旋操作流程是固定的：

1. 取出待旋转节点的右子节点，作为旋转后新的子树根节点
2. 把新根原来的左子树，接到原待旋转节点的右指针上
3. 把原待旋转节点，设为新根的左子节点
4. 把新子树根节点返回给调用方，替换父节点原来指向旧子树的指针

修复后的可运行代码 #

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


def show_aux(root):
    if not root:
        return ''
    string = str(root.data)
    if root.left or root.right:
        string += ' (' + show_aux(root.left) + ')'
    else:
        string += ' ()'
    if root.right:
        string += ' (' + show_aux(root.right) + ')'
    else:
        string += ' ()'
    return string


def show(root):
    print('(' + show_aux(root) + ')')


def rotate_left(root):
    # 边界判断：无右子节点时无法执行左旋，直接返回原节点
    if root is None or root.right is None:
        return root
    rotated_root = root.right
    temp = rotated_root.left
    # 执行指针调整
    rotated_root.left = root
    root.right = temp
    return rotated_root


# 测试用例：给待旋转的b节点添加右子节点，满足左旋的操作前提
root = TreeBinary('a')
root.left = TreeBinary('b')
root.left.right = TreeBinary('d')
root.right = TreeBinary('c')
show(root)
print()
root.left = rotate_left(root.left)
show(root)

注意：如果保持原来b是纯叶子节点的测试用例，因为b没有右子节点，修复后的函数会直接返回原b节点，不会做任何修改——这是符合左旋规则的合理结果，不会出现原有节点丢失的问题。按照示例给b加上右子节点后，旋转完成的树结构会变成a的左子节点是d，d的左子节点是b，完全匹配左旋的预期效果。

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