python - 如何通过一个函数调用更新二叉树中所有节点的高度？

Question

我有一个由此类节点组成的二叉树：

class Node:
    def __init__(self,key,parent=None,right=None,left=None):
        self.key = key
        self.left = left
        self.right = right
        self.parent = parent
        self.height = 0

树构造的一个示例可能是：

a = Node(1)
a.left = Node(2,parent=a)
a.right = Node(5,parent=a)
a.right.right = Node(3,parent=a.right)

我想编写一个函数来更新这棵树中所有节点的高度。我找到了获取一个节点高度的方法。但是，我想一次更新所有高度。

我怎么能这样做？

标签： pythonbinary-tree

Answer 1

您可以添加此递归方法：

def syncheight(self):
    self.height = max(
        -1 if self.left is None else self.left.syncheight(), 
        -1 if self.right is None else self.right.syncheight()
    ) + 1
    return self.height

您可以在根目录上调用它，如下所示：

a.syncheight()

请注意，我将调用该类Node而不是node，并且您的参数名称与构造函数主体中使用的名称不同（left, leftChild）

建议

我不会将 传递parent给构造函数，因为这应该遵循传递为left和的信息right。后者应该parent更新他们的属性以引用当前创建的节点。

height然后，您还可以通过更新新创建节点的祖先的高度来保持更新：

class Node:
    def __init__(self, key, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right
        self.parent = None
        if left:
            left.parent = self
        if right:
            right.parent = self
        self.height = -1
        self.bubbleheight()
    
    def bubbleheight(self):
        height = max(
            -1 if self.left is None else self.left.height,
            -1 if self.right is None else self.right.height
        ) + 1
        if height != self.height:
            self.height = height
            if self.parent is not None:
                self.parent.bubbleheight()

tree = Node(1,
            Node(2),
            Node(5,
                Node(3)
            )
        )

print(tree.height)  # 2