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

Question

Я рассчитываю рассчитать минимальное и максимальное количество узлов и листьев в укорененном дереве с высотой h и степенью d.

Я предполагаю, что минимальное количество листьев всегда равно 1 (если h> = 2). Максимальное количество узлов должно быть G ^ (h-2), листья должны быть G ^ (h-1). Для минимального количества узлов я не в курсе.

Я прав или я что-то упустил?

Answer 1

Учитывая, что дерево имеет высоту h и степень d, применяется следующее.

Минимальное количество узлов

Чтобы построить дерево высоты h с таким количеством узловнасколько возможно, вы захотите, чтобы у каждого узла был только один дочерний элемент.Следовательно, вам понадобится h узлов.

Максимальное количество узлов

Чтобы использовать как можно больше узлов, вам нужно, чтобы каждый узел (кроме листьев) имелкак можно больше детей, то есть детей.Это будет выглядеть так:

level      nodes at level 

  1              1    (d^0)
  2              d    (d^1)
  3              d^2
  4              d^3

Таким образом, число узлов представляет собой сумму, подобную

num_nodes = d^0 + d^1 + d^2 + d^3 + ....

Это геометрическая сумма, которая может быть рассчитана как:

num_nodes = (1 - d^h)/(1 - d)