Мне нужно написать рекурсию для бинарного дерева с минимальной кучей, чтобы проверить, является ли это дерево минимальной кучей. Один из тестовых случаев просто НЕТ.
Является ли None деревом с минимальной кучей и возвращает True или None равно False?
Причина, по которой я спрашиваю, заключается в том, что в какой-то момент я достигну листьев, а их узлы None, и если базовый случай True, то он вернет True.
Я считаю, что тип none будет абсолютно истинным, поскольку он не нарушает определение дерева минимальной кучи.
Да, None считается деревом средней кучи.
Вы должны иметь в виду Min Heap. Когда мы имеем дело с любой древовидной структурой, потомки узла чаще всего инициализируются как None. Одна из причин заключается в том, что мы можем легко избежать рекурсии как таковой:
def find_node(node, data):
if root is None:
return
if root.data == data:
print "Node found"
find_node(node.left, data)
find_node(node.right, data)
class Node(object):
def __init__(self, data):
self.left = None
self.right = None
self.data = data
В вашем случае вы хотите проверить, является ли дерево минимальной кучей, пройдя по нему. Вы бы сделали что-то подобное
def is_min_heap(root):
#.....check here and then do
return is_min_heap(root.left) and is_min_heap(root.right)
Но это зависит от того, как вы хотите справиться с этим. Любой узел без дочерних элементов является минимальной кучей или максимальной кучей, но это не имеет смысла. Если вы хотите позвонить
is_min_heap(None) тогда вы можете это сделать, но вам решать, хотите ли вы сказать, что это Истина или нет.
Noneдля представления пустого дерева? - person chepner schedule 16.05.2015