Рубрики

G-Fact 11

Следующее отношение выполняется в любом n-арном дереве, в котором каждый узел имеет 0 или n дочерних элементов.

L = (n-1) * I + 1

Где L — количество листовых узлов, а I — количество внутренних узлов.

Доказательство:
Дерево это н-арное дерево. Предположим, что он имеет T общих узлов, которые являются суммой внутренних узлов (I) и конечных узлов (L). Дерево с T полными узлами будет иметь (T — 1) ребер или ветвей.

Другими словами, так как дерево является n-арным деревом, каждый внутренний узел будет иметь n ветвей, дающих общее количество n * I внутренних ветвей. Поэтому мы имеем следующие отношения из приведенных выше объяснений,

n * I = T — 1
L + I = T

Из приведенных выше двух уравнений легко доказать, что L = (n — 1) * I + 1.

Спасибо venki за предоставление доказательства.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

G-Fact 11

0.00 (0%) 0 votes