Как сделать полное бинарное дерево с 6 узлами?

Question

Я хорошо знаю о Полном двоичном дереве и Полном двоичном дереве.Но невозможно создать полное двоичное дерево только с 6 узлами.

Answer 1

Прорабатывая ответ @ vivek_23, это, к сожалению, невозможно.Есть красивая теорема, которая гласит следующее:

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

Интуиция за этой теоремой на самом деле довольно проста.Представьте, что вы взяли полное двоичное дерево и удалили из него все внутренние узлы.Теперь у вас есть лес из L одноузловых полных двоичных деревьев, по одному на каждый лист.Теперь добавьте внутренние узлы обратно по одному за раз.Каждый раз, когда вы это делаете, вы берете два разных дерева в лесу и объединяете их в одно дерево, что уменьшает количество деревьев в лесу на одно.Это означает, что у вас должно быть ровно L - 1 внутренних узлов, так как, если бы у вас было немного меньше, вы не смогли бы объединить все деревья в лесу, и если бы у вас было больше, у вас не хватило бы деревьев, чтобыобъединение.

Тот факт, что в полном двоичном дереве всего 2L - 1 узлов, означает, что число узлов в полном двоичном дереве всегда нечетное, поэтому вы не можете создать полное двоичное дерево с 6узлы.Тем не менее, вы можете создать полное двоичное дерево с любым количеством нечетных узлов - можете ли вы выяснить, как это доказать?

Надеюсь, это поможет!

Answer 2

Еще один способ увидеть, что полное двоичное дерево имеет нечетное количество узлов:

Начиная с определения полного двоичного дерева ( Википедия ):

дерево, в котором каждый узел имеет 0 или 2 дочерних элементов.

Это означает, что общее число дочерних узлов четное (0 + 2 + 2 + 0 + ... + 2 всегда четное). Существует только один узел, который не является дочерним по отношению к другому, который является корневым. Таким образом, учитывая этот узел, сумма становится нечетной.

Следовательно, не существует полного бинарного дерева с 6 узлами.

Answer 3

Ответ No.Вы не можете создать полное двоичное дерево всего с 6 узлами.Как говорится в определении Википедии :

Полное двоичное дерево (иногда его называют правильным или плоским двоичным деревом) - это дерево, в котором каждый узел имеет либо 0, либо2 детейДругой способ определения полного двоичного дерева - это рекурсивное определение.Полное двоичное дерево - это либо:

Одна вершина.

Дерево, у корневого узла которого есть два поддерева, оба из которых являются полными двоичными деревьями.

ДругоеИнтересное свойство, которое я заметил, заключается в том, что число узлов, необходимых для создания полного двоичного дерева, всегда будет нечетным.