Полное двоичное дерево против полного двоичного дерева
Двоичное дерево - это дерево, в котором каждый узел имеет одного или двух дочерних элементов. В двоичном дереве узел не может иметь более двух дочерних элементов. В бинарном дереве дочерние элементы называются «левыми» и «правыми» дочерними элементами. Дочерние узлы содержат ссылку на своего родителя. Полное двоичное дерево - это двоичное дерево, в котором все уровни двоичного дерева полностью заполнены, кроме последнего уровня. На незаполненном уровне узлы прикрепляются, начиная с самого левого положения. Полное двоичное дерево - это дерево, в котором каждый узел в дереве имеет двух дочерних элементов, кроме листьев дерева.
Что такое полное двоичное дерево?
Полное двоичное дерево - это двоичное дерево, в котором каждый узел в дереве имеет ровно ноль или два дочерних элемента. Другими словами, у каждого узла в дереве, кроме листьев, ровно два дочерних элемента. На рисунке 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
В чем разница между полным двоичным деревом и полным двоичным деревом?
Полные бинарные деревья и полные бинарные деревья имеют явное различие. В то время как полное двоичное дерево - это двоичное дерево, в котором каждый узел имеет ноль или два дочерних элемента, полное двоичное дерево - это двоичное дерево, в котором все уровни двоичного дерева полностью заполнены, кроме последнего уровня. Некоторые специальные структуры данных, такие как кучи, должны быть полными двоичными деревьями, в то время как они не должны быть полными двоичными деревьями. В полном двоичном дереве, если вы знаете общее количество узлов, или количество ступеней, или количество внутренних узлов, вы можете очень легко найти два других. Но полное двоичное дерево не имеет особого свойства, связанного с этими тремя атрибутами.
