Бинарное дерево представляет собой структуру, в которой каждый узел (или вершина) имеет не более двух узлов-потомков и в точности одного родителя. Самый верхний узел дерева является единственным узлом без родителей; он называется корневым узлом, или корнем.
Бинарное дерево с N узлами имеет не меньше ⌊log2N + 1⌋ уровней (при максимально плотной упаковке узлов).
Например, у полного бинарного дерева с 15 узлами один корень, два узла на втором уровне, четыре узла на третьем уровне и восемь узлов на четвертом уровне; наше равенство также дает ⌊log215⌋ + 1 = ⌊3,9⌋ + 1 = 4 уровня.
Заметим, что добавление еще одного узла к дереву приведет к необходимости появления нового уровня, и их число станет равным ⌊log216⌋ + 1 = ⌊4⌋ + 1 = 5.
В самом большом бинарном дереве с N узлами N уровней: у каждого узла этого дерева в точности один потомок (и само дерево представляет собой просто список) .
Заметим, что добавление еще одного узла к дереву приведет к необходимости появления нового уровня, и их число станет равным ⌊log216⌋ + 1 = ⌊4⌋ + 1 = 5.
В самом большом бинарном дереве с N узлами N уровней: у каждого узла этого дерева в точности один потомок (и само дерево представляет собой просто список) .
Если уровни дерева занумеровать, считая что корень лежит на уровне 1, то на уровне с номером k лежит не более чем 2k-1 узла.
У полного бинарного дерева с j уровнями (занумерованными от 1 до j) все листья (узлы без потомков) лежат на уровне с номером j, и у каждого узла на уровнях с первого по j - 1 в точности два непосредственных потомка.
В полном бинарном дереве с j уровнями 2j - 1 узел.
У полного бинарного дерева с j уровнями (занумерованными от 1 до j) все листья (узлы без потомков) лежат на уровне с номером j, и у каждого узла на уровнях с первого по j - 1 в точности два непосредственных потомка.
В полном бинарном дереве с j уровнями 2j - 1 узел.
