首页 文章

确定以节点为根的二叉树是否为最大堆[重复]

提问于
浏览 次
2

这个问题在这里已有答案：

我试图确定一个以节点为根的二叉树是否是一个最大堆，为此我按照堆属性的规则获取了一个max-heap，它指出：

Max-heap:

所有节点都大于或等于其子节点

My Idea of the implementation:

  • 如果在作为is_max_heap参数给出的节点处没有右或左节点而不是返回True

  • 否则，如果节点的值大于左右节点的值，则在右侧和左侧节点上再次调用该函数 .

  • 否则返回False .

My code:

class BTNode:
    '''A generic binary tree node.'''

    def __init__(self, v):
        '''(BTNode, int) -> NoneType

        Initialize a new BTNode with value v.

        '''
        self.value = v
        self.left = None
        self.right = None


def is_max_heap(node):
    '''(BTNode) -> bool

    Return True iff the binary tree rooted at node is a max-heap
    Precondition: the tree is complete.

    '''
    if node.left and node.right is None:
        return True
    else:
        if node.value > node.left.value and node.value > node.right.value:
            return is_max_heap(node.left) and is_max_heap(node.right)
        else:
            return False


if __name__ == '__main__':
    l1 = BTNode(7)
    l2 = BTNode(6)
    l3 = BTNode(8)
    l1.left = l2
    l1.right = l3
    print(is_max_heap(l1))

因此，在 if __name__ == '__main__': 下，我创建了三个节点，其值为7,6和8.第一个节点有一个左右节点 . 所以树看起来像这样：

7
 /   \
6     8

这不满足max-heap属性，因此它应该返回False . 然而，运行我的代码返回True，我无法弄清楚我可能出错的地方 . 如果有人可以帮助我，那将非常感激 .

python heap

1 回答

  • 0

    当只有一个孩子时，你没有想到这种情况 . 确保你的程序在这两棵树上正常工作 - 一个是最小堆，另一个是最大堆：

    2     1
 /     /
1     2

    还要学会正确设置括号;你犯了经典错误 True and 42 == 42 ;这是 True .

    考虑以同样的方式处理两个可能不存在的孩子 .

    if left is not None:
  if not <check max heap property for left subtree>: return False
if right is not None:
  if not <check max heap property for right subtree>: return False
return True

    丢失的函数应与当前节点进行比较，并在必要时递归到子树中 .

    回复于

相关问题