Понимание мощности числа 2

Question

Предположим, если узел имеет N детей в дереве и высоту H, то общее число узлов равно N pow (H), или логика применяется только для 2 из-за базы базы 2?

Answer 1

Я предполагаю, что высота дерева с одним узлом 0.

Я также предполагая, что число детей каждого узла, кроме листьев N.

Пусть теперь Num (X) число узлов в дереве высоты X. Ответ, который мы ищем, - Num (H).

Теперь мы можем получить рекуррентное соотношение:

Num(H) = 1 + N.Num(H-1) 

Термин 1 является учет корня и каждого Num(H-1), как упоминалось выше, обозначает высоту поддерева с корнем в качестве потомка корня и там N детей основного корня.

Аналогично,

Num (Н) = 1 + N. (1 + N.Num (Н-2)) = 1 + N + N .Num (Н-2) = 1+ N + N + N + .... + N ^Н .Num (0)

Но Num (0) = 1, так как число узлов в дереве с высотой 0 1 т.е. один узел.

Следовательно, Кол-во (Н) = (N ^{Н + 1} -1)/(N-1)