如何在单个函数中递归计算 AVL-Tree 节点的平衡？ (Python)

Question

这里是第一个问题，所以如果我遗漏了一些重要的事情，请告诉我。我有一个平衡的 AVL 树，我需要创建一个函数来计算单个给定节点的平衡。这需要在单个函数中发生，并且 递归地 。（顺便说一句，这是在Python中）

我还包含了节点的实例化方法class，以便您可以看到节点的属性。到目前为止，我已经想出了这个，虽然它有效，但它仍然不符合标准：

class Node: 
    def __init__(self, value, root): 
        self.value = value # Node value
        self.left = None # Left child
        self.right = None # Right child
        self.root = root # Stores the original root of the tree

    def getBalance(self, node):
        return self.getTreeHeight(node.right)-self.getTreeHeight(node.left)
        
    def getTreeHeight(self, rootnode):
        if rootnode == None:
            return -1
        else: 
            return max(self.getTreeHeight(rootnode.left), self.getTreeHeight(rootnode.right)) + 1

如有任何提示，我们将不胜感激。我所需要的只是朝着正确的方向轻推，因为老实说，我有点难过。

提前致谢！

Answer 1

首先是对您的实施的一些一般性评论：

为每个节点提供一个指向树根的指针是不寻常的。如果您决定在树的顶部添加一个新节点，使当前根成为新节点的子节点，这是非常不切实际的。然后你将不得不访问每个节点来更新对根的引用。
这两个方法都以一个节点为参数，可惜，因为self已经是一个节点，所以那个节点可能是手术的对象。这需要对 getTreeHeight 进行微小的更改，因为您当前允许参数为 None。但最后最好让这些方法在没有参数的情况下工作（self除外）。

现在进入正题。不可能写出只调用自身而不传递或return任何额外信息的getBalance方法。这是因为平衡的概念不是归纳的：如果您知道给定节点的子节点的平衡，那么此信息对于确定节点本身的平衡是没有用的。所以你需要以某种方式传递一些额外的信息。

实现此目的的一种方法是向 getBalance 添加一个可选参数，它将指示该函数是否被递归调用。如果递归，它可以 return 高度，如果不是，则平衡。这样你实际上合并了你已经写的两个函数：

def getBalance(self, recurring=False):
    left = self.left.getBalance(True) if self.left else 0
    right = self.right.getBalance(True) if self.right else 0
    return max(left, right) + 1 if recurring else right - left

呼叫为：

node = root.left.right.right  # get a reference to some node in your tree
balance = node.getBalance()  # get the balance of that node (no argument!)

如何在单个函数中递归计算 AVL-Tree 节点的平衡？ (Python)

How to calculate balance of AVL-Tree node recursively and in a single function? (Python)

python

tree

binary-tree

avl-tree