Количество узлов дерева, где каждый узел имеет два дочерних узлов

Question

Я дерево, которое имеет следующий вид:

На первых изображений, высота дерева равна 1, и есть 3 общих узла. 2 для 7 на следующем и 3 для 15 для последнего. Как я могу определить, сколько будет числа узлов, которые будут иметь дерево этой формы из l высоты? Кроме того, что это за дерево (что называется, в частности?)?

Answer 1

Это perfect binary tree

Вы можете получить номер узла с учетом рекурсивного Approch:

n(0) = 1 
n(l+1) = n(l) + 2^l 

так

n(l) = 2^(l+1) - 1 

Answer 2

Количества узлов в полном дереве ..

n = 2^(h + 1) - 1.

Answer 3

Полное двоичное дерево на глубине 'd' является строго двоичным деревом, где все листья находятся на уровне d.

• для Fig1, д = 1
• для fig2, д = 2
• для fig3, д = 3

Итак, Пусть двоичное дерево Т глубины d. Затем в большинстве

2(d+1)-1 узлов n может быть там в T.

• для Fig1, д = 1; 2(1+1)-1 = 2(2)-1 = 4-1 = 3
• для fig2, d = 2; 2(2+1)-1 = 2(3)-1 = 8-1 = 7
• для fig3 d = 3; 2(3+1)-1 = 2(4)-1 = 16-1 = 15

высота (h) и глубина (d) дерева (длина самого длинного пути от корня до листа узла) численно равны.

Вот answer, где подробно описано, как вычислить глубину и высоту.

Answer 4

То, что вы описываете, звучит как «идеальное двоичное дерево». «двоичное дерево - это структура данных дерева, в которой каждый узел имеет не более двух детей» http://en.wikipedia.org/wiki/Binary_tree Идеальное дерево «Бинарное дерево со всеми узлами листа на одной глубине." http://xlinux.nist.gov/dads//HTML/perfectBinaryTree.html

высоты до максимального числа узлов в идеальном бинарном дереве = 2^(высота + 1) -1

число узлов до минимальной высоты = ПОТОЛКА (LOG (узлы + 1,2) -1,1)

Определения, связанные с бинарными деревьями можно найти в вики Википедии цитированной ранее.

Answer 5

Это также можно понять, как это.

В случае совершенного двоичного дерева общее количество листовых узлов являются 2^Н (Н = высота дерева)

и общее количество внутренних узлов являются 2^Н - 1

Следовательно, общее число узлов будет 2^H + 2^H - 1, что составляет 2^(H + 1) - 1, как упомянуто другими.

Надеюсь, это поможет.