Я запутался в терминологии нижележащих деревьев, я изучал Дерево, и я не могу различать эти деревья:
a) Полное двоичное дерево
b) Строковое двоичное дерево
c) Полное двоичное дерево
Пожалуйста, помогите мне разделить эти деревья. Когда и где эти деревья используются в структуре данных?
Полное двоичное дерево (иногда правильное двоичное дерево или 2-дерево или строго двоичное дерево) - это дерево, в котором каждый node, кроме листьев, имеет двух детей.
Таким образом, у вас нет узлов с одним ребенком. Кажется, это то же самое, что и строковое двоичное дерево.
Вот изображение полного/строкового двоичного дерева, из google:
Полное двоичное дерево - это двоичное дерево, в котором каждый уровень, за исключением, возможно, последнего, полностью заполняется, и все узлы как можно более далеки.
Кажется, это сбалансированное дерево.
Вот изображение полного двоичного дерева, из google, полная часть изображения - бонус.
Идеальное дерево:
x
/ \
/ \
x x
/ \ / \
x x x x
/ \ / \ / \ / \
x x x x x x x x
Полное дерево:
x
/ \
/ \
x x
/ \ / \
x x x x
/ \ /
x x x
Строгое/Полное Дерево:
x
/ \
/ \
x x
/ \
x x
/ \
x x
Существует различие между STRICT и FULL BINARY TREE.
1) FULL BINARY TREE: Бинарное дерево высотой h, содержащее точно (2 ^ h) -1, называется полным бинарным деревом. (Ссылка: Pg 427, Структуры данных, алгоритмы и приложения в С++ [Университетская пресса], второе издание Sartaj Sahni).
или другими словами
В FULL BINARY TREE каждый node имеет ровно 0 или 2 детей, и все листовые узлы находятся на одном уровне.
Пример: Ниже приведено ПОЛНОЕ БИНАРНОЕ ДЕРЕВО:
18
/ \
15 30
/ \ / \
40 50 100 40
2) STRICT BINARY TREE: Каждый node имеет ровно 0 или 2 детей.
Например: Ниже приведено строковое бинарное дерево:
18
/ \
15 30
/ \
40 50
Я думаю, что нет смысла в определении полного двоичного дерева, все еще для полноты сообщения, которое я хотел бы рассказать, что такое полное двоичное дерево.
3) ПОЛНОЕ БИНАРНОЕ ДЕРЕВО: Двоичное дерево является полным двоичным деревом, если все уровни полностью заполнены, за исключением, возможно, последнего уровня, а последний уровень имеет все возможные ключи.
Пример: Ниже приведено ПОЛНОЕ БИНАРНОЕ ДЕРЕВО:
18
/ \
15 30
/ \ / \
40 50 100 40
/ \ /
8 7 9
Примечание: Следующее также представляет собой полное двоичное дерево:
18
/ \
15 30
/ \ / \
40 50 100 40
Отказ от ответственности - Основным источником некоторых определений является википедия, любые предложения по улучшению моего ответа приветствуются.
Хотя этот пост имеет принятый ответ и является хорошим, я все еще был в замешательстве и хотел бы добавить еще несколько разъяснений относительно разницы между этими условиями.
(1) ПОЛНОЕ БИНАРНОЕ ДЕРЕВО -. Полное двоичное дерево - это двоичное дерево, в котором каждый node, кроме листьев, имеет двух дочерних элементов. Это также называется строго бинарным деревом.
Вышеприведенные два являются примерами полного или строго бинарного дерева.
(2) ПОЛНОЕ БИНАРНОЕ ДЕРЕВО -. Теперь определение полного двоичного дерева довольно неоднозначно, в нем говорится: - Полное двоичное дерево - это двоичное дерево, в котором каждый уровень, за исключением, возможно, последнего, полностью заполнена, и все узлы как можно дальше. Он может иметь от 1 до 2h узлов, насколько это возможно, на последнем уровне h
Обратите внимание на строки, выделенные курсивом.
Неоднозначность лежит в курсивом, "за исключением, возможно, последнего", что означает, что последний уровень также может быть полностью заполнен, т.е. это исключение не всегда должно выполняться. Если исключение не выполняется, то это точно так же, как и второе изображение, которое я написал, которое также можно назвать идеальным бинарным деревом. Таким образом, идеальное двоичное дерево также полно и полно, но не наоборот, что будет понятно еще одним определением, которое мне нужно указать:
ПОЧТИ ПОЛНОЕ БИНАРНОЕ ДЕРЕВО - Когда выполняется исключение в определении полного бинарного дерева, оно называется почти полным двоичным деревом или почти полным двоичным деревом. Это всего лишь тип полного бинарного дерева, но для его более четкого определения требуется отдельное определение.
Таким образом, почти полное двоичное дерево будет выглядеть так: вы можете видеть на изображении узлы как можно дальше, так что это больше похоже на подмножество полного двоичного дерева, чтобы сказать более строго, каждое почти полное бинарное дерево полное двоичное дерево, но не наоборот.
Завершая из вышеприведенных ответов, Вот точная разница между полными/строго, полными и совершенными бинарными деревьями
Полное/строго бинарное дерево: - Каждый node, за исключением листовых узлов, имеет два дочерних элемента
Полное двоичное дерево: - Каждый уровень, за исключением последнего уровня, полностью заполняется, и все узлы остаются в силе.
Идеальное двоичное дерево: - Каждый node, за исключением листовых узлов, есть два ребенка, и каждый уровень (последний уровень тоже) полностью заполнен.
Рассмотрим двоичное дерево, узлы которого вычерчены в виде дерева. Теперь начните нумерацию узлов сверху вниз и слева направо. Полное дерево имеет следующие свойства:
Если n имеет дочерние элементы, то все узлы с номером меньше n имеют два дочерних элемента.
Если n имеет один дочерний элемент, он должен быть левым дочерним, а все узлы меньше n имеют два дочерних элемента. Кроме того, node с номером больше n имеет дочерние элементы.
Если n не имеет детей, то no node с номером больше n имеет дочерние элементы.
Для представления кучи можно использовать полное двоичное дерево. Он может быть легко представлен в непрерывной памяти без пробелов (т.е. Все элементы массива используются, за исключением любого пространства, которое может существовать в конце).
Полное двоичное дерево - это полное двоичное дерево, но наоборот невозможно, и если глубина двоичного файла равна n. узлов в полном двоичном дереве (2 ^ n-1). В двоичном дереве нет необходимости, чтобы у него было два дочерних, но в полном двоичном файле каждый node не имел ни одного, ни двух дочерних элементов.
Чтобы начать с основ, очень важно понять бинарное дерево, чтобы понять различные его типы.
Дерево является двоичным деревом тогда и только тогда, когда: -
- Он имеет корень node, у которого могут не быть дочерние узлы (0 дочерних узлов, NULL-дерево)
-Root node может иметь 1 или 2 дочерних узла. Каждый такой node формирует само черное дерево
- Количество дочерних узлов может быть 0, 1, 2....... не более 2
- существует уникальный путь от корня до любого другого node
Пример:
X
/ \
X X
/ \
X X
Приступая к вашим запрошенным терминологиям:
Двоичное дерево - это полное двоичное дерево (высота h, мы корнем node как 0) тогда и только тогда, когда: -
Уровень 0 до h-1 представляет собой полное двоичное дерево высоты h-1
- Один или несколько узлов уровня h-1 могут иметь 0 или 1 дочерние узлы
Если j, k - узлы уровня h-1, то j имеет больше дочерних узлов, чем k, если и только если j находится слева от k, т.е. на последнем уровне (h) могут отсутствовать узлы листа, присутствующие должны быть сдвинуты влево
Пример:
X
/ \
/ \
/ \
X X
/ \ / \
X X X X
/ \ / \ / \ / \
X X X X X X X X
Двоичное дерево является строго бинарным деревом тогда и только тогда, когда: -
Каждый node имеет ровно два дочерних узла или узлы
Пример:
X
/ \
X X
/ \
X X
/ \ / \
X X X X
Двоичное дерево является полным двоичным деревом тогда и только тогда, когда: -
Каждый не-лист node имеет ровно два дочерних узла
Все листовые узлы находятся на одном уровне
Пример:
X
/ \
/ \
/ \
X X
/ \ / \
X X X X
/ \ / \ / \ / \
X X X X X X X X
/ \ / \ / \ / \ / \ / \ / \ / \
X X X X X X X X X X X X X X X X
Вы также должны знать, что такое идеальное бинарное дерево?
Двоичное дерево является идеальным бинарным деревом тогда и только тогда, когда: -
- полное двоичное дерево
- все листовые узлы находятся на одном уровне
Пример:
X
/ \
/ \
/ \
X X
/ \ / \
X X X X
/ \ / \ / \ / \
X X X X X X X X
/ \ / \ / \ / \ / \ / \ / \ / \
X X X X X X X X X X X X X X X X
Ну, извините, я не могу опубликовать изображения, так как у меня нет 10 репутации. Надеюсь, это поможет вам и другим!
В моем ограниченном опыте с бинарным деревом, я думаю:
Полное двоичное дерево - это двоичное дерево, в котором каждый node имеет 0 или 2 детей. Другими словами, каждый node в дереве, кроме листьев, имеет ровно двух детей.
A Полное двоичное дерево - это двоичное дерево, в котором каждый уровень дерева полностью заполнен, за исключением последнего уровня. Кроме того, на последнем уровне узлы должны быть прикреплены, начиная с самого левого положения. Полное двоичное дерево должно удовлетворять следующим условиям:
Рассмотрим бинарное дерево высотой 'h'. Двоичное дерево называется полным двоичным деревом, если все листья присутствуют на высоте "h" или "h-1" без пропущенных чисел в последовательности.
1
/ \
2 3
/ \
4 5
Это полное двоичное дерево.
1
/ \
2 3
/ /
4 6
Это не полное двоичное дерево, так как узел с номером 5 отсутствует в последовательности