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

Question

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

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

Answer 1

Сделанное вами утверждение верно, если и только если вы говорите об идеальном бинарном дереве:

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

Answer 2

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

РЕДАКТИРОВАТЬ: Возможно, что оригинальное доказательство сказал, что в дереве есть по крайней мере h + 1 NULL указателей. Это утверждение действительно верно, как мы можем видеть по индукции. В качестве базового случая дерево одного узла имеет высоту 0 и два указателя NULL, поэтому утверждение выполняется для h = 0. Для индуктивного шага предположим, что утверждение выполняется для всех деревьев высоты h '

Answer 3

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