Разница между полным двоичным деревом и полным двоичным деревом

Полное двоичное дерево против Полного двоичного дерева

Двоичное дерево - это дерево, в котором каждый узел имеет одного или двух дочерних элементов. В двоичном дереве узел не может иметь более двух дочерних элементов. В двоичном дереве дочерние элементы называются «левыми» и «правыми» дочерними элементами. Дочерние узлы содержат ссылку на своего родителя. Полное двоичное дерево - это двоичное дерево, в котором каждый уровень двоичного дерева полностью заполнен, кроме последнего уровня. На незаполненном уровне узлы присоединяются, начиная с крайней левой позиции. Полное двоичное дерево - это дерево, в котором каждый узел дерева имеет двух дочерних элементов, кроме листьев дерева..

Что такое полное бинарное дерево?

Полное двоичное дерево - это двоичное дерево, в котором каждый узел дерева имеет ровно ноль или два дочерних элемента. Другими словами, каждый узел дерева, кроме листьев, имеет ровно двух детей. На рисунке 1 ниже изображено полное двоичное дерево. В полном двоичном дереве число узлов (n), число лав (l) и количество внутренних узлов (i) связаны особым образом, так что если вы знаете какой-либо из них, вы можете определить два других значения следующим образом:

1. Если полное двоичное дерево имеет i внутренних узлов:

- Количество листьев l = i + 1

- Общее количество узлов n = 2 * i + 1

2. Если полное двоичное дерево имеет n узлов:

- Количество внутренних узлов i = (n-1) / 2

- Количество листьев l = (n + 1) / 2

3. Если полное двоичное дерево имеет l листьев:

- Общее количество узлов n = 2 * l-1

- Количество внутренних узлов i = l-1

Что такое полное бинарное дерево?

Как показано на рисунке 2, полное двоичное дерево - это двоичное дерево, в котором каждый уровень дерева полностью заполнен, кроме последнего уровня. Кроме того, на последнем уровне узлы должны быть присоединены, начиная с крайней левой позиции. Полное двоичное дерево высоты h удовлетворяет следующим условиям:

- От корневого узла уровень выше последнего уровня представляет полное двоичное дерево высоты h-1.

- Один или несколько узлов на последнем уровне могут иметь 0 или 1 детей

- Если a, b - два узла на уровне выше последнего уровня, то a имеет больше дочерних элементов, чем b, если и только если a расположен слева от b

В чем разница между Полным двоичным деревом и Полным двоичным деревом?

Полные двоичные деревья и полные двоичные деревья имеют четкую разницу. Хотя полное двоичное дерево - это двоичное дерево, в котором каждый узел имеет ноль или два потомка, полное двоичное дерево - это двоичное дерево, в котором каждый уровень двоичного дерева полностью заполнен, кроме последнего уровня. Некоторые специальные структуры данных, такие как кучи, должны быть полными двоичными деревьями, в то время как они не должны быть полными двоичными деревьями. В полном бинарном дереве, если вы знаете количество общих узлов или число лав, или количество внутренних узлов, вы можете легко найти два других. Но полное двоичное дерево не имеет специального свойства, связанного с этими тремя атрибутами.