Полное бинарное дерево и определения совершенного бинарного дерева

Question

У меня мало вопросов о типах двоичного дерева.

ЗАВЕРШЕНИЕ ДВОЙНОГО ДЕРЕВА: Двоичное дерево завершено Двоичное дерево, если все уровни полностью заполнены, за исключением, возможно, последнего уровня и последнего уровняимеет все ключи как можно левее.

Почти каждый пример для полного бинарного дерева приведен так. На одном из последних узлов остался только дочерний элемент.

          18
       /       \  
     15         30  
    /  \        /  
  40    50    100   

Все нормально.

Мой вопрос: Является ли следующее дерево также полным двоичным деревом?

           18
       /       \  
     15         30  
    /  \        
  40    50    

Я знаю, что это также полное двоичное дерево.

Мой второй вопрос: если оно является одновременно полным двоичным деревоми полное двоичное дерево, можно ли сказать, что оно также является идеальным двоичным деревом?(Последнее дерево, которое я написал)

Answer 1

1-й ответ

Да Это дерево также можно назвать полным двоичным деревом.

Пояснение

Полный двоичный файлДерево:

Как вы упомянули, любое дерево, в котором все уровни полностью заполнены и последний уровень имеет как можно более левые ключи, рассматривается как двоичное дерево.Это условие удовлетворяет вашему примеру, поэтому это полное двоичное дерево.

Полное двоичное дерево:

Любое двоичное дерево, в котором все узлы, кроме конечного узла, имеют двух дочерних элементов, затем рассматривается как полное двоичное дерево.,1-е рассматриваемое дерево не является полным двоичным деревом, а 2-е дерево является полным двоичным деревом.

2-й ответ

Нет, если дерево является как полным, так и полным, что не означает, что выМожно назвать это идеальным двоичным деревом.

Бинарное дерево считается совершенным, если оно заполнено и все листья находятся на одном уровне.В вашем примере это не идеальное двоичное дерево.