Определите, является ли двоичное дерево максимальной кучей

Question

Я пишу функцию, чтобы определить, является ли данное двоичное дерево максимальной кучей. Если бинарное дерево имеет только один узел (корень), будет ли оно считаться допустимой максимальной кучей?

Answer 1

Чтобы считаться допустимой максимальной кучей, двоичное дерево должно удовлетворять двум свойствам:

1. Свойство Shape. Дерево должно быть полным двоичным деревом . То есть каждый уровень, кроме последнего, должен быть полным. Если последний не заполнен, он заполняется слева.
2. Свойство кучи. Каждый дочерний узел должен быть меньше или равен своему родителю.

Дерево с одним узлом удовлетворяет обоим свойствам, поэтому оно является допустимой максимальной кучей.