Python实现AVL树插入节点时出现NoneType无rightnode属性报错求解

问题根因 #

你的代码存在两个核心逻辑错误：

• 递归插入未接收返回值：insertnode函数递归向左右子树插入节点时，仅调用了insertnode(rootnode.leftnode,nodevalue)/insertnode(rootnode.rightnode,nodevalue)，没有将子树旋转后返回的新根节点赋值给当前节点的对应子节点，导致子树结构更新无法同步到上层，触发后续平衡判断异常。
• RL/RR失衡判断条件写反：右子树过重（balance < -1）时的两个旋转条件写反，导致本来属于RR型的失衡触发了RL型的处理逻辑，对无左子节点的节点调用rightrotation，最终抛出NoneType无rightnode属性的错误。

修复方案 #

修正insertnode函数逻辑 #

def insertnode(rootnode,nodevalue):
    # 原判断rootnode.data is None逻辑不合理，改为直接判断节点是否为空，统一插入逻辑
    if not rootnode:
        return AVL(nodevalue)
    elif nodevalue < rootnode.data:
        # 接收递归返回的子树新根，赋值给左子节点
        rootnode.leftnode = insertnode(rootnode.leftnode, nodevalue)
    else:
        # 接收递归返回的子树新根，赋值给右子节点
        rootnode.rightnode = insertnode(rootnode.rightnode, nodevalue)

    rootnode.height = 1 + max(getheight(rootnode.leftnode), getheight(rootnode.rightnode))
    balance = getbalance(rootnode)
    
    # LL型失衡 直接右旋
    if balance > 1 and nodevalue < rootnode.leftnode.data:
        return rightrotation(rootnode)
    # LR型失衡 先左旋左子树再右旋
    if balance > 1 and nodevalue > rootnode.leftnode.data:
        rootnode.leftnode = leftrotation(rootnode.leftnode)
        return rightrotation(rootnode)
    # RR型失衡 直接左旋（原条件写反，已修正）
    if balance < -1 and nodevalue > rootnode.rightnode.data:
        return leftrotation(rootnode)
    # RL型失衡 先右旋右子树再左旋（原条件写反，已修正）
    if balance < -1 and nodevalue < rootnode.rightnode.data:
        rootnode.rightnode = rightrotation(rootnode.rightnode)
        return leftrotation(rootnode)
    return rootnode

测试运行 #

修复后运行你的测试代码，层序遍历输出结果为：

10
5
15
20

完全符合你预期的旋转后树结构。

内容的提问来源于stack exchange，提问作者Super Ultra Noob