Полное бинарное дерево против полного бинарного дерева
Бинарное дерево - это дерево, в котором каждый узел имеет одного или двух потомков. В бинарном дереве узел не может иметь более двух потомков. В бинарном дереве дочерние элементы называются «левыми» и «правыми» дочерними элементами. Дочерние узлы содержат ссылку на своего родителя. Полное бинарное дерево - это бинарное дерево, в котором все уровни бинарного дерева полностью заполнены, кроме последнего уровня. На незаполненном уровне узлы присоединяются, начиная с крайнего левого положения. Полное бинарное дерево - это дерево, в котором каждый узел дерева имеет двух потомков, кроме листьев дерева.
Что такое полное двоичное дерево?
Полное бинарное дерево - это бинарное дерево, в котором каждый узел в дереве имеет ровно ноль или два потомка. Другими словами, каждый узел дерева, кроме листьев, имеет ровно двух потомков. На рисунке 1 ниже показано полное бинарное дерево. В полном бинарном дереве количество узлов (n), количество ветвей (l) и количество внутренних узлов (i) связаны особым образом, так что если вы знаете любой из них, вы можете определить два других. значения следующим образом:
1. Если полное бинарное дерево имеет i внутренних узлов:
– Количество листьев l=i+1
– Общее количество узлов n=2i+1
2. Если полное бинарное дерево имеет n узлов:
– Количество внутренних узлов i=(n-1)/2
– Количество листьев l=(n+1)/2
3. Если полное бинарное дерево имеет l листьев:
– Общее количество узлов n=2l-1
– Количество внутренних узлов i=l-1
Что такое полное двоичное дерево?
Как показано на рисунке 2, полное бинарное дерево - это бинарное дерево, в котором все уровни дерева полностью заполнены, кроме последнего уровня. Кроме того, на последнем уровне узлы должны быть присоединены, начиная с крайнего левого положения. Полное бинарное дерево высоты h удовлетворяет следующим условиям:
– От корневого узла уровень выше последнего уровня представляет собой полное бинарное дерево высоты h-1
– Один или несколько узлов на последнем уровне могут иметь 0 или 1 потомка
– Если a, b - два узла на уровне выше последнего уровня, то a имеет больше потомков, чем b, тогда и только тогда, когда a расположен слева от b
В чем разница между полным двоичным деревом и полным двоичным деревом?
Полные бинарные деревья и полные бинарные деревья имеют четкое различие. В то время как полное бинарное дерево - это бинарное дерево, в котором каждый узел имеет ноль или двух дочерних элементов, полное бинарное дерево - это бинарное дерево, в котором все уровни бинарного дерева полностью заполнены, кроме последнего уровня. Некоторые специальные структуры данных, такие как кучи, должны быть полными бинарными деревьями, хотя они и не должны быть полными бинарными деревьями. В полном бинарном дереве, если вы знаете общее количество узлов, количество лав или количество внутренних узлов, вы можете очень легко найти два других. Но полное бинарное дерево не имеет специального свойства, связывающего эти три атрибута.
