Нашел формулу, чтобы узнать, сколько "дочерних" деревьев есть, если это дочернее дерево

Question

Моя проблема немного сложна для объяснения, потому что я не являюсь носителем английского языка, и я не знаю слова в этом вопросе, но я попытаюсь объяснить это.Если вы думаете, что у вас есть ключевое слово, чтобы помочь мне, не стесняйтесь, спасибо.

Итак, я объяснял концепцию двоичного дерева для новичка, и я дал ему формулу «2 ^ n - 1».Таким образом, если двоичное дерево заполнено и имеет глубину 3, в двоичном дереве будет элемент «2 ^ 3 - 1 = 7».

Тогда новичок спросил «что, если не только 2ребенок (слева и справа) но 3? Какая формула будет?(хорошо, если у каждого элемента есть 3 дочерних элемента, это больше не бинарное дерево, но потерпите меня, это ради аргумента).

Итак, приступил к поиску формулы, но не смог этого сделать.

Я знаю, что решение:

n

^ 3 ^ (x-1)

x = 1

но я не могу найти «упрощенную» версию, например

n

Ʃ 2 ^ (x-1)

x =1

дают 2 ^ n - 1

Существовала ли формула?Можем ли мы получить общую формулу с числом «C» в качестве числа дочернего элемента дерева?

Извините за мой английский, и спасибо за чтение.

Answer 1

Количество узлов C_{m,k} полного дерева высот k с m -при разветвлении определяется по формуле

C_{m,k} = (m^(k+1) - 1) / (m-1);

Доказательство:

Наблюдение: на уровне i точно есть m^i узлов в дереве. «Уровень» означает расстояние до корневого узла (следовательно, уровень корневого узла равен 0). Таким образом,

C_{m,k} = sum_{i=0..k} ( m^i )

Суммирование является конечной геометрической прогрессией (т. Е. Частное между последовательными элементами суммирования является константой). Общая формула ...

C_{m,k} = (m^(k+1) - 1) / (m-1);

... что легко проверить по индукции