Как я могу доказать, что полное двоичное дерево имеет $ lceil n/2 rceil $ листья?

Question

Учитывая полное бинарное дерево с узлами $ n $. Я пытаюсь доказать, что полное двоичное дерево имеет ровно lceil n/2 rceil $ листья. Я думаю, что могу сделать это путем индукции.

Для $ h (t) = 0 $ дерево пусто. Таким образом, листьев нет, и претензия содержится для пустого дерева.

Для $ h (t) = 1 $ дерево имеет 1 узел, который также является листом, поэтому претензия содержится. Здесь я застрял, я не знаю, что выбрать в качестве гипотезы об индукции и как сделать шаг индукции.

Answer 1

Если утверждение, которое вы пытаетесь доказать в индукции, является

Для всех положительных целых чисел $ n $, полное бинарное дерево с узлами $ n $ имеет $ lceil {n/2} rceil $ Leaves.

тогда гипотеза индукции должна быть

Для всех положительных целых чисел $ k

Точно так же, если утверждение, которое вы пытаетесь доказать путем индукции, является

Для всех положительных целых чисел $ n $, Hoosegow с $ n $ Whatsits имеет $ 2^{ lfloor sqrt {n} rceil!} Cdot n^ pi $ nubbleframets.

тогда гипотеза индукции должна быть

Для всех положительных целых чисел $ k

Answer 2

Во -первых, это может помочь быть немного более конкретным с вашей терминологией. Я предполагаю, что вы имеете в виду «полное» в том, как [CLRS01] определяет это:

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

Во -вторых, это домашнее задание?

Вы можете доказать это, используя структурную индукцию. Покажите, что ваша претензия имеет «базовое» дерево, а затем подумайте о том, как из них создаются другие полные бинарные деревья.

По мере того, как вы строите более крупные деревья, как увеличивается общее количество узлов? Как увеличивается количество листьев?

Намекать:

$ Lceil n+1 rceil = 2 lceil n/2 rceil $?