Найдена формула, чтобы узнать, сколько "дочерних" элементов у дерева, если это дочернее дерево
Моя проблема немного сложна для объяснения, потому что я не носитель английского языка и не знаю ни слова в этом вопросе, но я попытаюсь объяснить. Если вы думаете, что у вас есть ключевое слово, чтобы помочь мне, не стесняйтесь, спасибо.
Итак, я объяснял новичку концепцию бинарного дерева и дал ему формулу "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» в качестве числа дочерних элементов дерева?
Извините за мой английский, и спасибо за чтение.
Ответы 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);
... что легко доказать по индукции
да ! Я только что нашел источник, разъясняющий то, что вы только что сказали, поэтому я понимаю, что вы сказали. Блин, моя математика заржавела....