Сколько узлов в пустом двоичном дереве?

Question

Я получил этот вопрос, когда работал над функцией, которая возвращает количество узлов в двоичном дереве.

На мой взгляд, пустое двоичное дерево имеет корень, который указывает на nullptr в C ++, поэтомутехнически это один узел или ноль узлов.

Буду признателен, если кто-то сможет прояснить ситуацию.

Answer 1

Число узлов n в полном двоичном дереве составляет не менее n = 2h + 1 и не более n = 2 ^ (h + 1) -1, где h - высота дерева. Дерево, состоящее только из корневого узла, имеет высоту 0.

Википедия

Следовательно, ваш первый ответ действительно верен. инициализированное пустое двоичное дерево будет иметь только 1 узел, однако 0 по высоте.