在python中，在AVL树中向左旋转子树

Question

算是计算机科学的新手

我掌握了Python中二叉树的基本知识，我正在研究AVL树中的一些应用程序：

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) + ')'  # Space before '('
    else:
        string += ' ('  # Space before '('
        string += ')'
    if root.right:
        string += ' (' + show_aux(root.right) + ')'  # Space before '('
    else:
        string += ' ('  # Space before '('
        string += ')'
    return string


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


def rotate_left(root):
    rotated_root = root.right
    try:
        temp = rotated_root.left
    except:
        show(root)

    rotated_root.left = root
    root.right = temp
    return rotated_root


root = TreeBinary('a')
root.left = TreeBinary('b')
root.right = TreeBinary('c')
show(root)
print()
root.left = rotate_left(root.left)
show(root)

我试图解决的挑战之一是在一个以根为参数的函数中旋转树的左侧，但我得到以下错误：

root.left = rotate_left(root.left)
  File "rotated_left_binary_tree.py", line 36, in rotate_left
    rotated_root.left = root
AttributeError: 'NoneType' object has no attribute 'left'

我试图解决，但它只打印根和右根

Answer 1

您正在b旋转子树，但是您的函数期望给定节点有一个正确的子节点，显然不是这样：在b没有任何东西可以旋转

如果您的主代码要求在节点a处进行轮换，则更有意义：

root = rotate_left(root)

另一方面，最好能稍微保护一下旋转功能。当它没有合适的子级时，让它不加更改地返回根：

def rotate_left(root):
    rotated_root = root.right
    if not rotated_root:
        return root  # cannot rotate here
    try:
        temp = rotated_root.left
    except:
        show(root)

    rotated_root.left = root
    root.right = temp
    return rotated_root

现在，您的原始主代码不会触发异常，但树也不会更改，这确实是在叶节点（b）上调用旋转函数时的正确行为