Нахождение номера листьев

Question

N-арное дерево имеет N подузлов для каждого узла. Если дерево имеет M неконечных узлов, как найти число листовых узлов?

Answer 1

Прежде всего, если корнем является уровень 0, тогда K -й уровень дерева будет иметь N^K узлы.Вы можете начать увеличивать уровень счетчика за уровнем, пока не получите M узлов.Таким образом, вы найдете, сколько уровней состоит из дерева.А число конечных узлов - это число узлов на последнем уровне - это N^lastLevel.

Вот пример: N = 3, M = 4.

First level = 3^0 = 1
Second level = 3^1 = 3
1 + 3 = 4

Итак, мы обнаружили, чтоДерево имеет два уровня (считая от 0).Ответ: 3^2 = 9.

Примечание: номер уровня можно также найти напрямую, заметив, что M является суммой геометрической прогрессии: 1 + 3 + 9 + 27 ... = M

Надеюсь, что это понятно.

Answer 2

Математически говоря, узлы увеличиваются в геометрической прогрессии.

0-й уровень - 1
1-й уровень - n
2 уровень - n ^ 2
3 уровень - n ^ 3
.... м-й уровень - n ^ m

Таким образом, общее количество узлов на уровне m-1 равно 1 + n + n ^ 2 + .. + n ^ m-1.

Теперь есть хорошая формула для вычисления 1 + a + a ^ 2 + a ^ 3 + ... + a ^ m, которая (1 - n ^ (m + 1)) / (1-n), назовем эту величину K.

Теперь нам нужно количество листовых узлов, которое равно n ^ m, и то, что мы имеем, это K., то есть общее количество неконечных узлов. Выполнив некоторые настройки математической формулы, вы обнаружите, что
n ^ m = K * (n-1) + 1.

например. Скажем, в 3-х дереве общее число неконечных узлов равно 40, затем, используя эту формулу, вы получите общее число листовых узлов равным 81, что является правильным ответом.