Количество листовых узлов в бинарном дереве

Question

Я прочитал, что число конечных узлов в дереве высотой Н, по крайней мере час + 1

Но, как показано здесь в ПОС

Дерево имеет высоту 2, но число узлов листа составляет всего 2 (по крайней мере), а не 3. Где я ошибаюсь?

Answer 1

Утверждение, что количество листьев в дереве с высотой h не менее h + 1 явно ложно - просто рассмотрите связанный список длины h, который имеет только один листовой узел. Либо источник, который вы читаете, является неправильным, либо он делает некоторые дополнительные предположения о структуре дерева.

EDIT: Возможно, что оригинальное доказательство говорит о том, что в дереве есть как минимум h + 1 указатели NULL. Это утверждение действительно верно, как мы можем видеть по индукции. В качестве базового случая дерево одиночных узлов имеет высоту 0 и имеет два указателя NULL, поэтому требование выполняется для h = 0. Для индуктивного шага предположим, что требование выполняется для всех деревьев с высотой h '< h и рассматривает любое дерево высота h. Одно из его поддеревьев должно иметь высоту h - 1 и по индуктивному предположению должно иметь h NULL указателей. Теперь рассмотрим другое поддерево. Если нет другого поддерева, корень вносит указатель (h + 1) st NULL, и мы закончили. В противном случае существует поддерево высот k для k ≥ 0, и поэтому по индуктивному предположению есть по крайней мере (k + 1) ≥ 1 указатели NULL, поэтому само дерево имеет по крайней мере h + 1 указатели NULL, завершая доказательство ,

Answer 2

заявления вы сделали верно, если и только если вы говорите о совершенном бинарном дереве:

Идеальное бинарное дерево представляет собой полное бинарное дерева, в котором все листы находятся на тот же глубине или же уровень

Answer 3

Я знаю, что это старый, но в случае, если кто-то попадается здесь, чтобы найти листья: (п - 1) - (п/2) где п = общее число узлов , В этом случае это (4 - 1) - (4/2) = 3 - 2 = 1